深度优先遍历 (Depth First Search)，也有称深度优先搜索，简称为 DFS
图的深度优先遍历类似树的前序遍历

无向图的深度优先搜索

#include<iostream>
using namespace std;
#define len 100
int visited[len];

struct fact{
    char node[len];     // 定点集合
    int edge[len][len]; // 邻接矩阵
    int n;              // 节点个数 
    int e;              // 边的个数
};

// 返回顶点下标
int get_Node_Index(struct fact *g, char number){
    for(int i=0; i < g->n; i++){
        if(number == g -> node[i]){
            return i;
        }
    }
    return -1; //这句话永远不会执行的
}

void DFS(struct fact *g, int number){
    cout<<"深度优先遍历序列为: "<<g->node[number]<<endl;
    visited[number] = 1;
    for(int j=0; j < g->n; j++){
        if(g->edge[number][j] == 1 && !visited[j]){
            DFS(g, j);
        }
    }
}

int main(){
    struct fact *graph;

    graph = new struct fact; // 为指针分配内存空间
    graph -> n = 7;
    graph -> e = 7;
    // cout<<graph->n<<" "<<graph->e<<endl;

    // 设置节点为默认数值
    string nodes = "ABCDEFG";
    // 输入节点
    for(int i=0; i < graph->n; i++){
        graph -> node[i] = nodes[i];
    }

    // 设置边为默认值
    char edges[][2] = {
        {'A', 'C'},
        {'A', 'D'},
        {'A', 'F'},
        {'C', 'B'},
        {'C', 'D'},
        {'F', 'G'},
        {'G', 'E'}
    };
    // 边初始化为０
    for(int i=0; i < graph->n; i++){
        for(int j=0; j < graph->n; j++){
            graph -> edge[i][j] = 0;
        }
    }
    for(int i=0; i < graph->e; i++){
        // cout<<edges[i][0]<<" "<<edges[i][1]<<endl;
        int start = get_Node_Index(graph, edges[i][0]);
        int end = get_Node_Index(graph, edges[i][1]);
        graph -> edge[start][end] = 1;
        graph -> edge[end][start] = 1; // 无向图的建立
    }

    // 初始化 visited 数组
    for(int i=0; i < graph->n; i++){
        visited[i] = 0;
    }

    // 开始深度优先遍历
    for(int i=0; i < graph->n; i++){
        if(!visited[i]){
            DFS(graph, i);
        }
    }

    return 0;
}

有向图的深度优先搜索

#include<iostream>
using namespace std;
#define len 100
int visited[len];

struct fact{
    char node[len];     // 定点集合
    int edge[len][len]; // 邻接矩阵
    int n;              // 节点个数 
    int e;              // 边的个数
};

// 返回顶点下标
int get_Node_Index(struct fact *g, char number){
    for(int i=0; i < g->n; i++){
        if(number == g -> node[i]){
            return i;
        }
    }
    return -1; //这句话永远不会执行的
}

void DFS(struct fact *g, int number){
    cout<<"深度优先遍历序列为: "<<g->node[number]<<endl;
    visited[number] = 1;
    for(int j=0; j < g->n; j++){
        if(g->edge[number][j] == 1 && !visited[j]){
            DFS(g, j);
        }
    }
}

int main(){
    struct fact *graph;

    graph = new struct fact; // 为指针分配内存空间
    graph -> n = 7;
    graph -> e = 9;

    // 设置节点为默认数值
    string nodes = "ABCDEFG";
    // 输入节点
    for(int i=0; i < graph->n; i++){
        graph -> node[i] = nodes[i];
    }

    char edges[][2] = {
        {'A', 'B'}, 
        {'B', 'C'}, 
        {'B', 'E'}, 
        {'B', 'F'}, 
        {'C', 'E'}, 
        {'D', 'C'}, 
        {'E', 'B'}, 
        {'E', 'D'}, 
        {'F', 'G'}
    }; 
    // 边初始化为０
    for(int i=0; i < graph->n; i++){
        for(int j=0; j < graph->n; j++){
            graph -> edge[i][j] = 0;
        }
    }
    for(int i=0; i < graph->e; i++){
        // cout<<edges[i][0]<<" "<<edges[i][1]<<endl;
        int start = get_Node_Index(graph, edges[i][0]);
        int end = get_Node_Index(graph, edges[i][1]);
        graph -> edge[start][end] = 1;
    }

    // 初始化 visited 数组
    for(int i=0; i < graph->n; i++){
        visited[i] = 0;
    }

    // 开始深度优先遍历
    for(int i=0; i < graph->n; i++){
        if(!visited[i]){
            DFS(graph, i);
        }
    }

    return 0;
}

小结

• 图的遍历之 深度优先搜索和广度优先搜索
• 注意观察有向图和无向图在构建边时的不同，边的构建是主要区别

邻接矩阵方式

邻接表方式