How to use depth-first search algorithm in C++

How to use the depth-first search algorithm in C

The depth-first search (DFS) algorithm is an algorithm for traversing or searching a graph or tree, which starts from Start with a root node and explore the branches of the graph as deeply as possible until you can go no further, then go back and explore other branches. DFS is a very useful solution to many problems, such as graph connectivity detection, finding graph cycles, generating and printing out all possible paths, etc.

This article will introduce how to implement the depth-first search algorithm in C and use specific code examples to illustrate.

The basic idea of ​​depth-first search is to use recursion or stack to save the nodes that need to be traversed. The following is a sample code of the DFS algorithm for a graph represented by an adjacency matrix:

#include <iostream>
#include <stack>

using namespace std;

const int MAX = 100;
bool visited[MAX];
int graph[MAX][MAX];
int numVertices;

void dfs(int start) {
    stack<int> s;
    visited[start] = true;
    cout << start << " ";

    s.push(start);

    while (!s.empty()) {
        int current = s.top();
        s.pop();

        for (int i = 0; i < numVertices; i++) {
            if (graph[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                cout << i << " ";
                s.push(i);
            }
        }
    }
}

int main() {
    int numEdges, start;

    cout << "Enter the number of vertices: ";
    cin >> numVertices;
    cout << "Enter the number of edges: ";
    cin >> numEdges;

    for (int i = 0; i < numEdges; i++) {
        int u, v;
        cout << "Enter edge (u, v): ";
        cin >> u >> v;
        graph[u][v] = 1;
        graph[v][u] = 1; // Assuming undirected graph
    }

    cout << "Enter the starting vertex for DFS: ";
    cin >> start;

    dfs(start);

    return 0;
}

In the above sample code, we first define a global two-dimensional adjacency matrix graph, andvisitedThe array is used to mark whether the node has been visited. Then we defined a dfs() function to implement depth-first search. This function uses a stack to save the nodes that need to be traversed. First, the starting node is pushed onto the stack and marked as visited. Then it starts to enter the loop, taking out a node from the stack each time and traversing the adjacent nodes of the node. If the adjacent node has not been visited, it is pushed into the stack and marked as visited. This process will continue until the stack is empty. Finally, we use the main() function to read the graph information and call the dfs() function to perform a depth-first search.

The above code example is just a simple application of the depth-first search algorithm. In fact, the algorithm can also be optimized through some techniques, such as using recursive implementation, using color marking, etc.

The depth-first search algorithm is very effective in solving various graph theory problems and is widely used in practical applications. Proficiency in the implementation of the DFS algorithm is very helpful for understanding graph theory and solving related problems.

Summary:

This article introduces how to implement the depth-first search algorithm in C and gives specific code examples. The depth-first search algorithm is an important graph theory algorithm that can solve many graph-related problems by traversing or searching branches of the graph. Mastering the DFS algorithm is very helpful for understanding graph theory and solving related problems.

The above is the detailed content of How to use depth-first search algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!