掌握深度优先遍历
实验题目
邻接表存储实现图的深度优先遍历
设计文档
代码
#include<iostream> using namespace std; #define MVNum 100 typedef char OtherInfo; int visited[MVNum]={0}; // visited数组，用于记录顶点是否被访问过 // 邻接表：顶点表、边表、邻接表 typedef struct ArcNode{ int adjvex; // 下标信息 OtherInfo info; // 其他信息 struct ArcNode* next; }ArcNode; typedef struct VNode{ char vex; // 顶点信息 ArcNode* first; // 指向第一条边的指针 }VNode,AdjList[MVNum]; typedef struct{ AdjList vertices; // 邻接表数组 int vexnum,arcnum; // 顶点数和边数 }ALGraph; // 定位顶点v在邻接表中的位置 int LocateVex(ALGraph G, char v){ for(int i = 0; i < G.vexnum; ++i){ if(G.vertices[i].vex == v) return i; } return -1; } void CreatALGraph(ALGraph &G, int &err){ cin >> G.vexnum >> G.arcnum; // 输入顶点数和边数 for(int i = 0; i < G.vexnum; ++i){ // 输入顶点信息，并初始化每个顶点的边表为空 cin >> G.vertices[i].vex; G.vertices[i].first = NULL; } for(int k = 0; k < G.arcnum; ++k){ // 构建边表 char v1, v2; cin >> v1 >> v2; int i, j; i = LocateVex(G, v1); j = LocateVex(G, v2); if(i == -1 || j == -1) err = 1; else{ ArcNode* p1 = new ArcNode; // 创建新的边节点 p1->adjvex = j; p1->next = G.vertices[i].first; G.vertices[i].first = p1; ArcNode* p2 = new ArcNode; // 创建新的边节点 p2->adjvex = i; p2->next = G.vertices[j].first; G.vertices[j].first = p2; } } } void DFS_ALGraph(ALGraph G, int adj){ cout << G.vertices[adj].vex << " "; // 输出当前顶点信息 visited[adj] = 1; // 标记该顶点已访问 ArcNode* p = G.vertices[adj].first; // 获取当前顶点的第一条边 while(p != NULL){ // 遍历当前顶点的所有邻接点 if(visited[p->adjvex] != 1) // 如果邻接点未被访问，则递归访问 DFS_ALGraph(G, p->adjvex); p = p->next; // 移动到下一个邻接点 } } int main(){ ALGraph G; int err = 0; char star; CreatALGraph(G, err); // 创建邻接表 cin >> star; // 输入起始顶点 int adj = LocateVex(G, star); // 定位起始顶点在邻接表中的位置 if(adj == -1 || err == 1) cout << "error"; else{ DFS_ALGraph(G, adj); // 开始深度优先遍历 } return 0; }
一、 个人体会(此部分与拼题a上主观题提交应一致)
第一题
1、 实验中遇到的具体问题：
在实现这个程序时，我遇到了两个主要问题。首先，我需要理解邻接表如何用于图的表示。其次，我需要理解深度优先搜索遍历的原理和实现方法。
2、 问题如何解决的：
我首先定义了一个结构体来作为邻接表，然后通过输入的边的信息，将每个顶点与其相邻的顶点之间的关系记录在邻接表中。在深度优先搜索遍历中，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。
3、 实验设计思路：
结构体定义：首先定义了一些结构体，包括ArcNode（边节点），VNode（顶点）和ALGraph（邻接表图）。边节点包含了一个邻接点（一个顶点）和其他信息。顶点包含了一个字符表示的顶点信息和一个指向第一条边的指针。邻接表图包含了一个顶点数组、一个边数组和一个邻接表数组，分别存储顶点信息、边信息和邻接表。
创建邻接表图：在CreatALGraph函数中，首先从标准输入中读取顶点数和边数。然后，为每个顶点输入一个字符表示的名称，并将每个顶点的边表初始化为空。接下来，你循环读取每条边的两个端点，并使用LocateVex函数找到这两个端点在邻接表中的位置。如果找不到任何一个端点，就设置错误标志。如果找到了，就使用"头插法"将一个新的边节点添加到这两个端点的边表中。
深度优先搜索：在DFS_ALGraph函数中，实现了深度优先搜索算法。从一个指定的邻接点开始，输出这个顶点的信息，并将这个顶点标记为已访问。然后，遍历这个顶点的所有邻接点。如果一个邻接点还没有被访问过，就递归地调用DFS_ALGraph函数对这个邻接点进行深度优先搜索。
主函数：在主函数中，创建了一个空的邻接表图，并调用CreatALGraph函数来填充这个图。然后，调用DFS_ALGraph函数来对图进行深度优先搜索遍历。
3、 实验后的感想：
在完成这个实验后，我对图的邻接表表示和深度优先搜索有了更深入的理解。邻接表是一种常用的图的表示方法，它通过使用数组和链表，有效地表示了图中顶点之间的关系。深度优先搜索则是一种用于遍历或搜索树或图的算法，它沿着树的深度遍历树的节点，尽可能深地搜索树的分支。在实验过程中，我遇到了一些困难，尤其是在构建邻接表和进行深度优先搜索时。我通过仔细阅读和理解代码，以及多次尝试和调试，最终成功地完成了实验。这个实验让我认识到编程需要细心和耐心，同时也需要不断地学习和实践。通过这个实验，我不仅学会了如何使用邻接表表示图，还学会了如何使用深度优先搜索遍历图。