|
邻接表表示的图的深度优先搜索和广度优先搜索程序 #include <stdioh> #define maxvertexnum #define queuesize #define null typedef struct{ int frontrearcountdata[queuesize]; }cirqueue;//循环队列结构定义 typedef int vertextype;//为了简单设图中结点的数据为整型 typedef struct node{ int adjvex;//存放邻接点序号 struct node *next;//指向下一个边结点 }edgenode;//图的邻接表的边结点定义 typedef struct vnode{ vertextype vertex;//顶点数据域 edgenode *firstedge;//指向第一个边结点 }vertexnode;//图的邻接表表示的顶点结点定义 typedef vertexnode adjlist[maxvertexnum];//用向量定义图的邻接表表示的顶点表 typedef struct{ adjlist adjlist; int n;//图的顶点数 int e;//图的边数 }algraph;//定义图的邻接表 typedef enum{FALSETRUE}boolean; boolean visited[maxvertexnum];//保存访问信息的布尔向量 main()//主函数 {//建立图g并进行深度优先搜索和广度优先搜索 algraph *g; g=(algraph*)malloc(sizeof(algraph));//申请图g的邻接表空间 createalgraph(g);//建立图g的邻接表表示 printf(the dfs is:);/ dfstraverse(g);//对图g进行深度优先搜索并打印搜索序列 printf(the bfs is:); bfstraverse(g);//对图g进行广度优先搜索并打印搜索序列 } createalgraph(algraph *g) {//建立图g的邻接表表示 int ijk; int flag; edgenode *s; printf(\ncreat:\n)//选择建立有向图或无向图 printf(digraph\n); printf(undigraph\n); scanf(%d&flag); printf(input ne\n); scanf(%d%d&g>n&g>e);//输入图g的顶点数和边数 printf(input nodes:\n); for(i=;i<g>n;i++){//构造一个只含n个顶点边数为的图 scanf(%d&(g>adjlist[i]vertex)); //输入顶点的数据域（为了简单起见输入为整数） g>adjlist[i]firstedge=null;//将顶点结点的firstedge域置为空 }//end for for(k=;k<g>e;k++){ printf(input ij(~n):\n); scanf(%d%d&i&j);//输入对应于一条边的顶点序号序偶对要求顶点序号为~n s=(edgenode *)malloc(sizeof(edgenode));//申请一个边结点*s s>adjvex=j;//将序号j放入边结点*s的adjvex域 s>next=g>adjlist[i]firstedge; //将边结点*s作为第一个邻接点插入到序号为i的顶点的边表中 g>adjlist[i]firstedge=s; if (flag){//若要建立无向图 s=(edgenode *)malloc(sizeof(edgenode));申请一个边结点*s s>adjvex=i;//将序号i放入边结点*s的adjvex域 s>next=g>adjlist[j]firstedge; //将边结点*s作为第一个邻接点插入到序号为j的顶点的边表中 g>adjlist[j]firstedge=s; }//end of if }//end of for }//end of creatalgraph dfs(algraph *gint i) {//对图g进行以序号为i的顶点作为出发点深度优先搜索 edgenode *p; printf(visit vertex:%dg>adjlist[i]vertex);//打印序号为i的顶点信息 visited[i]=TRUE;//将序号为i的顶点设置已访问过标记 p=g>adjlist[i]firstedge;//设置寻找序号为i的第一个未访问过邻接点的扫描指针 while(p){ if (!visited[p>adjvex])//若*p边结点对应顶点（假设序号为j）未访问过 dfs(gp>adjvex);//对图g进行以序号为j的顶点作为出发点进行深度优先搜索 p=p>next;//p顺着边表next指针往后继续寻找 }//end of while }//end of dfs dfstraverse(algraph *g) {//对以邻接表表示的图g进行深度优先搜索 int i; for(i=;i<g>n;i++)//将图g的所有顶点设置未访问过标记 visited[i]=FALSE; for(i=;i<g>n;i++)//对图g调用dfs函数进行深度优先搜索 if(!visited[i]) dfs(gi); printf(\n); }//end of dfstraverse bfs(algraph *gint k) {//对图g进行以序号为k的顶点作为出发点广度优先搜索 int ij; cirqueue *q;//设置循环队列指针 edgenode *p; q=(cirqueue *)malloc(sizeof(cirqueue));//申请循环队列空间 q>rear=q>front=q>count=;//将循环队列置为空队 printf(visit vertex:%dg>adjlist[k]vertex); visited[k]=TRUE;//将序号为k的顶点设置为已访问过 q>data[q>rear]=k;q>rear=(q>rear+)%queuesize;q>count++;//将顶点序号k入队 while(q>count){//当队列非空时做以下操作 i=q>data[q>front];q>front=(q>front+)%queuesize;q>count;//将队首元素i出队 p=g>adjlist[i]firstedge;//设置寻找序号为i顶点的未访问过邻接点的扫描指针p while (p){//当*p不为空时做以下操作 if(!visited[p>adjvex]){//若*p边结点对应顶点（假设序号为j）未访问过 printf(visit vertex:%dg>adjlist[p>adjvex]vertex); //访问序号为j的顶点 visited[p>adjvex]=TRUE;//设置已访问过标记 q>data[q>rear]=p>adjvex;q>rear=(q>rear+)%queuesize;q>count++; //将序号为j的顶点入队 }//end of if p=p>next;//p顺着边表next指针往后继续寻找 }//end of while }//end of while }//end of bfs bfstraverse(algraph *g) {//对以邻接表表示的图g进行广度优先搜索 int i; for(i=;i<g>n;i++)//将图g的所有顶点设置未访问过标记 visited[i]=FALSE; for(i=;i<g>n;i++)//对图g调用bfs函数进行广度优先搜索 if(!visited[i]) bfs(gi); printf(\n); } |
