Introduction

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.

Note

The terms "node" and "vertex" can be used interchangeably when we talk about...