DFS(G,v); printf("\n"); } #include"E:\SourceCode\DS\实验\第三章\循环队列.c" //算法7.6 void BFSTraverse(MGraph G,Status(*Visit)(VertexType)) { int v,u,w; VertexType w1,u1; SqQueue *Q; for(v=0;v<G.vexnum;v++) visited[v]=FALSE; Q=InitQueue(Q); for(v=0;v<G.vexnum;v++) if(!visited[v]) { visited[v]=TRUE; Visit(G.vexs[v]); EnQueue(Q,v); while(!QueueEmpty(Q)) { u=DeQueue(Q); strcpy(u1,*GetVex(G,u)); for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w)))) if(!visited[w]) { visited[w]=TRUE; Visit(G.vexs[w]); EnQueue(Q,w); } } } printf("\n"); }
Байду номын сангаас
void main() { MGraph g; printf("----------------------------------------------------------------------\n"); printf(" 利用图的邻接矩阵进行图的遍历 \n"); printf(" Algorithm 7.4,7.5,7.6 \n"); printf("----------------------------------------------------------------------\n"); CreateUDN(&g); Display(g); printf("深度优先搜索的结果:\n"); DFSTraverse(g,visit); printf("广度优先搜索的结果:\n"); BFSTraverse(g,visit); } //------------------图的邻接表存储表示-----------------#include<stdio.h> #include<malloc.h> #include<string.h> #define OK 1 #define ERROR 0 typedef int Status; #define MAX_VERTEX_NUM 20 #define MAX_NAME 3 typedef int InfoType; typedef char VertexType[MAX_NAME]; typedef enum{DG,DN,UDG,UDN}GraphKind;//{有向图,有向网,无向图,无向 网} typedef struct ArcNode { int adjvex; struct ArcNode *nextarc;
InfoType *info;//该弧有关信息的指针 }ArcNode; typedef struct VNode { VertexType data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; int kind; }ALGraph; //求顶点在图中的位置 int LocateVex(ALGraph G,VertexType u) { int i; for(i=0;i<G.vexnum;i++) if(strcmp(u,G.vertices[i].data)==0) return i; return -1; } //建图 Status CreateGraph(ALGraph *G) { int i,j,k,w; VertexType v1,v2; ArcNode *p; printf("请输入图的类型(有向图:0,有向网:1,无向图:2,无向网:3):"); scanf("%d",&(*G).kind); printf("请输入图的顶点数,边数:"); scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
p->info=(int*)malloc(sizeof(int)); *(p->info)=w; } else p->info=NULL; p->nextarc=(*G).vertices[j].firstarc; (*G).vertices[j].firstarc=p; } } return OK; } //输出 void Display(ALGraph G) { int i; ArcNode *p; switch(G.kind) { case DG: printf("建立的是有向图:\n"); break; case DN: printf("建立的是有向网:\n"); break; case UDG: printf("建立的是无向图:\n"); break; case UDN: printf("建立的是无向网:\n"); } printf("%d个顶点:\n",G.vexnum); for(i=0;i<G.vexnum;++i) printf("%s ",G.vertices[i].data); printf("\n%d条弧(边):\n",G.arcnum); for(i=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p) {
printf("请输入%d个顶点的值(最大命名为%d个字符):\n", (*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;++i) { scanf("%s",(*G).vertices[i].data); (*G).vertices[i].firstarc=NULL; } if((*G).kind==1||(*G).kind==3) printf("输入每条边的权值+弧尾+弧头:\n"); else printf("输入每条边的弧尾+弧头:\n"); for(k=0;k<(*G).arcnum;++k) { if((*G).kind==1||(*G).kind==3) scanf("%d%s%s",&w,v1,v2); else scanf("%s%s",v1,v2); i=LocateVex(*G,v1); j=LocateVex(*G,v2); p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=j; if((*G).kind==1||(*G).kind==3) { p->info=(int *)malloc(sizeof(int)); *(p->info)=w; } else p->info=NULL; p->nextarc=(*G).vertices[i].firstarc; (*G).vertices[i].firstarc=p; if((*G).kind>=2) { p=(ArcNode*)malloc(sizeof(ArcNode)); p->adjvex=i; if((*G).kind==3) {
//-----------------------使用数组结构的BFS_DFS遍历----------------------//-----------------------在调用main函数时要把其他的main函数注释掉------------------#include"图的邻接矩阵存储表示.c" #include<process.h> #define TRUE 1 #define FALSE 0 typedef int Boolean; Boolean visited[MAX_VERTEX_NUM]; Status(*VisitFunc)(VertexType); //访问函数 Status visit(VertexType i) { printf("%s ",i); return OK; } //返回顶点的值 VertexType* GetVex(MGraph G,int v) { if(v>=G.vexnum||v<0) exit(ERROR); return &G.vexs[v]; } //求第一个邻接点的位置 int FirstAdjVex(MGraph G,VertexType v) { int i,j=0,k; k=LocateVex(G,v); for(i=0;i<G.vexnum;i++) if(G.arcs[k][i].adj!=j) return i; return -1;
} //下一个邻接点的位置 int NextAdjVex(MGraph G,VertexType v,VertexType w) { int i,j=0,k1,k2; k1=LocateVex(G,v); k2=LocateVex(G,w); for(i=k2+1;i<G.vexnum;i++) if(G.arcs[k1][i].adj!=j) return i; return -1; } //算法7.5 void DFS(MGraph G,int v) { VertexType w1,v1; int w; visited[v]=TRUE; VisitFunc(G.vexs[v]); strcpy(v1,*GetVex(G,v)); for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w)))) if(!visited[w]) DFS(G,w); } //算法7.4 void DFSTraverse(MGraph G,Status(*Visit)(VertexType)) { int v; VisitFunc=Visit; for(v=0;v<G.vexnum;v++) visited[v]=FALSE; for(v=0;v<G.vexnum;v++) if(!visited[v])
