使用邻接矩阵实现图的深度优先遍历

在数据结构中，图是一种非常重要的非线性结构，而深度优先遍历（Depth-First Search, DFS）是遍历图的基本方法之一。下面是一个使用邻接矩阵表示图，并实现DFS的C++代码示例：

#include

#include

using namespace std;

const int MaxInt = 32767;

const int MVNum = 100;

const int OK = 1;

typedef char VerTexType;

typedef int ArcType;

typedef int Status;

struct AMGraph {

vector vexs;

vector> arcs;

int vexnum, arcnum;

};

int LocateVex(const AMGraph &G, VerTexType u) {

for (int i = 0; i

if (u == G.vexs[i]) return i;

}

return -1;

}

Status CreateUDN(AMGraph &G) { // 创建无向网

cout <<"请输入顶点数及边数: ";

cin >> G.vexnum >> G.arcnum;

G.vexs.resize(G.vexnum);

G.arcs.resize(G.vexnum, vector(G.vexnum, 0));

cout <<"依次输入各顶点的信息: ";

for (int i = 0; i

cin >> G.vexs[i];

}

cout <<"输入每条边连接的两个顶点及权重: ";

for (int k = 0; k

VerTexType v1, v2;

int w;

cin >> v1 >> v2 >> w;

int i = LocateVex(G, v1), j = LocateVex(G, v2);

G.arcs[i][j] = w;

G.arcs[j][i] = w;

}

cout <<"输出邻接矩阵: ";

for (int i = 0; i

for (int j = 0; j

cout <

}

cout <

}

return OK;

}

bool visited[MVNum];

void DFS_AM(const AMGraph &G, int v) { // 深度优先搜索遍历

cout <

visited[v] = true;

for (int w = 0; w

if (G.arcs[v][w] != 0 && !visited[w]) {

DFS_AM(G, w);

}

}

}

int main() {

int start;

AMGraph G;

cout <<"初始化图..." <

CreateUDN(G);

cout <<"请输入遍历的起始位置: ";

cin >> start;

cout <<"遍历结果如下: " <

DFS_AM(G, start);

return 0;

}