本文共 4907 字，大约阅读时间需要 16 分钟。

DFS遍历无向图的实现方法

无向图的DFS遍历是一种常见的图遍历算法，类似于二叉树的前序遍历。以下将详细介绍两种实现方法：邻接矩阵和邻接表。

方法一：邻接矩阵实现

思路：

DFS遍历的思路是使用深度优先搜索，依次访问图中每个顶点的未访问邻接顶点。

实现代码：

#include 
   
    #include 
    
     using namespace std;#define MAXVEX 10struct MGraph {    char vexs[MAXVEX];    int arc[MAXVEX][MAXVEX];    int numVEXS;};void Traverse(MGraph& G, bool* visited) {    for (int i = 0; i < G.numVEXS; ++i) {        if (!visited[i])            DFS(G, visited, i);    }}void DFS(MGraph& G, bool* visited, int i) {    visited[i] = true;    cout << G.vexs[i] << endl;    for (int j = 0; j < G.numVEXS; ++j) {        if (G.arc[i][j] && !visited[j])            DFS(G, visited, j);    }}int main() {    MGraph G;    G.numVEXS = 9;    for (int i = 0; i < G.numVEXS; ++i)        for (int j = 0; j < G.numVEXS; ++j)            G.arc[i][j] = 0;    G.arc[0][1] = G.arc[1][0] = 1;    G.arc[0][5] = G.arc[5][0] = 1;    G.arc[1][6] = G.arc[6][1] = 1;    G.arc[1][2] = G.arc[2][1] = 1;    G.arc[1][8] = G.arc[8][1] = 1;    G.arc[2][3] = G.arc[3][2] = 1;    G.arc[2][8] = G.arc[8][2] = 1;    G.arc[3][8] = G.arc[8][3] = 1;    G.arc[3][6] = G.arc[6][3] = 1;    G.arc[3][7] = G.arc[7][3] = 1;    G.arc[3][4] = G.arc[4][3] = 1;    G.arc[4][5] = G.arc[5][4] = 1;    G.arc[4][7] = G.arc[7][4] = 1;    G.arc[5][6] = G.arc[6][5] = 1;    G.arc[6][7] = G.arc[7][6] = 1;    G.vexs[0] = 'A'; G.vexs[1] = 'B'; G.vexs[2] = 'C';    G.vexs[3] = 'D'; G.vexs[4] = 'E'; G.vexs[5] = 'F';    G.vexs[6] = 'G'; G.vexs[7] = 'H'; G.vexs[8] = 'I';    bool visited[MAXVEX];    memset(visited, false, sizeof(visited));    Traverse(G, visited);    system("pause");    return 0;}
    
   

方法二：邻接表实现

结构体定义：

struct EdgeNode {    int adjvex;    EdgeNode* next;    EdgeNode(int value = -1) : adjvex(value), next(NULL) {}};struct VertexNode {    char data;    EdgeNode* firstedge;};typedef VertexNode VertexTable[MAXVEX];struct GraphAdjList {    VertexTable vertexTable;    int numVEXS;};

实现代码：

#include 
   
    #include 
    
     using namespace std;#define MAXVEX 15struct EdgeNode {    int adjvex;    EdgeNode* next;    EdgeNode(int value = -1) : adjvex(value), next(NULL) {}};struct VertexNode {    char data;    EdgeNode* firstedge;};typedef VertexNode VertexTable[MAXVEX];struct GraphAdjList {    VertexTable vertexTable;    int numVEXS;};void Traverse(GraphAdjList& G, bool* visited) {    for (int i = 0; i < G.numVEXS; ++i) {        if (!visited[i])            DFS(G, visited, i);    }}void DFS(GraphAdjList& G, bool* visited, int i) {    cout << G.vertexTable[i].data << endl;    visited[i] = true;    EdgeNode* temp = G.vertexTable[i].firstedge;    while (temp != NULL) {        if (!visited[temp->adjvex])            DFS(G, visited, temp->adjvex);        temp = temp->next;    }}int main() {    GraphAdjList G;    G.numVEXS = 9;    for (int i = 0; i < 9; ++i) {        G.vertexTable[i].firstedge = NULL;        G.vertexTable[i].data = 'A' + i;    }    EdgeNode* A_B = new EdgeNode(1);    EdgeNode* A_F = new EdgeNode(5);    EdgeNode* B_A = new EdgeNode(0);    EdgeNode* B_C = new EdgeNode(2);    EdgeNode* B_G = new EdgeNode(6);    EdgeNode* B_I = new EdgeNode(8);    EdgeNode* C_B = new EdgeNode(1);    EdgeNode* C_D = new EdgeNode(3);    EdgeNode* C_I = new EdgeNode(8);    EdgeNode* D_C = new EdgeNode(2);    EdgeNode* D_E = new EdgeNode(4);    EdgeNode* D_G = new EdgeNode(6);    EdgeNode* D_H = new EdgeNode(7);    EdgeNode* D_I = new EdgeNode(8);    EdgeNode* E_D = new EdgeNode(3);    EdgeNode* E_F = new EdgeNode(5);    EdgeNode* E_H = new EdgeNode(7);    EdgeNode* F_A = new EdgeNode(0);    EdgeNode* F_E = new EdgeNode(4);    EdgeNode* F_G = new EdgeNode(6);    EdgeNode* G_B = new EdgeNode(1);    EdgeNode* G_D = new EdgeNode(3);    EdgeNode* G_F = new EdgeNode(5);    EdgeNode* G_H = new EdgeNode(7);    EdgeNode* H_D = new EdgeNode(3);    EdgeNode* H_E = new EdgeNode(4);    EdgeNode* H_G = new EdgeNode(6);    EdgeNode* I_B = new EdgeNode(1);    EdgeNode* I_C = new EdgeNode(2);    EdgeNode* I_D = new EdgeNode(3);    G.vertexTable[0].firstedge = A_B;    A_B->next = A_F;    G.vertexTable[1].firstedge = B_A;    B_A->next = B_C;    B_C->next = B_G;    B_G->next = B_I;    G.vertexTable[2].firstedge = C_B;    C_B->next = C_D;    C_D->next = C_I;    G.vertexTable[3].firstedge = D_C;    D_C->next = D_E;    D_E->next = D_G;    D_G->next = D_H;    D_H->next = D_I;    G.vertexTable[4].firstedge = E_D;    E_D->next = E_F;    E_F->next = E_H;    G.vertexTable[5].firstedge = F_A;    F_A->next = F_E;    F_E->next = F_G;    G.vertexTable[6].firstedge = G_B;    G_B->next = G_D;    G_D->next = G_F;    G_F->next = G_H;    G.vertexTable[7].firstedge = H_D;    H_D->next = H_E;    H_E->next = H_G;    G.vertexTable[8].firstedge = I_B;    I_B->next = I_C;    I_C->next = I_D;    bool visited[MAXVEX];    memset(visited, false, sizeof(visited));    Traverse(G, visited);    system("pause");    return 0;}
    
   

总结

通过上述两种方法，可以实现对无向图的DFS遍历。邻接矩阵和邻接表的实现方式各有优劣，邻接矩阵的实现代码较为简洁，而邻接表实现更适合复杂图的扩展。