Book Image

C++ Data Structures and Algorithm Design Principles

By : John Carey, Anil Achary, Shreyans Doshi, Payas Rajan
Book Image

C++ Data Structures and Algorithm Design Principles

By: John Carey, Anil Achary, Shreyans Doshi, Payas Rajan

Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.
Table of Contents (11 chapters)


In the previous two chapters, we discussed two algorithm design paradigms: divide and conquer and the greedy approach, which led us to well-known solutions to widely used and important computational problems such as sorting, searching, and finding the minimum weight spanning tree on a graph. In this chapter, we shall discuss some algorithms that are specifically applicable to the graph data structure.

A graph is defined as a set of vertices and edges that connect a pair of vertices. Mathematically, this is often written as G = < V, E >, where V denotes the set of vertices and E denotes the set of edges that constitute a graph. Edges that point from one node to another are called directed, while edges that have no direction are called undirected. Edges may also be associated with a weight or be unweighted, as we saw in Chapter 2, Trees, Heaps, and Graphs.


The terms "node" and "vertex" can be used interchangeably when we talk about graphs. In this chapter...