Vomitting blood collates programmer to read list: github.com/silently952…

Wechat official account: Beta learning Java

In the previous part, we learned depth-first search, how to use depth-first search to find a path in a graph; In this article, we will continue to look at other application scenarios of depth-first search algorithms

Connected components

Finding all connected components from a graph is also an application scenario for depth-first search. What is a connected component? This definition has been mentioned in the previous article “How to Detect whether two people are friends in social Networks (Union-find Algorithm)”.

In this paper, the connectivity check implemented by Union-find algorithm is adopted. In this paper, we will use depth-first search to find all connected components in the graph

API definition of connected components

public class DepthFirstCC { public DepthFirstCC(Graph graph); public boolean connected(int v, int w); Public int count(); Public int id(int v); // The connected component of vertex v}Copy the code

API implementation of connected components

As before we need to mark vertices if we haven’t scanned them, so we still need to define a marked[] array

To figure out how many connected components there are in the graph, we need to define a variable, count

In order to judge whether two vertices are connected, we need to record the identity values corresponding to the connected vertices as the same value. When calling connected method, we directly take out the identity values of the two vertices and compare them. If they are the same, they are connected; otherwise, they are disconnected.

For this we use the count value, each vertex needs to store an id value, so we also need an IDS [] array.

public class DepthFirstCC { private boolean marked[]; private int count; private int[] ids; public DepthFirstCC(Graph graph) { this.marked = new boolean[graph.V()]; this.ids = new int[graph.V()]; for (int v = 0; v < graph.V(); v++) { if (! this.marked[v]) { dfs(graph, v); count++; } } } private void dfs(Graph graph, int v) { this.marked[v] = true; this.ids[v] = count; for (int w : graph.adj(v)) { if (! this.marked[w]) { dfs(graph, w); } } } public boolean connected(int v, int w) { return id(v) == id(w); } public int count() { return count; } public int id(int v) { return ids[v]; }}Copy the code

Unit testing

To construct such a graph, the total number of connected components should be 3

@Test public void test() { Graph graph = new Graph(10); graph.addEdge(0, 1); graph.addEdge(0, 2); graph.addEdge(0, 5); graph.addEdge(1, 3); graph.addEdge(2, 4); graph.addEdge(4, 3); graph.addEdge(5, 3); graph.addEdge(6, 7); graph.addEdge(8, 9); DepthFirstCC cc = new DepthFirstCC(graph); System. The out. Println (cc) connected (0, 5)); System. The out. Println (cc) connected (1, 2)); System.out.println(cc.count()); }Copy the code

Connectivity checking based on depth-first search is theoretically faster than the previous implementation of Union-find, because versions of depth-first search are guaranteed to be completed in constant time, whereas union-find is not.

However, union-find has its own advantages: it does not need to construct and represent a graph completely, and more importantly, it adds nodes dynamically.

Check for loops in an undirected graph

To reduce the complexity of implementation, we assume that there are no self-loops and parallel edges in the graph.

If there is a ring starting from vertex V, indicating that the adjacent vertex of a vertex in the connected component starting from vertex V is V, then vertex V must be encountered again in the search process

The idea of implementation:

  1. Marks each vertex that has been searched
  2. When a marked vertex is encountered, it indicates that there is a ring in the graph.
  3. Since the graph is undirected, if V and W are connected, then the adjacency list of vertex V has W, and the adjacency list of vertex W also has V, but they do not form a ring, so we need to exclude this case.
public class Cycle { private boolean marked[]; private boolean hashCycle; public Cycle(Graph graph) { this.marked = new boolean[graph.V()]; for (int s = 0; s < graph.V(); s++) { if (! this.marked[s]) { dfs(graph, s, s); } } } private void dfs(Graph graph, int v, int pV) { this.marked[v] = true; for (int w : graph.adj(v)) { if (! this.marked[w]) { this.dfs(graph, w, v); } else if (w ! = pV) { this.hashCycle = true; return; } } } public boolean hasCycle() { return hashCycle; }}Copy the code

The parameter v of method DFS represents the vertices to be searched, and pV represents the vertices reaching V. Therefore, if a vertex in v’s adjacency list has been marked and this vertex is not equal to the vertex reaching V, then the graph has a ring

Checks whether an undirected graph is a binary graph

What is a binary graph? The vertices connected by each edge of the graph belong to a different part; The diagram below:

The red node represents one set, and the white node is another set. The two vertices connected by each edge belong to different sets.

A practical example is easy to understand, the relationship between movie and actor, movie as a vertex, actor as a vertex, movie and movie directly have no edges, actor and actor directly have no edges, this is a binary graph.

public class TwoColorGraph { private boolean twoColor = true; private boolean[] marked; private boolean[] color; public TwoColorGraph(Graph graph) { this.marked = new boolean[graph.V()]; this.color = new boolean[graph.V()]; for (int v = 0; v < graph.V(); v++) { if (! this.marked[v]) { dfs(graph, v); } } } private void dfs(Graph graph, int v) { this.marked[v] = true; for (int w : graph.adj(v)) { if (! this.marked[w]) { this.color[w] = ! this.color[v]; dfs(graph, w); } else if (this.color[w] == this.color[v]) { this.twoColor = false; return; } } } public boolean isTwoColor() { return twoColor; }}Copy the code

All the source code has been put into github repository: github.com/silently952…

Finally (pay attention, don’t get lost)

There may be more or less deficiencies and mistakes in the article, suggestions or opinions are welcome to comment and exchange.

Finally, writing is not easy, please do not white whoring I yo, I hope friends can point comment attention to three even, because these are all the power source I share 🙏