树的深度优先遍历代码

树的深度优先遍历代码

ID:34476481

大小:39.00 KB

页数:3页

时间:2019-03-06

树的深度优先遍历代码_第1页
树的深度优先遍历代码_第2页
树的深度优先遍历代码_第3页
资源描述:

《树的深度优先遍历代码》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

1、对下图实现深度优先遍历:02345761采用邻接矩阵表示图:程序代码如下:#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum20//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵,可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGr

2、aph(MGraph*G){inti,j,k;chara;printf("InputVertexNumandEdgesNum(n,e):");scanf("%d,%d",&G->n,&G->e);//输入顶点数和边数printf("InputVertexstring:");for(i=0;in;i++){scanf("%d",&a);G->vexs[i]=a;//读入顶点信息,建立顶点表}for(i=0;in;i++)for(j=0;jn;j++)G->edges[i][j]=0;//初始化邻接矩阵print

3、f("Inputedges,CreatAdjacencyMatrix");for(k=0;ke;k++){//读入e条边,建立邻接矩阵scanf("%d%d",&i,&j);//输入边(Vi,Vj)的顶点序号G->edges[i][j]=1;G->edges[j][i]=1;//若为无向图,矩阵为对称矩阵;若建立有向图,去掉该条语句}}//=========定义标志向量,为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//====

4、====DFS:深度优先遍历的递归算法======voidDFSM(MGraph*G,inti){//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索,邻接矩阵是0,1矩阵intj;printf("%d",G->vexs[i]);//访问顶点Vivisited[i]=TRUE;//置已访问标志for(j=0;jn;j++)//依次搜索Vi的邻接点if(G->edges[i][j]==1&&!visited[j])DFSM(G,j);//(Vi,Vj)∈E,且Vj未访问过,故Vj为新出发点}voidDFS(MGraph*G){in

5、ti;for(i=0;in;i++)visited[i]=FALSE;//标志向量初始化for(i=0;in;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi为源点开始DFS搜索}voidmain(){MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));//为图G申请内存空间CreatMGraph(G);//建立邻接矩阵printf("TheUndigraph'sDFS:");DFS(G);//深度优先遍历printf("");}运行方法如下:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。