代理充值平台网站,网站如何做服务器授权书,做ppt在哪些网站可以卖钱,qq推广群任务要求参考答案评论2
任务描述相关知识编程要求测试说明 任务描述
本关任务#xff1a;以邻接矩阵存储图#xff0c;要求编写程序实现图的深度优先遍历。
相关知识
图的深度优先遍历类似于树的先序遍历, 是树的先序遍历的推广#xff0c;其基本思想如下#xff1a;
…
任务要求参考答案评论2
任务描述相关知识编程要求测试说明 任务描述
本关任务以邻接矩阵存储图要求编写程序实现图的深度优先遍历。
相关知识
图的深度优先遍历类似于树的先序遍历, 是树的先序遍历的推广其基本思想如下
从某个顶点v出发访问此顶点。访问一个与v邻接的顶点u之后再从u出发访问与u邻接且未被访问的顶点w依此类推。当到达一个所有邻接顶点都被访问的顶点时则又从最后被访问过的顶点开始依次退回到最近被访问的尚有邻接顶点的末被访问过的顶点从该顶点出发重复步骤 2 和 3 直到所有被访问过的顶点的邻接顶点都被访问过为止。
在程序里完成遍历需要在函数体外定义全局访问标志数组记录顶点是否被访问过初始时所有元素均为0表示所有顶点未被访问过
int visited[MAX_VERTEX_NUM] {0};
访问每个顶点时定义输出顶点数据的专用函数 void visit(VertexType i){printf(%s ,i); // VertexType是char [20]类型}
以邻接矩阵作为存储结构进行深度优先遍历的算法如下
深度优先遍历的代码分为两部分遍历的图可能是非连通图从一个顶点出发可能不能遍历所有顶点故对于每个顶点都要检查一次是否被访问过如果没有从这个没被访问的顶点出发执行一次深度优先遍历算法如下 void DFSTraverse(Mgraph G){ // 初始条件图G存在vi是顶点的输出函数的指针。// 操作结果从第1个顶点起深度优先遍历图G并对每个顶点访问一次且仅一次 int v;for(v0;vG.vexnum;v)visited[v]0; // 访问标志数组初始化(未被访问) for(v0;vG.vexnum;v)if(!visited[v])DFS(G,v); // 对尚未访问的顶点v调用DFS printf(\n);}
编程要求
根据提示在右侧编辑器补充代码实现以邻接矩阵作为存储结构的图深度优先遍历算法:
void DFS(MGraph G,int v); // 从第v个顶点出发递归地深度优先遍历图Gvoid DFSTraverse(MGraph G); // 图G存在从第1个顶点起深度优先遍历图G并对每个顶点调用函数visit一次且仅一次
测试说明
平台会对你编写的代码进行测试
测试输入 0 lt2.txt 输入说明 第一行输入0表示输入图的类型为有向图。 第二行输入文件名该文件里保存了图的数据信息内容如下 第1行为图的顶点的个数n 第2行为图的边的条数m 第3行至第n2行是n个顶点的数据 第n3行至第nm2行是m条边的数据 预期输出 有向图 7个顶点9条边。顶点依次是: 高等数学 程序设计基础 C语言 离散数学 数据结构 编译原理 操作系统 图的邻接矩阵: 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 深度优先遍历序列 高等数学 C语言 数据结构 编译原理 操作系统 离散数学 程序设计基础
#includestdio.h
#includestdlib.h
#includestring.h
#includelimits.h #includeMGraph.hvoid DFS(MGraph G,int v);// 从第v个顶点出发递归地深度优先遍历图G
void DFSTraverse(MGraph G);// 图G存在从第1个顶点起深度优先遍历图G并对每个顶点调用函数visit一次且仅一次 int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) int main()
{MGraph g;VertexType v1,v2;CreateGraphF(g); /* 利用数据文件创建无向图*/Display(g); /* 输出无向图*/ printf(深度优先遍历序列\n); DFSTraverse(g);return 0;
}void DFS(MGraph G,int v)
{// 从第v个顶点出发递归地深度优先遍历图G /********** Begin **********/int w;visited[v]1;visit(G.vexs[v]);for(wFirstAdjVex(G,G.vexs[v]);w0;wNextAdjVex(G,G.vexs[v],G.vexs[w]))if(!visited[w])DFS(G,w);/********** End **********/
}void DFSTraverse(MGraph G)
{ //图G存在从第1个顶点起深度优先遍历图G并对每个顶点调用函数visit一次且仅一次 /********** Begin **********/int v;for(v0;vG.vexnum;v)visited[v]0;for(v0;vG.vexnum;v)if(!visited[v])DFS(G,v);printf(\n);/********** End **********/
}输出说明 第一行输出图的类型。 第二行起输出图的顶点和边的数据信息。 最后一行为从“高等数学”出发进行深度优先遍历的序列。
