Graph Theory 03-[Unweighted and Undirected]-Depth-first DFS traversal of graphs-path problem/detection cycle/bipartite graph

Article directory

  • 1. Code warehouse
  • 2. Single source path
    • 2.1 Ideas
    • 2.2 Main code
  • 3. All point-pair paths
    • 3.1 Ideas
    • 3.2 Main code
  • 4. Optimization of path problem-end recursion early
    • 4.1 Ideas
    • 4.2 Main code
  • 5. Detection loop
    • 5.1 Ideas
    • 5.2 Main code
  • 6. Bipartite graph
    • 6.1 Ideas
    • 6.2 Main code
      • 6.2.1 Traverse each connected component
      • 6.2.2 Recursively determine whether the colors of two adjacent points are consistent

1. Code warehouse

https://github.com/Chufeng-Jiang/Graph-Theory

2. Single source path

2.1 Idea

  1. Construct visited array and pre array
    1.1 The visited array records whether the current node has been visited
    You can also not use the visited array. The pre array is all initialized to -1. The value of the pre array corresponding to the connected vertices is the previous node. The values of -1 in the pre array are all disconnected vertices.
    1.2 The pre array records the previous node of the current node
  2. Use the pre array to push back the end point back to the source point and record
  3. Output the path from the end point to the origin in reverse order

2.2 Main code

 public SingleSourcePath(Graph G, int s){<!-- --> //Single source path, the source s must be passed in, and only the vertices connected to s will be considered, and those that are not connected will not be considered

        G.validateVertex(s);

        this.G = G;
        this.s = s;
        visited = new boolean[G.V()];
        pre = new int[G.V()];

        dfs(s, s);
    }

    private void dfs(int v, int parent){<!-- --> //Parameter one: current vertex; Parameter two: previous vertex

        visited[v] = true;
        pre[v] = parent;

        for(int w: G.adj(v)) //All vertices adjacent to v, equivalent to v being the source, traverse all points adjacent to the current vertex
            if(!visited[w])
                dfs(w, v); //(vertex, source)
    }
    
     public Iterable<Integer> path(int t){<!-- --> //The path from source to t

ArrayList<Integer> res = new ArrayList<Integer>();
if(!isConnectedTo(t)) return res;
int cur = t; // Find back from t
\t     
while(cur != s){<!-- -->
res.add(cur); //Add the current node (the source is not included in the loop)
cur = pre[cur]; //The value of pre[cur] is the previous node of cur
}
\t     
res.add(s); //Add source
Collections.reverse(res);
return res;
 }

3. All point-pair paths

3.1 Idea

Traverse all vertices and create a single-source path array for each point.

3.2 Main code

public AllPairsPath(Graph G){<!-- -->
    this.G = G;
    paths = new SingleSourcePath[G.V()];
    for(int v = 0; v < G.V(); v + + )
        paths[v] = new SingleSourcePath(G, v);
}

4. Optimization of path problem – ending recursion early

4.1 Idea

When filling the visited and pre arrays, if the target node is encountered, it will end directly. The remaining nodes are not processed.

if(v == t) return true; //Program exit, when reaching the t vertex, return true to end the recursion in advance, instead of just returning return

4.2 Main code

 private boolean dfs(int v, int parent){<!-- -->

        visited[v] = true;
        pre[v] = parent;

        if(v == t) return true; //Program exit, when reaching the t vertex, return true to end the recursion in advance, instead of just returning return

        for(int w: G.adj(v)) //Traverse the vertices adjacent to v
            if(!visited[w]) //If the adjacent vertex has not been visited
                if(dfs(w, v)) //Recursively traverse adjacent vertices, if v==t is reached, the value is true
                    return true; //Return true early

        return false; // If you cannot reach t after one turn, you can return false
    }

5. Detection ring

5.1 Idea

Starting from a certain point v, we find point w, w has been visited, and w is not the previous node of v

5.2 Main code

public CycleDetection(Graph G){<!-- -->
    this.G = G;
    visited = new boolean[G.V()];

    //To perform ring detection on all connected components
    for(int v = 0; v < G.V(); v + + )
        if(!visited[v]) //If not visited
            if(dfs(v, v)){<!-- --> //Perform deep search. If the deep search result is true, it means there is a loop, then enter the loop break
                hasCycle = true;
                break;
            }
}

    
private boolean dfs(int v, int parent){<!-- -->
    visited[v] = true;

    for(int w: G.adj(v))
        if(!visited[w]){<!-- --> //case1: if w has not been visited
            if(dfs(w, v)) //If dfs returns true, it means there is a cycle. Because dfs has a loop, it will return true. Then enter the if selection statement and return true to end early.
                return true;
        }
        else if(w != parent) // case2: Starting from v, w is found, w has been visited, and w is not the previous node of v
            return true; // The ring is found at this time

    //In other cases, if no ring is found after searching for a circle, return false
    return false;
}

6. Bipartite graph

6.1 Idea

Bipartite graphs can distinguish vertices through the coloring process.
[-1: The vertices have not been dyed yet]
[0:a color]
[1:Another color]

6.2 Main code

6.2.1 Traverse each connected component

  1. dfs(v, 0) returns true, which means that the colors of the two connected points are different, and there is no conflict yet;
  2. dfs(v, 0) returns false, which means that the two connected points have the same color, which does not meet the definition of a bipartite graph, so enter the if statement block, set isBipartite = false; and end the loop early.
for(int v = 0; v < G.V(); v + + )
    if(!visited[v]) //If not visited
    // At the beginning, dye v to 0 color uniformly. If dfs returns false, enter the following structure, otherwise jump out of execution v + +
        if(!dfs(v, 0)){<!-- -->
            isBipartite = false; // If the detection error occurs, set it to false
            break; // Subsequent loops do not need to be performed
        }

6.2.2 Recursively determine whether the colors of two adjacent points are consistent

private boolean dfs(int v, int color){<!-- --> //Parameter one: vertex Parameter two: color
    visited[v] = true;
    colors[v] = color;

    //Determine the color of adjacent vertices w in turn
    for(int w: G.adj(v))
        if(!visited[w]){<!-- --> //If w has not been visited, enter judgment
            if(!dfs(w, 1 - color)) //If the color of v is 0, then the color of w should be 1. If the color of v is 1, then the color of w should be 0.
                return false; //If two adjacent vertices have the same color, then it is not a bipartite graph.
        }
        else if(colors[w] == colors[v]) //If two adjacent vertices have the same color, then it is not a bipartite graph
            return false;

        return true;
}