Basic Concept of Graph Structures

Graphs are basically an extension of binary trees. This section covers terminology, a general-purpose implementation, and graph traversal algorithms.

Core Concepts in Graph Theory

A graph consists of a collection of vertices (also called nodes) together with edges that link pairs of those vertices.

Every vertex is assigned a distinct identifier.
Edges may be directed, producing a directed graph, or undirected, producing an undirected graph.
Edges may also carry numeric weights, yielding a weighted graph, or carry none, yielding an unweighted graph.

Edge Direction and Weight

Consider a directed unweighted graph below:

A directed edge running from vertex 3 to vertex 2 permits travel from 3 to 2 in a single step, yet the absence of an edge in the opposite direction means travel from 2 back to 3 is impossible in one step.

Now consider an undirected unweighted graph.
An undirected edge joining vertex 1 and vertex 3 permits travel in either direction: from 1 to 3 or from 3 to 1.

An undirected graph can be viewed as a bidirectional structure. In practice, an undirected edge is frequently stored in code as a pair of opposing directed edges.

A directed weighted graph assigns a numeric cost or distance to each directed edge.

An undirected weighted graph does the same for each undirected edge.

Weighted graphs appear frequently outside pure theory. In a mapping application the weight of an edge may represent the physical distance between two locations; in a logistics network the weight may represent the cost of shipping goods between two sites.

Several foundational algorithms operate on weighted graphs, among them algorithms for shortest paths and minimum spanning trees. Those algorithms are examined in subsequent chapters.

Degree of a Vertex

Every vertex possesses a degree.
In an undirected graph the degree of a vertex equals the number of edges incident to it.

In the undirected example that follows, vertex 1 has degree 2 while vertex 4 has degree 4.

In a directed graph direction matters, so each vertex is characterized by both an indegree and an outdegree.

In the directed example that follows, vertex 3 has no indegree (no edge points toward it) and outdegree 4 (fours edges leaves it).

Relationship Between Edges and Vertices

A simple graph has E edges and V nodes. What range can E take?

The minimum is 0: unconnected nodes are still a valid graph.

For the maximum, each node can connect to at most V−1 others, giving E = V(V−1)/2 ≈ V².

If E is close to V², the graph is dense. If E is much smaller than V², it's sparse.

Connectivity

Connectivity concerns the existence of paths between vertices and is one of the central ideas in graph theory.

Connectivity for Undirected Graphs

An undirected graph is connected when a path exists between every pair of its vertices.
The graph that follows is connected: from any vertex it is possible to reach every other vertex.

In a disconnected undirected graph each maximal connected piece is called a connected component. A single graph may contain several such components.

The graph that follows contains two connected components: vertices 1 through 5 form one component while vertices 6 and 7 form another.