图的遍历算法之深度优先遍历（DFS）(C++)

图的深度优先遍历思想是：

从图中某结点出发，访问其某一相邻结点，再访问该结点的相邻结点，直至访问完所有的结点。

形象的比喻就是：一条路走到头，回头再走没走过的路。

可见，深度优先遍历是一种递归思想；

需要注意的是：

对于图的邻接矩阵存储和邻接表存储，深度优先遍历输出的次序有有一定去别的。

对于邻接矩阵而言，DFS和BFS得到的序列是唯一的；

对于邻接表而言，DFS和BFS输入的序列不同，得到的输出序列也不相同。

深度优先遍历的核心算法 ：

void DFS(GraAdList G, int v) {
    EdgeNode* p;
    int j;
    cout << G.AdList[v].data << " ";
    visited[v] = 1;
    p = G.AdList[v].first;
    while (p)
    {
        j = p->adjvex;
        if (visited[j] == 0)
        {
            DFS(G, j);
        }
        p = p->next;
    }
}
void DFS(GraAdList G)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (visited[i] == 0)
        {
            DFS(G, i);
        }
    }
}

完整代码实现：

#include<iostream>
using namespace std;
#define MAX 6
int visited[MAX];
int D[MAX] = { 9999 };
typedef struct EdgeNode {
    int adjvex;
    EdgeNode* next;
};
typedef struct VexNode {
    char data;
    EdgeNode* first;
};
typedef struct GraAdList {
    VexNode AdList[MAX];
    int vexnum;
    int edgenum;
};
//创建邻接矩
void Creat(GraAdList& G) {
    int i, j, k;
    EdgeNode* e = NULL;
    EdgeNode* q = NULL;
    cout << "请输入顶点数和边数： " << endl;
    cin >> G.vexnum >> G.edgenum;
    cout << "请输入顶点信息" << endl;
    for (k = 0; k < G.vexnum; k++)
    {
        cin >> G.AdList[k].data;
        G.AdList[k].first = NULL;
    }
    for (k = 0; k < G.edgenum; k++)
    {
        cout << "请输入边(vi,vj)的下标i,j： " << endl;
        cin >> i >> j;
        e = new EdgeNode;
        e->adjvex = j;
        e->next = G.AdList[i].first;
        G.AdList[i].first = e;
    }
}
void myprint(GraAdList G) {
    cout << endl << "邻接表: " << endl;
    EdgeNode* p;
    for (int i = 0; i < G.vexnum; i++)
    {
        cout << G.AdList[i].data << ": ";
        for (p = G.AdList[i].first; p; p = p->next)
        {
            cout << p->adjvex << " ";
        }
        cout << endl;
    }
}
void DFS(GraAdList G, int v) {
    EdgeNode* p;
    int j;
    cout << G.AdList[v].data << " ";
    visited[v] = 1;
    p = G.AdList[v].first;
    while (p)
    {
        j = p->adjvex;
        if (visited[j] == 0)
        {
            DFS(G, j);
        }
        p = p->next;
    }
}
void DFS(GraAdList G)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (visited[i] == 0)
        {
            DFS(G, i);
        }
    }
}
int main() {
    GraAdList G;
    Creat(G);
    myprint(G);
    for (int i = 0; i < G.vexnum; i++)
    {
        visited[i] = 0;
    }
    cout << endl << "深度遍历： " << endl;
    DFS(G, 0);
    return 0;
}

执行结果：

我创建的图：