Graph traversal - BFS, DFS

One 、 Depth-first search （Depth First Search,DFS）

The algorithm is similar to the preorder traversal of binary tree , The access operation is performed when a vertex is passed for the first time , And record that the vertex has been accessed . The specific steps are as follows ：

1. Set the pointer p, Point to the top v.
2. visit p Pointed vertex , And make p Points to a vertex that is adjacent to it and has not been accessed .
3. If p The pointed vertex exists , Then repeat the steps (2), Otherwise, carry out the steps (4).
4. Trace back to a vertex that has adjacent vertices and has not been visited in the order and direction just visited , And make p Point to this vertex . Then repeat the steps (2), Until all vertices are accessed .

Suppose there is a diagram as follows ：

The data format of adjacency table is expressed as ：

Assuming that the 0 Start traversing the vertices , Then the traversal node is ：

0 4 2 6 7
//  Other vertices from 0 I can't get to , Because the vertex 0 They are not accessible through directed edges .
//  Print other vertices if necessary , Just add a cycle .

Sample code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define MAX_NODE 20     //  The maximum number of vertices in a graph 

struct ArcNode          //  The table node adjacent to the linked list 
{
    int adjVex;                 // adjacent vertex  The vertex sequence number of the adjacent vertex 
    double weight;              //  The weight of the arc 
    struct ArcNode* nextNode;   //  Point to the next adjacent vertex 
};

struct AdjHead          //  Adjacent to the head node of the linked list 
{
    int data;                   //  Data represented by vertices , Use a number to represent 
    struct ArcNode* firstNode;  //  Point to the first adjacent vertex 
};
using AdjList = vector<AdjHead>;    //  Adjacency list 

struct Graph
{
    int vNum;           //  The number of vertices in a graph 
    AdjList adjList;
};

int visited[MAX_NODE] = {0};    //  Record whether the vertices in the graph have been accessed 

// Breadth First Search
void BFS(const Graph& g)
{
    int visited[MAX_NODE] = {0};             //  Record whether the vertices in the graph have been accessed 
    queue<int> q;                            //  Create a queue 
    for (int i = 0; i < g.vNum; i++) {
        if (visited[i] == 0) {               //  The vertices i Not visited 
            q.push(i);
            cout << i << " ";
            visited[i] = 1;                  //  The vertices i Mark as visited 

            while(!q.empty()) {              //  If the queue is not empty , Then continue to take the vertex for BFS
                int k = q.front();
                q.pop();
                ArcNode* n = g.adjList[k].firstNode;
                while(n != nullptr) {        //  Check all and vertices k The adjacency vertex of 
                    int j = n->adjVex;
                    if (visited[j] == 0) {   //  If adjacent vertices j Not visited , take j Join the queue 
                        q.push(j);
                        cout << j << " ";
                        visited[j] = 1;
                    }
                    n = n->nextNode;
                }
            }
        }
    }
}

int main()
{
    AdjList adjList;
    adjList.resize(MAX_NODE);
    ArcNode n1{4, 1.0, nullptr};
    ArcNode n2{6, 1.0, nullptr};
    ArcNode n3{0, 1.0, &n2};
    ArcNode n4{6, 1.0, nullptr};
    ArcNode n5{0, 1.0, &n4};
    ArcNode n6{1, 1.0, nullptr};
    ArcNode n7{7, 1.0, nullptr};
    ArcNode n8{2, 1.0, &n7};
    ArcNode n9{7, 1.0, nullptr};
    ArcNode n10{1, 1.0, &n9};
    ArcNode n11{6, 1.0, nullptr};
    adjList[0] = AdjHead{0, &n1};
    adjList[1] = AdjHead{1, &n3};
    adjList[2] = AdjHead{2, &n5};
    adjList[3] = AdjHead{3, &n6};
    adjList[4] = AdjHead{4, &n8};
    adjList[5] = AdjHead{5, &n10};
    adjList[7] = AdjHead{7, &n11};
    Graph g{8, move(adjList)};
    DFS(g, 0);
    //BFS(g);

    return 0;
}

Algorithm complexity

The process of depth first traversing a graph is essentially the process of finding its adjacent nodes for a vertex , The time it takes depends on the storage structure . When a graph is represented by an adjacency matrix , The time needed to find the adjacency of all vertices is O(n²). When the adjacency table is used as the storage structure , The time complexity of depth first search traversal graph is O(n+e).

Two 、 Breadth first search （Breadth First Search,BFS）

Breadth first search method is ： From a vertex in the graph v set out , During a visit to the v And then access v The adjacent points that have not been visited , Then access their adjacency points one by one from each of these adjacency points , And make The adjacent point of the vertex accessed first Precede The adjacent point of the vertex to be accessed later To be accessed , Until the adjacent points of all accessed vertices in the graph are accessed . If there are still unreachable vertices , Select another vertex in the graph that has not been accessed as the starting point , Repeat the process , Until all vertices in the graph are accessed .

Sample code

// Depth First Search
void DFS(const Graph& g, int i) {
    cout << i << " ";      //  The access number is i The summit of 
    visited[i] = 1;         //  The tag has been accessed 

    ArcNode* n = g.adjList[i].firstNode;     //  Take the top i The first adjacent vertex of 
    while (n != nullptr) {                   //  Check all and i A vertex adjacent to a vertex 
        int j = n->adjVex;
        if (visited[j] == 0) {               //  If the vertex j Not visited , From the vertex j Set out for DFS
            DFS(g, j);
        }
        n = n->nextNode;                     //  Continue to traverse the next adjacent vertex 
    }
}

The output is ：

0 4 2 7 6 1 3 5

Algorithm complexity

The process of traversing a graph is essentially the process of finding adjacent nodes through edges or arcs , because BFS And DFS The algorithm time complexity of traversing the graph is the same , The only difference is that the order of access to vertices is different .