C语言版图的深度和广度优先遍历源代码

《C语言版图的深度和广度优先遍历源代码》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、邻接表表示的图：#include"stdio.h"#include"stdlib.h"#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域}EdgeNode;typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjLi

2、stadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;//图类型//=========建立图的邻接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s;//定义边表结点printf("InputVertexNum(n)andEdgesNum(e):");scanf("%d,%d",&G->n,&G->e);//读入顶点数和边数fflush(stdin);//清空内存缓冲printf("InputVertexstring:");for(i=0;in;i++)//建立边表{scan

3、f("%c",&a);G->adjlist[i].vertex=a;//读入顶点信息G->adjlist[i].firstedge=NULL;//边表置为空表}printf("Inputedges,CreatAdjacencyList");for(k=0;ke;k++){//建立边表scanf("%d%d",&i,&j);//读入边（Vi，Vj）的顶点对序号s=(EdgeNode*)malloc(sizeof(EdgeNode));//生成边表结点s->adjvex=j;//邻接点序号为js->next=G->adjlist[i].firstedge;G->adjlist[

4、i].firstedge=s;//将新结点*S插入顶点Vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));s->adjvex=i;//邻接点序号为is->next=G->adjlist[j].firstedge;G->adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voi

5、dDFSM(ALGraph*G,inti){//以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p;printf("%c",G->adjlist[i].vertex);//访问顶点Vivisited[i]=TRUE;//标记Vi已访问p=G->adjlist[i].firstedge;//取Vi边表的头指针while(p){//依次搜索Vi的邻接点Vj，这里j=p->adjvexif(!visited[p->adjvex])//若Vj尚未被访问DFSM(G,p->adjvex);//则以Vj为出发点向纵深搜索p=p->next;//找Vi的下一个邻接点}}voidDF

6、S(ALGraph*G){inti;for(i=0;in;i++)visited[i]=FALSE;//标志向量初始化for(i=0;in;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi为源点开始DFS搜索}//==========BFS：广度优先遍历=========voidBFS(ALGraph*G,intk){//以Vk为源点对用邻接链表表示的图G进行广度优先搜索inti,f=0,r=0;EdgeNode*p;intcq[MaxVertexNum];//定义FIFO队列for(i=0;in;i++)visited[i]

7、=FALSE;//标志向量初始化for(i=0;i<=G->n;i++)cq[i]=-1;//初始化标志向量printf("%c",G->adjlist[k].vertex);//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=-1){//队列非空则执行i=cq[f];f=f+1;//Vi出队p=G->adjlist[i].firstedge;//取Vi的