Algorithms #3 Graph Algorithms

Tags:

Algorithms & Data Structure Content List Algorithms #1 Sort

• ComputerScience

#SWE#ComputerScience

This note mainly covers various graph algorithms.

Graphs

Definition

Regarding graphs, there are a series of not-so-complex definitions. Here we briefly list some of them.

1. A graph is a data model consisting of a set of vertices and the edges connecting them.
2. Parallel edges refer to a set of edges connecting the same pair of vertices.
3. A self-loop is an edge connecting a vertex to itself.
4. A graph without parallel edges and self-loops is called a simple graph. Unless otherwise specified, when we refer to a graph we mean a simple graph.
5. Two vertices connected by an edge are adjacent (neighbors).
6. A directed graph is one where edge ab and edge ba are not considered the same. In an undirected graph, edge ab and edge ba are considered the same edge.
7. In an undirected graph, the degree of a vertex is the number of edges incident to it.
8. In a directed graph, the out-degree of a vertex is the number of edges leaving it, and the in-degree is the number of edges entering it.
9. A path is a sequence of connected edges and the vertices they pass through. A simple path is a path with no repeated vertices.
10. A cycle (loop) is a path with at least one edge where the start and end vertices are the same. A simple cycle is a cycle where except for the start and end being the same, there are no repeated vertices or edges.
11. The length of a path is the number of edges in it.
12. A connected graph is one where there exists at least one path from any vertex to any other vertex.
13. A disconnected graph consists of several connected subgraphs, which are called connected components.
14. A tree is a connected acyclic graph.

This is basically sufficient for discussing the content of this note.

Implementation

From an implementation perspective, a graph only needs to maintain edges and vertices. The methods it needs to maintain can be quite complex—for example, we need functions that can return the degree of any node, return the neighbors of a vertex, the maximum degree, and methods to determine whether a path exists from one vertex to another.

Based on different requirements, graphs naturally have many different data structure representations. One method that is satisfactory in both performance and functionality is the adjacency array. Store a vector<vector<int>> V, where V[i] represents the index array of neighbor vertices of the i-th vertex. For convenience in the following discussion, we adopt this method to represent the graph.

Undirected Graph Algorithms

DFS (Depth-First Search)

Depth-First Search (DFS) is a recursive algorithm that can be described by the following steps:

1. Choose a search starting point and mark it as visited.
2. Recursively visit all its unmarked neighbors.

The most classic application of DFS is to check whether a given graph is connected. This problem is equivalent to: for vertex u in graph G, does a path exist to another vertex v? These two problems are called the connectivity problem and the single-source path problem respectively; as mentioned above they are equivalent.

We can maintain a marked array of length equal to the number of vertices, marking vertices that have been visited. For the connectivity problem, several subproblems that can be solved with DFS:

1. Is the given graph connected: After DFS completes, check whether all entries in the marked array are marked; if yes return true, otherwise return false.
2. How many connected components does the given graph have: Until the marked array is fully marked, maintain count; each time the recursive call reaches the bottom, check whether the marked array is fully marked. If yes return count, otherwise count++.
3. Are vertices u and v in the same connected component: Start DFS from vertex u; if after DFS completes vertex v is marked as visited in the marked array, then they are in the same connected component.

Note that the third subproblem above is actually identical to the single-source path problem.

A DFS that performs no specific task is shown below:

In the implementation above, we only maintain the marked array but do not complete any task. If we want to solve subproblem 1 (whether the given graph is connected), we only need to check after DFS completes.

The abstract part ends here. When applied to real problems, we need to accurately identify the manifestations of graphs, edges, and vertices in various scenarios. The following are some problems from LeetCode that are lovely manifestations of DFS.

1. Number of Islands (LC200)

BFS (Breadth-First Search)

Connected Components

Shortest Path Algorithms

Dijkstra's Algorithm

References:

1. Algorithms (4th Edition), Robert Sedgewick, China Industry & Information Technology Publishing Group / People's Posts and Telecommunications Press, translated by Xie Luyun