欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

图的深度优先搜索dfs

程序员文章站 2022-06-22 21:49:53
图的深度优先搜索: 1.将最初访问的顶点压入栈; 2.只要栈中仍有顶点,就循环进行下述操作: (1)访问栈顶部的顶点u; (2)从当前访问的顶点u 移动至顶点v 时,将v 压入栈。如果当前顶点u 不存在未访问的相邻矩阵,则将u 从栈中删除; 主要的几个变量: color[n] 用WHITE、GRAY ......

 图的深度优先搜索:

1.将最初访问的顶点压入栈;

2.只要栈中仍有顶点,就循环进行下述操作:

(1)访问栈顶部的顶点u;

(2)从当前访问的顶点u 移动至顶点v 时,将v 压入栈。如果当前顶点u 不存在未访问的相邻矩阵,则将u 从栈中删除;

 

主要的几个变量:

color[n] 用white、gray、black 中的一个来表示顶点i 的访问状态
m[n][n] 邻接矩阵, 如果存在顶点i 到顶点j 的边,则m[i][j]为true
stack s

栈, 暂存访问过程中的顶点

 

 

 

 

 

其中color 数组中, 白色代表“未访问的顶点”, 灰色代表“访问过的顶点”(虽然被访问过了,但仍然可能留有通往未访问顶点的边), 黑色代表”访问结束的顶点”;

 

有俩种方法实现深度优先遍历

(1)用递归实现的深度优先搜索

#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]表示该顶点访问与否,d[n]表示该顶点的发现时刻 ,f[n]表示该顶点的结束时刻 ,tt表示时间 


//用递归函数实现的深度优先搜索 
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;//访问结束 
}

void dfs() {
    int u;
    //初始化 
    for(u = 0; u < n; u++)    color[u] = white;
    tt = 0; 
    
    //以未访问的u为起点进行深度优先搜索
    for(u = 0; u < n; u++) {
        if(color[u] == white)
            dfs_visit(u);
    } 
    
    //输出 
    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);
    //初始化 
    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)用栈实现的深度优先搜索

 

#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]表示该顶点访问与否,d[n]表示该顶点的发现时刻 ,f[n]表示该顶点的结束时刻 
int nt[n];//记录每个顶点的邻接顶点偏移量,eg:顶点0有俩个顶点1,2;现已经访问过1了,那么, nt[u] = 1; 下次直接访问2 

//按编号顺序获取与u相邻的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() {
    //初始化
    for( int i = 0; i < n; i++) {
        color[i] = white;
        nt[i] = 0;
    } 
    //设置时间 
    tt = 0;
    
    //以未访问的u为起点进行深度优先搜索,设置循环的目的应该是防止该图不是连通图 
    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; //顶点数 
     
    //邻接矩阵置零 
    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;//输入顶点和顶点的度
        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
*/