学生作品
cout<<" 主菜单 "<<endl;
cout<<"1建立无向图的邻接表"<<endl;
cout<<"2按深度遍历图"<<endl;
cout<<"3按广度遍历图"<<endl;
cout<<"4结束程序运行"<<endl;
cout<<"-------------------------"<<endl;
cout<<"请输入你的选择1、2、3、4:"<<endl;
cin>>cord;
switch(cord)
{
case 1:creatgraph(AdjList);
break;
case 2:dfsTraverse(AdjList);
break;
case 3:bfsTraverse(AdjList);
break;
case 4:exit(0);
}
根据给定的信息，我们可以分析出该段代码主要实现了图的基本操作，包括图的创建和两种基本的图遍历方法：深度优先搜索（Depth-First Search, DFS）与广度优先搜索（Breadth-First Search, BFS）。接下来，我们将详细探讨这些知识点。
### 图的创建
在计算机科学中，图是一种非线性的数据结构，它由顶点集和边集组成，用来表示实体之间的关系。图可以分为有向图和无向图。在本例中，我们处理的是无向图。
#### 创建无向图的邻接表
邻接表是表示图的一种方式，适用于稀疏图，即边数远少于顶点数的平方。对于无向图而言，每条边连接两个顶点，因此在邻接表中，每个顶点都有一个链表记录与之相邻的所有顶点。
- **初始化**：
- 定义了 `struct Vnode` 结构体，其中包含顶点的数据 `data` 和指向第一条边的指针 `firstarc`。
- 定义了 `struct ArcNode` 结构体，其中包含边的另一个顶点编号 `adjvex` 和指向下一个邻接点的指针 `nextarc`。
- 用户输入边的数量 `m` 和顶点的数量 `n`。
- 初始化顶点列表 `A` 的大小为 `MaxSize`（50），并设置每个顶点的初始值。
- **添加边**：
- 循环读取每条边的两个端点 `i` 和 `j`，并为它们创建双向的邻接链表。
- 通过 `malloc` 分配内存来创建新的边，并将其添加到相应的顶点的链表中。
- 打印出每个顶点及其对应的邻接表。
### 深度优先遍历 (DFS)
深度优先搜索是一种用于遍历或搜索树或图的算法。在这个过程中，算法会尽可能深地沿着树的分支探索。当到达某个节点的末端而没有找到目标时，它会回溯到上一步，改变路径继续探索。
#### DFS 实现
- **初始化**：
- 定义一个栈 `ar` 来存储遍历过程中的节点。
- 初始化一个数组 `visited` 来标记已经访问过的顶点。
- 用户输入起始顶点 `x`。
- **遍历过程**：
- 将起始顶点入栈并标记已访问。
- 当栈不为空或当前节点有未访问的邻接点时，循环进行以下操作：
- 如果当前节点没有未访问的邻接点，则弹出栈顶元素，并将栈顶的邻接点赋值给当前节点。
- 否则，访问当前节点的一个未访问的邻接点，将其入栈，并将当前节点更新为其邻接点的第一个邻接点。
- 遍历完成后，所有可达的顶点都将被访问。
### 广度优先遍历 (BFS)
广度优先搜索是从根节点开始，然后依次对每一层的节点进行访问的图遍历算法。这种遍历方式确保了距离根节点最近的节点先被访问。
#### BFS 实现
- **初始化**：
- 定义一个队列 `ar` 来存储待访问的节点。
- 初始化一个数组 `visited` 来标记已经访问过的顶点。
- 用户输入起始顶点 `x`。
- **遍历过程**：
- 将起始顶点入队并标记已访问。
- 当队列不为空时，循环进行以下操作：
- 出队队首元素并访问。
- 将当前顶点的所有未访问的邻接点加入队列，并标记为已访问。
- 遍历完成后，所有可达的顶点都将被访问。
### 总结
以上代码片段展示了如何创建一个无向图的邻接表，并实现两种常用的图遍历算法：深度优先搜索和广度优先搜索。通过这种方式，我们可以有效地解决很多实际问题，例如寻找最短路径、检测环路等。理解这些基础概念和技术对于学习更高级的数据结构和算法非常重要。
