Graph theory brush questions

1. The range of motion of the robot
2. Path in matrix
3. Image rendering
4. Swimming in a rising pool

1971. Find out if there is a path in the graph

Try to catch up with the original question Address

Difficulty and label

Simple difficulty

• Depth-first traversal
• Breadth first traversal
• And find

Title Description

There is one with n Vertex two-way chart , Where each vertex is marked from 0 To n - 1（ contain 0 and n - 1）. The edges in the graph are represented by a two-dimensional array of integers edges Express , among edges[i] = [ui, vi] It means a vertex ui And vertex vi Two way edges between . Each vertex pair consists of One at most Edge connection , And no vertex has an edge connected to itself .

Please determine whether there is a vertex start Start , To the top end The end of the Effective path .

Here's your array edges And integer n、start and end, If from start To end There is Effective path , Then return to true, Otherwise return to false.

Example 1

 Input ：n = 3, edges = [[0,1],[1,2],[2,0]], start = 0, end = 2
 Output ：true
 explain ： Existence by vertex  0  To the top  2  The path of :
- 0 → 1 → 2 
- 0 → 2

Example 2

 Input ：n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5
 Output ：false
 explain ： There are no vertices  0  To the top  5  The path of .

• 1 <= n <= 2 * 10^5
• 0 <= edges.length <= 2 * 10^5
• edges[i].length == 2
• 0 <= ui, vi <= n - 1
• ui != vi
• 0 <= start, end <= n - 1
• There are no two-way edges
• There is no edge pointing to the vertex itself

Topic analysis

It's easier to understand , Without adding some fancy scene descriptions . It's similar to the questions I did before, such as 778. Swimming in a rising pool The difference is that the structure of the graph needs to be built by itself , Given are all edges .

So first build the structure of the graph, and then traverse to find the answer .

In order to be more intuitive, I drew the following pictures ：

What is given is n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], So when constructing this graph, it can be expressed as multiple groups of vectors , The index of each set of vectors represents the starting point , The elements in the vector are represented as the elements reachable from this starting point , As shown in the figure ：

Then start from the starting point X Start , The depth traversal rules are not very different from those before . The specific process can be summarized as :

Looking for a starting point X The corresponding neighbor vector S, Traverse S Each of them Never been interviewed The elements of W, If W == The goal is Y, Then the return true, Otherwise, continue to visit W Neighbors of , Repeat the whole step .

Code implementation

class Solution {
    
public:
    /** *  Initialize all paths , According to the matrix given in the title , Into sets of vectors . */
    void initPath(const vector<vector<int>>& edges,
                  vector<vector<int>>& paths) {
    
        for (int i=0; i<edges.size(); i++) {
    
             int source = edges[i][0];
             int destination = edges[i][1];
             //  Undirected graph , Both directions should be recorded 
             paths[source].push_back(destination);
             paths[destination].push_back(source);
        }
    }

    /** *  Depth traversal , Until all points are accessed or paths from the starting point are accessed  */
    bool dfs(vector<vector<int>>& paths, 
             vector<bool>& visited, 
             int source,
             int destination) {
    
        //  The tag has been accessed 
        visited[source] = true;
        //  Reach your destination 
        if (source == destination) {
    
            return true;
        }
        //  Traverse source  All reachable neighbors as a starting point 
        for (int i=0; i<paths[source].size(); i++) {
    
            int newSource = paths[source][i];
            //  If this point has not been visited , Then continue to look for its neighbors .
            if (!visited[newSource] && 
                dfs(paths, visited, newSource, destination)) {
    
                return true;
            }
        }
        return false;
    }

    bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
    
        
        vector<vector<int>> paths(n);
        vector<bool> visited(n, false);
        
        initPath(edges, paths);
        return dfs(paths, visited, source, destination);
    }
};

The storage structure of the graph should belong to the adjacency table type , Therefore, the time complexity is closely related to the number of edges , If the number of edges is $e$, The number of points is $n$.

• Time complexity ：$O(n+e)$;
• Spatial complexity ：$O(n\times e)$, namely $paths$ Space occupied by variables .

summary

The topic is simple but it is not so easy to do , Need to think more , Look back .

Smileyan
2022.3.30 0:00