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 graphs. In this chapter...