C语言版图的深度和广度优先遍历源代码(共6页).doc
精选优质文档-倾情为你奉上表示的图：#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 /定义最大顶点数typedef struct node /边表结点int adjvex; /邻接点域struct node *next; /链域EdgeNode;typedef struct vnode /顶点表结点char vertex; /顶点域EdgeNode *firstedge; /边表头指针VertexNode;typedef VertexNode AdjListMaxVertexNum; /AdjList是邻接表类型typedef struct AdjList adjlist; /邻接表int n,e; /图中当前顶点数和边数 ALGraph; /图类型/=建立图的邻接表=void CreatALGraph(ALGraph *G)int i,j,k;char a;EdgeNode *s; /定义边表结点printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); /读入顶点数和边数fflush(stdin); /清空内存缓冲printf("Input Vertex string:");for(i=0;i<G->n;i+) /建立边表scanf("%c",&a);G->adjlisti.vertex=a; /读入顶点信息G->adjlisti.firstedge=NULL; /边表置为空表printf("Input edges,Creat Adjacency Listn");for(k=0;k<G->e;k+) /建立边表 scanf("%d%d",&i,&j); /读入边（Vi，Vj）的顶点对序号s=(EdgeNode *)malloc(sizeof(EdgeNode); /生成边表结点s->adjvex=j; /邻接点序号为js->next=G->adjlisti.firstedge;G->adjlisti.firstedge=s; /将新结点*S插入顶点Vi的边表头部s=(EdgeNode *)malloc(sizeof(EdgeNode); s->adjvex=i; /邻接点序号为is->next=G->adjlistj.firstedge; G->adjlistj.firstedge=s; /将新结点*S插入顶点Vj的边表头部/=定义标志，为=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：的=void DFSM(ALGraph *G,int i)/以Vi为出发点对邻接表示的图G进行DFS搜索EdgeNode *p;printf("%c",G->adjlisti.vertex); /访问顶点Vivisitedi=TRUE; /标记Vi已访问p=G->adjlisti.firstedge; /取Vi边表的头指针while(p) /依次搜索Vi的邻接点Vj，这里j=p->adjvexif(! visitedp->adjvex) /若Vj尚未被访问DFSM(G,p->adjvex); /则以Vj为出发点向纵深搜索p=p->next; /找Vi的下一个邻接点void DFS(ALGraph *G)int i;for(i=0;i<G->n;i+)visitedi=FALSE; /标志向量初始化for(i=0;i<G->n;i+)if(!visitedi) /Vi未访问过 DFSM(G,i); /以Vi为源点开始DFS搜索 /=BFS：=void BFS(ALGraph *G,int k) /以Vk为源点对用邻接链表表示的图G进行int i,f=0,r=0; EdgeNode *p; int cqMaxVertexNum; /定义FIFO队列 for(i=0;i<G->n;i+)visitedi=FALSE; /标志向量初始化for(i=0;i<=G->n;i+)cqi=-1; /初始化标志向量printf("%c",G->adjlistk.vertex); /访问源点Vkvisitedk=TRUE;cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队 while(cqf!=-1) / 队列非空则执行i=cqf; f=f+1; /Vi出队p=G->adjlisti.firstedge; /取Vi的边表头指针while(p) /依次搜索Vi的邻接点Vj（令p->adjvex=j）if(!visitedp->adjvex) /若Vj未访问过printf("%c",G->adjlistp->adjvex.vertex); /访问Vjvisitedp->adjvex=TRUE;r=r+1; cqr=p->adjvex; /访问过的Vj入队p=p->next; /找Vi的下一个邻接点/endwhile/=主函数=void main()/int i;ALGraph *G;G=(ALGraph *)malloc(sizeof(ALGraph);CreatALGraph(G);printf("Print Graph DFS: ");DFS(G);printf("n");printf("Print Graph BFS: ");BFS(G,3);printf("n");表示的图：#include"stdio.h"#include"stdlib.h"#define MaxVertexNum 100 /定义最大顶点数typedef structchar vexsMaxVertexNum; /顶点表int edgesMaxVertexNumMaxVertexNum; /邻接，可看作边表int n,e; /图中的顶点数n和边数eMGraph; /用邻接矩阵表示的图的类型/=建立邻接矩阵=void CreatMGraph(MGraph *G)int i,j,k;char a;printf("Input VertexNum(n) and EdgesNum(e): ");scanf("%d,%d",&G->n,&G->e); /输入顶点数和边数scanf("%c",&a); printf("Input Vertex string:");for(i=0;i<G->n;i+) scanf("%c",&a);G->vexsi=a; /读入顶点信息，建立顶点表for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)G->edgesij=0; /初始化邻接矩阵printf("Input edges,Creat Adjacency Matrixn");for(k=0;k<G->e;k+) /读入e条边，建立邻接矩阵 scanf("%d%d",&i,&j); /输入边（Vi，Vj）的顶点序号G->edgesij=1; G->edgesji=1; /若为无向图，矩阵为；若建立有向图，去掉该条语句 /=定义标志向量，为全局变量=typedef enumFALSE,TRUE Boolean;Boolean visitedMaxVertexNum;/=DFS：深度优先遍历的递归算法=void DFSM(MGraph *G,int i) /以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵int j;printf("%c",G->vexsi); /访问顶点Vivisitedi=TRUE; /置已访问标志for(j=0;j<G->n;j+) /依次搜索Vi的邻接点if(G->edgesij=1 && ! visitedj)DFSM(G,j); /（Vi，Vj）E，且Vj未访问过，故Vj为新出发点void DFS(MGraph *G) int i;for(i=0;i<G->n;i+)visitedi=FALSE; /标志向量初始化for(i=0;i<G->n;i+)if(!visitedi) /Vi未访问过DFSM(G,i); /以Vi为源点开始DFS搜索/=BFS：广度优先遍历=void BFS(MGraph *G,int k) /以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索int i,j,f=0,r=0;int cqMaxVertexNum; /定义队列 for(i=0;i<G->n;i+)visitedi=FALSE; /标志向量初始化for(i=0;i<G->n;i+)cqi=-1; /队列初始化printf("%c",G->vexsk); /访问源点Vkvisitedk=TRUE;cqr=k; /Vk已访问，将其入队。注意，实际上是将其序号入队while(cqf!=-1) /队非空则执行i=cqf; f=f+1; /Vf出队for(j=0;j<G->n;j+) /依次Vi的邻接点Vjif(!visitedj && G->edgesij=1) /Vj未访问printf("%c",G->vexsj); /访问Vjvisitedj=TRUE; r=r+1; cqr=j; /访问过Vj入队/=main=void main()/int i;MGraph *G;G=(MGraph *)malloc(sizeof(MGraph); /为图G申请内存空间CreatMGraph(G); /建立邻接矩阵printf("Print Graph DFS: ");DFS(G); /深度优先遍历printf("n");printf("Print Graph BFS: ");BFS(G,3); /以序号为3的顶点开始广度优先遍历printf("n");专心-专注-专业
