# 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;
}
}
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

for( int i = 0; i < n; i++) {
for(int j = 0; j < n; j++)
M[i][j] = 0;
}

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