C语言实现图的广度优先遍历
/*-----------------------------------------------------------------------------Copyright (c) 2010-2011 Zidane CLiUsage of this program is free for non-commercial use.-----------------------------------------------------------------------------*//* 用邻接矩阵实现图，并用广度优先遍历遍历图。*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#define MAX_NAME 5// 顶点字符串的最大长度+1#define MAX_INFO 20// 相关信息字符串的最大长度+1typedef int VRType;// 顶点关系的数据类型#define INFINITY INT_MAX// 用整型最大值代替∞#define MAX_VERTEX_NUM 20// 最大顶点个数 typedef char InfoType;// 信息的类型typedef char VertexType;// 顶点数据类型及长度typedef enum {DG, DN, UDG, UDN}GraphKind;typedef struct ArcCell{VRType adj;InfoType* info;}ArcCell, AdjMatrix;typedef struct{VertexType vexs;AdjMatrix arcs;int vexnum, arcnum;GraphKind kind;}MGraph;#define BOOL int#define TRUE 1#define FALSE 0typedef VertexType *QElemType;typedef struct{QElemType* elem;//存储空间基址int queuesize;int front;int rear;}SqQueue;void visit(VertexType a){printf("%s", a);}void InitQueue(SqQueue* Q, int size){Q->queuesize = size;Q->elem = (QElemType*)malloc(Q->queuesize * sizeof(QElemType));Q->front = Q->rear = 0;}void DestroyQueue(SqQueue* Q){Q->queuesize = 0;Q->front = Q->rear = 0;free(Q->elem);}void ClearQueue(SqQueue* Q){Q->rear = Q->front;Q->queuesize = 0;}BOOL QueueEmpty(SqQueue Q){return Q.front == Q.rear;}int QueueLength(SqQueue Q){return Q.rear - Q.front;}QElemType GetHead(SqQueue Q){return Q.elem;}void EnQueue(SqQueue* Q, QElemType e){Q->elem = e;}void DeQueue(SqQueue* Q, QElemType* e){//剩余元素向前移*e = Q->elem;int i;for (i = 0; i < Q->rear; i++){Q->elem = Q->elem;}Q->rear--;}int LocateVex(MGraph G, VertexType a){ int i;for (i = 0; i < G.vexnum; i++){if(strcmp(a, G.vexs) == 0){return i;}}return -1;}void CreateDG(MGraph* G){VertexTypeva, vb; int IncInfo, i, j, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs.adj = 0;G->arcs.info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s", va, vb);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs.adj = 1;if (IncInfo){scanf("%s", G->arcs.info);}G->arcs.adj = G->arcs.adj;}G->kind = DG;}void CreateDN(MGraph* G){VertexTypeva, vb; int IncInfo, i, j, w, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs.adj = INFINITY;G->arcs.info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s%d", va, vb, &w);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs.adj = w;if (IncInfo){scanf("%s", G->arcs.info);}}G->kind = DN;}void CreateUDG(MGraph* G){VertexTypeva, vb; int IncInfo, i, j, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs.adj = 0;G->arcs.info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s", va, vb);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs.adj = 1;if (IncInfo){scanf("%s", G->arcs.info);}G->arcs.adj = G->arcs.adj;}G->kind = UDG;}void CreateUDN(MGraph* G){VertexTypeva, vb; int IncInfo, i, j, w, k;printf("Number of Vex and Arc, Info: ");scanf("%d%d%d", &G->vexnum, &G->arcnum, &IncInfo);//构造顶点向量for (i = 0; i < G->vexnum; i++){scanf("%s", G->vexs); }//初始化邻接矩阵for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){G->arcs.adj = INFINITY;G->arcs.info = NULL;}}//构造邻接矩阵for (k = 0; k < G->arcnum; k++){//顶点1，顶点2，权值scanf("%s%s%d", va, vb, &w);i = LocateVex(*G, va);j = LocateVex(*G, vb);G->arcs.adj = w;if (IncInfo){scanf("%s", G->arcs.info);}G->arcs.adj = G->arcs.adj;}G->kind = UDN;}void CreateGraph(MGraph* G){printf("Kind of the Graph: ");scanf("%d", (int*)&G->kind);switch (G->kind){case DG: return CreateDG(G);break;case DN: return CreateDN(G);break;case UDG: return CreateUDG(G);break;case UDN: return CreateUDN(G);break;}}VertexType* GetVex(MGraph G, int v){ //局部变量保存在stack中，函数执行完会自动释放，所以不要将局部变量的指针作为返回值 VertexType* vex = (VertexType*)malloc(sizeof(VertexType)); vex = &G.vexs;return vex;}//对a赋新值valuevoid PutVex(MGraph* G, VertexType a, char* value){int i = LocateVex(*G, a);strcpy(G->vexs, value);}//返回a的第一个邻接顶点（从第一个顶点开始与其相连的第一个顶点）int FirstAdjVex(MGraph G, VertexType a){int k = LocateVex(G, a);int w = (G.kind == DN || G.kind == UDN ? INFINITY : 0);int i; //w为不存在时的值for (i = 0; i < G.vexnum; i++){if (G.arcs.adj != w){return i;}}return -1;}//返回a的（相对于b的）下一个邻接顶点。若b是a的最后一个邻接点，则返回-1。int NextAdjVex(MGraph G, VertexType a, VertexType b){int k1 = LocateVex(G, a);int k2 = LocateVex(G, b);//w为不存在时的值int w = (G.kind == DN || G.kind == UDN ? INFINITY : 0);int i;for (i = k2 + 1; i < G.vexnum; i++){if (G.arcs.adj != w){return i;}}return -1;}//在图中只添加一个顶点，且和图中顶点有相同特征void InsertVex(MGraph* G, VertexType a){strcpy(G->vexs, a);int i;for(i = 0; i <= G->vexnum; i++){switch (G->kind){case DG: case UDG: G->arcs.adj = 0;G->arcs.adj = 0;break;case DN: case UDN: G->arcs.adj = INFINITY;G->arcs.adj = INFINITY;break; }}G->vexnum++;}void DeleteVex(MGraph* G, VertexType v){int i, j, k;VRType m=0;k = LocateVex(*G,v);// k为待删除顶点v的序号 if(k < 0)// v不是图G的顶点if(G->kind == DN || G->kind == UDN) // 网m = INFINITY;for(j = 0; j < G->vexnum; j++)if(G->arcs.adj != m)// 有入弧或边 {if(G->arcs.info)// 有相关信息 free(G->arcs.info);// 释放相关信息 G->arcnum--;// 修改弧数 }if(G->kind == DG || G->kind == DN) // 有向 for(j = 0; j < G->vexnum; j++)if(G->arcs.adj != m)// 有出弧 {if(G->arcs.info) // 有相关信息 free(G->arcs.info); // 释放相关信息 G->arcnum--; // 修改弧数 }for(j = k + 1; j < G->vexnum; j++) // 序号k后面的顶点向量依次前移 strcpy(G->vexs, G->vexs);for(i = 0; i < G->vexnum; i++)for(j = k + 1; j < G->vexnum; j++)G->arcs = G->arcs; // 移动待删除顶点之后的矩阵元素 for(i = 0; i < G->vexnum; i++)for(j = k + 1; j < G->vexnum; j++)G->arcs = G->arcs; // 移动待删除顶点之下的矩阵元素 G->vexnum--;}void InsertArc(MGraph* G, VertexType a, VertexType b){int i = LocateVex(*G, a);int j = LocateVex(*G, b);G->arcnum++;switch (G->kind){case DG: G->arcs.adj = 1;break;case DN: printf("Please input value of arc: ");scanf("%d", &G->arcs.adj);break;case UDG: G->arcs.adj = 1;break;case UDN: printf("Please input value of arc: ");scanf("%d", &G->arcs.adj);break;}}void DeleteArc(MGraph* G, VertexType a, VertexType b){int i = LocateVex(*G, a);int j = LocateVex(*G, b);G->arcnum--;switch (G->kind){case DG: case UDG: G->arcs.adj = 0;break;case DN: case UDN: G->arcs.adj = INFINITY;break;}}/* 给定一个图和一个源顶点，则可以遍历整个图。 广度优先遍历构造了一棵广度优先树。算法首先显示源顶点，其次发现和源顶点距离为k的所有顶点，然后才发现距离为(k + 1)的所有顶点。 遍历的过程使用visited来存储结点是否被访问过。FALSE表示未被访问。*/BOOL visited;void BFSTraverse(MGraph G){printf("BFS: ");QElemType v;int i, j;for (i = 0; i < G.vexnum; i++){visited = FALSE;}SqQueue Q;InitQueue(&Q, G.vexnum);for (i = 0; i < G.vexnum; i++){if (!visited){visited = TRUE;visit(G.vexs);EnQueue(&Q, GetVex(G, i));//将距离为k的结点保存在队列中while (!QueueEmpty(Q)){ //队头元素出队并置为vDeQueue(&Q, &v);for (j = FirstAdjVex(G, *v); j >= 0; j = NextAdjVex(G, *v, *GetVex(G, j))){if (!visited){visited = TRUE;visit(G.vexs);EnQueue(&Q, GetVex(G, j));}}}}}DestroyQueue(&Q);printf("\n");}int main(){ MGraph a; CreateGraph(&a); BFSTraverse(a); return 0;}//error: expected declaration or statement at end of input 花括号不匹配
页:
[1]