Essential Algorithms, 2nd Edition

CHAPTER 13Basic Network Algorithms

Chapters 10–12 explained trees. This chapter describes a related data structure: the network. Like a tree, a network contains nodes that are connected by links. Unlike the nodes in a tree, however, the nodes in a network don't necessarily have a hierarchical relationship. In particular, the links in a network may create cycles, so a path that follows the links could loop back to its starting position.

This chapter explains networks and some basic network algorithms, such as detecting cycles, finding shortest paths, and finding a tree that is part of the network that includes every node.

Network Terminology

Network terminology isn't quite as complicated as tree terminology, because it doesn't borrow as many terms from genealogy, but it's still worth taking a few minutes to review the relevant terms.

A network consists of a set of nodes connected by links. (Sometimes, particularly when you're working on mathematical algorithms and theorems, a network is called a graph, nodes are called vertices, and links are called edges.) If node A and node B are directly connected by a link, they are adjacent and are called neighbors.

Unlike the case with a tree, a network has no root node, although there may be particular nodes of interest depending on the network. For example, a transportation network might contain special hub nodes where buses, trains, ferries, or other vehicles start and end their routes.

A link can be undirected (you can traverse it ...