Algorithms -- Decompositions of Graph
How to express graph
- Adjacency matrix
- Adjacency list
If the number of edges or |E| is close to the upper limit, we call the graph dense. On the contrary, if |E| is close to |V| , it is sparse.
So |E| is always the crucial factor when selecting the right algorithm.
Depth-First Search
Exploring Mazes
The problem is what parts of the graph are reachable from a given vertex?
procedure explore(G, v){
// Explore from vertex v in graph G
visited(v) = true;
previsit(v);
for each edge (v, u) in G:
if not visited(u): explore(G, u);
postvisit(v);
What is DFS?
procedure dfs(G){
for all v in V:
visited(v) = false;
for all v in V:
if not visited(v):
explore(G, v);
}
Using DFS, we will get connected component
And to define:
procedure previsit(v) ccnum[v] =cc
And cc will increase every time DFS calls explore;
DAG: Directed acyclic graph
There are some properties:
- Directed graph has a cycle iff. its DFS reveals a back-edge
- In DAG, every edge leads to a vertex with a lower POST number
- DAG has at least one source and at least one sink.
How to linearize the DAG?
- Find a source, output it and delete it
- Repeat until the graph is empty.
Strongly Connected Component
First, how to define connectivity?
Two nodes u and v of a directed graph are connected if there is a path from u to b and a reversed one
And a more intriguing one: Every directed graph is a dag of its strongly connected components.
An efficient algorithm
Property One: If the explore subroutine is started at node u, then it will terminate precisely when all nodes reachable from u have been visited.
Property Two: The node that receives the highest post number in a DFS must lie in a source strongly connected component.
Property Three: If C and C' are strongly connected components, and there is an edge from a node in C to a node in C', then the highest post number in C is bigger than the highest post number in C'