3.8.1. Representation of Graph

Graphs can be categorized in terms of direction and weight. In a weighted graph, edges have weights or costs associated with them, which can represent distances, costs, or any numerical value attributed to the connection between two vertices.

3.8.1.1. Adjacency Matrix

Adjacency Matrix can represent all graphs. For weighted graph, the elements of the matrix indicate the weight of the edge between the vertices, with the rows representing the source vertices and the columns representing the destination vertices. For unweighted graph, we can use 0 or 1 to represent if there is a connection between two vertices.

vector<vector<int>> graph; // always a square matrix.

3.8.1.2. Adjacency List

An adjacency list is a collection of lists used to represent a graph. Each list corresponds to a vertex in the graph and contains the neighbors of that vertex. This representation is efficient in terms of storage for sparse graphs, where the number of edges is much less than the square of the number of vertices. It’s also efficient for iterating over the neighbors of a vertex, making it a preferred choice for algorithms that need to do this frequently, such as depth-first search (DFS) or breadth-first search (BFS). A graph can be represent as a successor graph or a predecessor graph. If no specified, it is a successor graph.

unordered_map<int, set<int>> graph;

The below are some examples for various graphs represented in adjacent list.

  • Undirected Unweighted Graph

unordered_map<string, unordered_set<string>> graph; // Word Ladder I/II

  • Unweighted DAG

unordered_map<int, unordered_set<int>> suc, pre; // Course Schedule I
vector<int, vector<int>> G; // Course Schedule II
unordered_set<int> ns;

  • Weighted Graph

unordered_map<string, unordered_map<string,double>> G; //Evaluate Division
G["a"]["b"]=2.0;
G["b"]["a"]=1/2.0;

3.8.1.3. Edge List

An edge list is a simple and straightforward way to represent a graph, consisting of a list where each element represents an edge between two vertices. For an unweighted graph, each element can be a pair (tuple, 2-element array, etc.) of vertices indicating a direct connection between them. For a weighted graph, each element in the list can be a triplet (or a tuple with three elements), where the first two elements represent the vertices connected by the edge, and the third element represents the weight of the edge.

vector<pair<int,int>> unweighted_graph;
vector<tuple<int,int,int>> weighted_graph;

Sometimes we need to convert the edge list to adjacency list before applying algorithms.

In Section 3.8.5.3, we use a special representation(edge list ordered by weight) for the graph.

map<int, unordered_map<int, int>> m;  // w => (a -> b), weight-indexed map

3.8.1.4. Logical Graph

The Logical graph is also called implicit graph. It could be anything which can be considered as a graph, such as a matrix, or a game board and its next possible states. To solve questions like 8-puzzle, magic squares, we use logical graph in our minds, but not explicitly represent them in code.