Shulou(Shulou.com)06/01 Report--

1. Define

Connected component: in an undirected graph, it is a connected subgraph.

In the figure above, there are a total of four connected components. Vertices A, B, C and D constitute a connected component, vertex E constitutes a connected component, and vertex FMagi G and HMague I constitute two connected components respectively.

Strongly connected component: in a digraph, if there are as many vertices as possible in a subgraph, these vertices are accessible to each other, then these vertices become a strongly connected component.

There are three strongly connected components in the above figure, namely a, b, e and f, g and c, d, h.

two。 A method for solving connected components

For the connected component of an undirected graph, all vertices of the connected component can be traversed by a DFS starting from any vertex of the connected component. Therefore, the number of connected components of the entire graph should be equivalent to traversing the entire graph several times (outermost) DFS. All vertices traversed in a DFS belong to the same connected component.

Next, we will introduce the method of solving the strongly connected components of a digraph.

3. The basic principle of Kosaraju algorithm.

Let's use the simplest example to explain the Kosaraju algorithm.

Obviously, there are two strongly connected components in the above graph, namely, the strongly connected component An and the strongly connected component B, which are composed of vertex A0-A1-A2 and vertex B3-B4-B5 respectively. There are several vertices that can access each other in each connected component (here are all 3). There is no ring between the strongly connected component and the strongly connected component, otherwise these connected components should be regarded as a whole, that is, as the same strongly connected component.

Now we try to think whether we can solve the strongly connected component of a directed graph according to the idea of finding the connected component in the undirected graph. We assume that DFS starts from any vertex of strongly connected component B, then traversing the whole graph requires exactly two DFS, which is equal to the number of connected components, and the vertices of each DFS traversal happen to belong to the same connected component. However, if we start DFS from any vertex of the connected component A, we can't get the correct result, because we only need to DFS once to visit all the vertices. Therefore, we should not follow the natural order of vertex numbers. Or any other order, but should DFS in the order in which the vertices of the strongly connected components to be pointed are listed first In the above figure, the strongly connected component A points to the strongly connected component B. So, we follow

B3, B4, B5, A0, A1, A2

DFS in order to achieve our goal. But in fact, this order is so strict that we only need to make sure that at least one vertex of the strongly connected component being pointed is in front of all the vertices pointing to the connected component, such as

B3, A0, A1, A2, B4, B5

B3 ranks in front of all vertices of the strongly connected component A.

Now our key problem is how to get such a vertex order that meets the requirements. Kosaraju gives this solution: invert the original graph, and then start traversing the DFS from any node of the reverse graph, and the reverse order must meet our requirements.

The reverse traversal of DFS means that if the current vertex is not accessed, we first traverse all the other vertices connected to the current vertex and are not accessed, and then add the current vertex to the stack. Finally, the order from the top of the stack to the bottom of the stack is the vertex order we need.

The image above shows the reverse of the original image.

Let's make the first assumption now: suppose DFS starts at any node in the strongly connected component A. Then after the first DFS is completed, all the vertices of the stack are the vertices of the strongly connected component A, and after the second DFS, the top of the stack must be the vertex of the strongly connected component B. It ensures that the vertices of the ordered strongly connected component B from the top of the stack to the bottom of the stack are all in front of the vertex of the strongly connected component A.

Let's now make the second assumption: suppose DFS starts at any vertex in the strongly connected component B. Obviously, we only need to do one DFS to traverse the whole graph. Since it is an inverse subsequent traversal, then the starting vertex must be finally completed, so the vertex at the top of the stack must be the vertex in the strongly connected component B, which is obviously the result of the vertex ordering we want to get.

The simplest example above is used to illustrate the principle of the Kosaraju algorithm, which is still applicable when there are multiple strongly connected components and the connection is complex. You can give your own examples to prove it.

To sum up, no matter from which vertex, there are many strongly connected components in the graph, the order of vertices in the stack traversing in reverse must ensure that at least one vertex of the strongly connected component is in front of all the vertices pointing to the connected component. Therefore, our steps to solve the strongly connected components can be divided into two steps:

(1) invert the original image and perform inverse subsequent DFS traversal of the reverse graph from any vertex.

(2) DFS traversal is performed on the original graph according to the order of vertices in the stack in the inverse subsequent traversal, and all the vertices visited in a DFS traversal belong to the same strongly connected component.

4. Code implementation for solving connected components and strongly connected components

test data

ten

fifteen

0 1

0 4

1 0

1 8

