用邻接矩阵储存图（附带深度优先遍历DFS）代码解析

一、数据结构定义

代码中定义了结构体 AMGraph 来表示图。其中，Vnum 存储图的顶点数量，Anum 存储边的数量。vexs 是一个指向字符类型的指针，用于存储顶点信息，构成顶点表。arcs 是一个二维指针，指向整型类型，代表邻接矩阵，用于表示顶点之间的连接关系。结构体还包含析构函数 ~AMGraph()，其主要作用是在对象生命周期结束时释放动态分配的内存，包括 vexs 数组以及 arcs 二维数组的内存空间，以防止内存泄漏。

二、关键函数功能

1. LocateVex 函数
   该函数用于在图中查找给定顶点 x 的下标。通过遍历 AMGraph 结构体中的顶点表 vexs，逐一比较顶点元素，若找到与 x 相等的顶点，则返回其对应的下标值。此函数为后续根据顶点信息操作邻接矩阵提供了索引依据。
2. createVexs 函数
   此函数负责创建顶点表。依据 AMGraph 结构体中的顶点数量 Vnum，动态分配内存给 vexs 数组。随后利用循环，从标准输入读取顶点信息，并依次存储到 vexs 数组中，从而完成顶点表的构建。
3. createArcs 函数
   用于创建邻接矩阵。首先根据顶点数量 Vnum 为 arcs 二维指针分配内存空间，以构建能够表示图中顶点连接关系的矩阵结构。接着将邻接矩阵中的所有元素初始化为 0，表示初始状态下各顶点间无连接。然后，按照输入的边信息，通过循环读取每一条边的两个顶点 Vbefore 和 Vbehind，借助 LocateVex 函数获取这两个顶点在顶点表中的下标，进而在邻接矩阵中将对应位置的元素设置为 1，以表示这两个顶点之间存在边连接。由于所处理的是无向图，所以需要在邻接矩阵的对称位置（即 arcs[Vbehind 下标][Vbefore 下标]）也设置为 1。
4. DFS_AM 函数
   这是深度优先搜索的核心函数。从指定的起始顶点 v 开始搜索过程。首先输出当前顶点 G.vexs[v]，表示已访问该顶点，并在 visited 数组中将对应顶点的标记设置为 1。然后，通过循环遍历邻接矩阵的当前行（即与顶点 v 相关的连接关系），若发现与顶点 v 有边相连（G.arcs[v][i]!= 0）且目标顶点 i 尚未被访问（visited[i] == 0），则递归调用 DFS_AM 函数，以深度优先的策略继续探索与顶点 i 相连的其他顶点，直至无法继续深入或所有顶点均已被访问。

在 main 函数中，首先创建 AMGraph 图对象 G，并从标准输入读取图的顶点数量 Vnum 和边数量 Anum。接着依次调用 createVexs 函数和 createArcs 函数构建图的顶点表和邻接矩阵。随后创建并初始化 visited 数组，用于记录顶点的访问状态。最后，从顶点 0 开始调用 DFS_AM 函数进行深度优先搜索，并在搜索结束后释放 visited 数组的内存空间。

#include<iostream>
using namespace std;
typedef char VerTexType;
typedef int ArcType;

struct AMGraph
{
	int Vnum;  //点数
	int Anum;  //边数
	VerTexType* vexs;  //顶点表
	ArcType** arcs;  //领接矩阵

	~AMGraph()
	{
		delete[] vexs;
		for (int i = 0; i < Vnum; i++) {
			delete[] arcs[i];
		}
		delete[] arcs;
	}
};

//找到顶点下标
int LocateVex(AMGraph& G, VerTexType x)
{
	for (int i = 0; i < G.Vnum; i++) {
		if (G.vexs[i] == x)
			return i;
	}
}
//创建顶点表
void createVexs(AMGraph& G)
{
	//顶点表
	G.vexs = new VerTexType[G.Vnum];
	for (int i = 0; i < G.Vnum; i++) {
		cin >> G.vexs[i];
	}
}
//创建邻接矩阵
void createArcs(AMGraph& G)
{
	//领接矩阵
	G.arcs = new ArcType * [G.Vnum];
	for (int i = 0; i < G.Vnum; i++) {
		G.arcs[i] = new ArcType[G.Vnum];
	}
	for (int j = 0; j < G.Vnum; j++) {
		for (int k = 0; k < G.Vnum; k++) {
			G.arcs[j][k] = 0;
		}
	}

	VerTexType Vbefore, Vbehind;
	for (int i = 0; i < G.Anum; i++) {
		cin >> Vbefore >> Vbehind;
		G.arcs[LocateVex(G, Vbefore)][LocateVex(G, Vbehind)] = 1;
		G.arcs[LocateVex(G, Vbehind)][LocateVex(G, Vbefore)] = 1;
	}
}

void DFS_AM(AMGraph& G, int v,int*& visited)
{
	cout << G.vexs[v] << " ";
	visited[v] = 1;
	for (int i = 0; i < G.Vnum; i++) {
		if ((G.arcs[v][i] != 0) && (visited[i] == 0)) {
			DFS_AM(G, i,visited);
		}
	}
}

int main()
{
	AMGraph G;
	cin >> G.Vnum >> G.Anum;
	createVexs(G);
	createArcs(G);
	int* visited = new int[G.Vnum];
	for (int i = 0; i < G.Vnum; i++) {
		visited[i] = 0;
	}
	DFS_AM(G, 0, visited);

	delete[] visited;
	return 0;
}