图论（三）--深度优先搜索（DFS）

基于算法导论图算法-深度优先搜索

• 题目描述
• 问题分析
• 源代码
• 结果截图

题目描述

深度优先搜索（用递归和栈分别实现）：对图进行遍历，得到连通分支数，并求出每个顶点的发现时间和完成时间

问题分析

与广搜相同，每个顶点白色->灰色->黑色

伪代码

递归实现（栈实现伪代码未提供，可参见源代码）

源代码

void DFS(Graph G);//dfs图
void DFS_VISIT(Graph G, Vertex u);//从某个结点dfs递归实现
void DFS_visit_stack(Graph G, Vertex v);//深搜用栈实现
void print_path(Graph G, Vertex v);//打印一个点的深搜路径，沿着pred向上找
void print_path_everyPoint(Graph G);//打印每个顶点的深搜路径

图的顶点数据结构有所变化（添加发现时间和完成时间）

struct VertexRecord {
    Vertex pred;//先驱结点
    int in_degree;//入度 
    int out_degree;//出度 
    int color;//顶点状态
    int dist;//距离源点的距离
    int discover_time;//深搜发现时间
    int finish_time;//深搜时的结束时间
    List  adjto;//指向第一个邻接结点的指针
};

#include<stack>

void print_path(Graph G, Vertex v) {//打印一个点的深搜路径，沿着pred向上找
    if (G->vertices[v].pred != -1) {
        print_path(G, G->vertices[v].pred);
    }
    printf(" %d", v);
}
void print_path_everyPoint(Graph G) {//打印每个顶点的深搜路径
    for (int i = 0; i < G->vexnum; i++) {
        printf("顶点%d的深搜路径为：",i); 
        print_path(G, i);
        printf("\n");
    }
}

void print_time_dfs(Graph G) {//打印每个顶点的发现时间和结束时间 
    for (int i = 0; i < G->vexnum; i++) {
        printf("顶点%d发现时间:%d,结束时间为：%d", i, G->vertices[i].discover_time, G->vertices[i].finish_time);
        printf("\n");
    }
}

int Time;
//int count_finishTime_descreasing = VertexNum;
void DFS_VISIT(Graph G, Vertex u) {//递归实现深搜
    Time = Time + 1;
    G->vertices[u].discover_time = Time;
    //if (G->vertices[u].pred == -1) G->vertices[u].dist = 0;
    //else G->vertices[u].dist = G->vertices[G->vertices[u].pred].dist + 1;//权为1计算，此处为距离的计算
    G->vertices[u].color = 1;//gray
    PtrToNode ptr = G->vertices[u].adjto;
    while (ptr != NULL) {
        Vertex v = ptr->adjvex;
        if (G->vertices[v].color == 0) {
            G->vertices[v].pred = u;
            DFS_VISIT(G, v);
        }
        ptr = ptr->next;
    }
    G->vertices[u].color = 2;//black
    Time = Time + 1;
    G->vertices[u].finish_time = Time;

}

void DFS_visit_stack(Graph G, Vertex v) {//深搜用栈实现
    PtrToNode ptr;
    stack<int> S;
    S.push(v);
    //G->vertices[v].dist = 0;
    G->vertices[v].color = 1;//灰色
    G->vertices[v].discover_time = ++Time;
    printf("\n%d", v);
    while (!S.empty()) {
        Vertex u = S.top();
        ptr = G->vertices[u].adjto;
        while (ptr != NULL) {
            if (G->vertices[ptr->adjvex].color == 0) {
                S.push(ptr->adjvex);
                //G->vertices[ptr->adjvex].dist = G->vertices[u].dist + 1;//权为1计算，此处为距离的计算
                G->vertices[ptr->adjvex].color = 1;//灰色
                Time++;
                G->vertices[ptr->adjvex].discover_time = Time;
                G->vertices[ptr->adjvex].pred = u;
                printf(" %d", ptr->adjvex);
                break;
            }
            ptr = ptr->next;
        }
        if (S.top() == u) {
            G->vertices[u].color = 2;//黑色
            Time++;
            G->vertices[u].finish_time = Time;
            //finishTime_descreasing[--count_finishTime_descreasing] = u;
            S.pop();

        }

    }
    printf("\n");
}

void DFS(Graph G) {

    int count = 0;
    for (int i = 0; i < G->vexnum; i++) {
        G->vertices[i].color = 0;//白色
        G->vertices[i].pred = -1;
    }
    Time = 0;
    for (int i = 0; i < G->vexnum; i++) {
        if (G->vertices[i].color == 0) {
            //DFS_VISIT(G, i);
            DFS_visit_stack(G, i);
            count++;
        }
    }
    printf("共有%d个连通分量\n", count);
    print_path_everyPoint(G);//打印每个顶点的深搜路径 
    print_time_dfs(G);//打印每个顶点距离0的距离 
}
int main() {
    //有向图的随机生成（20个顶点，100左右的边，可以进行修改）
    //CreateRandomDirectGraph();
    //Graph G = CreateDirectGraph();

    //无向边的随机生成（20个顶点，50左右的边）
    CreateRandomUndirectGraph();
    Graph G = CreateUndirectGraph();
    printf("打印图结构：\n"); 
    print_graph(G);//打印图
    //printf("\n打印各顶点入度和出度：\n");
    //print_VertexDegree(G);//打印顶点度数
    //printf("\n打印每条边的权值：\n");
    //print_EdgeWeight(G);//打印边权

    //printf("\n下面是bfs:\n");
    //BFS(G, 0);

    printf("\n下面是dfs:");
    DFS(G);

    return 0;   
} 

结果截图