Graph depth first search dfs

Depth-first search for diagrams:

1. Push the originally visited vertex on the stack;

2. As long as there are still vertices in the stack, do the following for the loop:

(1) access vertex u at the top of the stack;

(2) when moving from the currently visited vertex u to the vertex v, push V onto the stack.If the current vertex u does not have an inaccessible adjacent matrix, u is removed from the stack.

 

The main variables are:

color[n] Use one of WHITE, GRAY, BLACK to represent the access state of vertex i
M[n][n] Adjacency matrix, M[i][j] is true if there is an edge from vertex i to vertex J
Stack S

Stack, vertex of temporary access

 

 

 

 

 

In the color array, white represents the "unvisited vertex", gray represents the "visited vertex" (although visited, there may still be an edge leading to the unvisited vertex), and black represents the end of the visited vertex;

 

There are two ways to achieve depth-first traversal

(1) Depth-first search implemented recursively

#include<stdio.h>

#define N 100
#define WHITE 0
#define GRAY 1
#define BLACK 2
 
int n, M[N][N];
int color[N], d[N], f[N], tt;//color[n]Indicates whether the vertex is accessed or not, d[n]Represents the time at which the vertex was discovered. f[n]Represents the end time of this vertex ,tt Represent time 


//Depth-first search using recursive functions 
void dfs_visit(int u) {
    int v;
    color[u] = GRAY;
    d[u] = ++tt;
    for(v = 0; v < n; v++) {
        if(M[u][v] == 0)    continue;
        if(color[v] == WHITE)
            dfs_visit(v);
    }
    color[u] = BLACK;
    f[u] = ++tt;//End of visit 
}

void dfs() {
    int u;
    //Initialization 
    for(u = 0; u < n; u++)    color[u] = WHITE;
    tt = 0; 
    
    //As not accessed u Deep-first search for starting point
    for(u = 0; u < n; u++) {
        if(color[u] == WHITE)
            dfs_visit(u);
    } 
    
    //output 
    for(u = 0; u < n; u++) {
        printf("%d %d %d\n", u+1, d[u], f[u]); 
    }
}

int main() {
    int u, v, k, i, j;
    
    scanf("%d", &n);
    //Initialization 
    for(i = 0; i < n; i++) {
        for(j = 0; j < n; j++) {
            M[i][j] = 0;
        }
    }
    //Input data, construct adjacency matrix 
    for(i = 0; i < n; i++) {
        scanf("%d %d", &u, &k);
        u--;
        for(j = 0; j < k; j++) {
            scanf("%d", &v);
            v--;
            M[u][v] = 1;
        }
    }
    
    dfs();
    
    return 0;
}

/*
6
1 2 2 3
2 2 3 4 
3 1 5
4 1 6
5 1 6
6 0
*/

 

 

 

(2) Depth-first search with stack

 

#include<iostream>
#include<stack> 
using namespace std;

static const int N = 100; 
static const int WHITE = 0;
static const int GRAY = 1;
static const int BLACK = 2;

int n, M[N][N];
int color[N], d[N], f[N], tt;//color[n]Indicates whether the vertex is accessed or not, d[n]Represents the time at which the vertex was discovered. f[n]Represents the end time of this vertex 
int nt[N];//Record the offset of adjacent vertices for each vertex. eg: Vertex 0 has two vertices 1,2; now that you have visited 1, nt[u] = 1; Next Direct Access 2 

//Get and in numbered order u Adjacent v
int next(int u) {
    for(int v = nt[u]; v < n; v++) {
        nt[u] = v + 1;
        if(M[u][v])    return v;
    }
    return -1;
}


void dfs_visit(int r) {
    for(int i = 0; i < n; i++)    nt[i] = 0;
    
    stack <int> S;
    S.push(r);
    color[r] = GRAY;
    d[r] = ++tt;
    
    while( !S.empty() ) {
        int u = S.top();
        int v = next(u);
        if(v != -1) {
            if(color[v] == WHITE) {
                color[v] = GRAY;
                d[v] = ++tt;
                S.push(v);
            }
        }
        else {
            S.pop();
            color[u] = BLACK;
            f[u] = ++tt;
        }
    }
}

void dfs() {
    //Initialization
    for( int i = 0; i < n; i++) {
        color[i] = WHITE;
        nt[i] = 0;
    } 
    //Set time 
    tt = 0;
    
    //As not accessed u For a depth-first search of the starting point, the loop should be set to prevent the graph from being connected 
    for(int u = 0; u < n; u++) {
        if(color[u] == WHITE)    dfs_visit(u);
    }
    
    for(int i = 0; i < n; i++) {
        cout << i+1 << " " << d[i] << " " << f[i] << endl;
    }
}

int main() {
    int u, k, v;
    cin >> n; //Number of vertices 
     
    //Adjacency matrix zeroing 
    for( int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) 
            M[i][j] = 0;
    }
    
    //Create adjacency matrix 
    for(int i = 0; i < n; i++) {
        cin >> u >> k;//Input vertices and degrees of vertices
        u--;
        for(int j = 0; j < k; j++) {
            cin >> v;
            v--;
            M[u][v] = 1;
        } 
    }
    
    dfs();
    
    return 0;
}

/*
6
1 2 2 3
2 2 3 4 
3 1 5
4 1 6
5 1 6
6 0
*/ 

Tags: C

Posted on Sun, 05 Apr 2020 21:39:33 -0700 by kristinac