2 1

2 4

2 7

3 4

4 3

5 0

5 6

7 9

7 4

8 5

9 2

Running result

Representation of a graph

0: 1 4

1: 0 8

2: 1 4 7

3: 4

4: 3

5: 0 6

6:

7: 9 4

8: 5

9: 2

Connected components: 4

A vertex that belongs to the same connected component as vertex 0

0 1 5 8

A vertex that belongs to the same connected component as vertex 3

3 4

A vertex that belongs to the same connected component as vertex 9

2 7 9

A vertex that belongs to the same connected component as vertex 6

six

ConnectedComponents includes the undirected graph to find the connected components and the implementation of Kosaraju algorithm.

Package datastruct;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.util.LinkedList;import java.util.List;import datastruct.Graph.Edge;public class ConnectedComponents {private boolean [] marked; / * is used to mark which (strongly) connected component each vertex belongs to. The (strongly) connected component of the same (strongly) connected component vertex has the same number value * / private int [] id. The number of private int count;// (strongly) connected components also indicates the number of (strongly) connected components private Graph g; public ConnectedComponents (Graph g) {this.g = g; marked = new boolean [g.V ()]; id = new int [g.V ()] If (g.isDirect ()) {/ / method for finding strongly connected components of a directed graph / / reverse order of a graph DFS, starting from vertex 0, you can start from any vertex LinkedList stack = g.reverse () .reversePostOrder (0); marked = new boolean [G.V ()] While (! stack.isEmpty ()) {int v = stack.pop (); if (! marked [v]) {dfs (v); count++ The connected component for of else {/ / undirected graph (int I = 0; I)

< g.V(); i++){ if(!marked[i]){ dfs(i); count++; } } } } private void dfs(int v){ if(!marked[v]){ marked[v] = true; id[v] = count; for(Edge e : g.adjEdge(v)){ int w = e.other(v); dfs(w); } } } public int count(){ return count; } //与顶点v属于同一连通分量的所有顶点 public List allConnected(int v){ LinkedList list = new LinkedList(); int k = id[v]; for(int i = 0; i < g.V(); i++){ if(id[i] == k){ list.add(i); } } return list; } public static void main(String[] args) throws FileNotFoundException{ File path = new File(System.getProperty("user.dir")).getParentFile(); File f = new File(path,"algs4-data/tinyDG2.txt"); FileReader fr = new FileReader(f); Graph graph = new Graph(fr, true, false); System.out.println("图的表示"); System.out.println(graph); ConnectedComponents cc = new ConnectedComponents(graph); System.out.println("连通分量数： " + cc.count()); System.out.println("\n"); System.out.println("和顶点 0 共属于同一个连通分量的顶点"); for(int i : cc.allConnected(0)){ System.out.printf("%-3d", i); } System.out.println("\n"); System.out.println("和顶点 3 共属于同一个连通分量的顶点"); for(int i : cc.allConnected(3)){ System.out.printf("%-3d", i); } System.out.println("\n"); System.out.println("和顶点 9 共属于同一个连通分量的顶点"); for(int i : cc.allConnected(9)){ System.out.printf("%-3d", i); } System.out.println("\n"); System.out.println("和顶点 6 共属于同一个连通分量的顶点"); for(int i : cc.allConnected(6)){ System.out.printf("%-3d", i); } System.out.println(); }} 图的临接表示，包含了很多实用的方法，但是此处主要使用通过原图构造它的反方向图和逆后序 package datastruct;import java.io.BufferedReader;import java.io.File;import java.io.FileNotFoundException;import java.io.FileReader;import java.io.PrintWriter;import java.io.Reader;import java.io.StringWriter;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Scanner;public class Graph{ private int v;//顶点数量 private int e;//边数量 private boolean isWeight; //时候是带权重的图 private boolean isDirect; //是否是有向图 private boolean hasCycle; //图中时候含有环 private LinkedList[] adj;//临接表 //图中边的表示 public static class Edge implements Comparable{ private final int from;//边起始顶点 private final int to;//边终结顶点 private final double w; //权值 public Edge(int from, int to, double w){ this.from = from; this.to = to; this.w = w; } //返回任意一个顶点 public int either(){ return from; } //返回另一个顶点 public int other(int v){ return v == this.from ? to : from; } //用于有向图 public int from(){ return from; } //用于有向图 public int to(){ return to; } public double weight(){ return w; } //边比较器，已权重为依据 @Override public int compareTo(Edge that) { if(this.w >

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.