国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > 数据结构(C实现)------- 图的广度优先遍历

数据结构(C实现)------- 图的广度优先遍历

来源:程序员人生   发布时间:2015-01-21 09:00:02 阅读次数:3563次

[本文是自己学习所做笔记,欢迎转载,但请注明出处:http://blog.csdn.net/jesson20121020]

算法描写:

          设图G的初始状态是所有顶点均未被访问过,在G中的任选1顶点vi为初始动身点,则广度优先遍历 可定义以下:首先,访问初始动身点vi,接着顺次访问vi的所有邻接点w1,w2,...,wk;然后,顺次访问w1,w2,...,wk 的邻接的所有未被访问过的顶点,顺次类推,直到图中所有的和初始点vi有路径相通的顶点都被访问过为止。

算法实现:

           (1) 访问初始顶点vi

          (2) 置顶点v已访问标记

          (3) 顶点v入队

          (4) while(队不空){

                   取出队首顶点i;

                   顺次搜索顶点i的所有的邻接点;

                   如果未被访问,则访问该邻接点,并将其入队。

           }

              

               用邻接矩阵实现图的广度优先遍历的源代码以下:

/** * 广度遍历图 **/ void BFS_MG(MGraph MG,int s){ //清空访问标志 init_Visit(); //定义队列,用于保存当前节点的邻接顶点 int Q[MAX_VEX_NUM]; int front = 0; int rear = 0; int i,j,k; printf("%c ",MG.vexs[s]); visit[s] = 1; Q[rear++] = s; //遍历队列 while(front < rear){ i = Q[front++]; for (j = 1; j <= MG.vexnum;j++){ if(visit[j] == 0 && MG.arcs[i][j] == 1){ printf("%c ",MG.vexs[j]); visit[j] = 1; Q[rear++] = j; } } } }

         用邻接表实现图的广度优先遍历的源代码以下:

/** * 广度遍历图 **/ void BFS_AG(ALGraph AG,int s){ ArcPtr p; //清空访问标志 init_Visit(); //定义队列,用于保存当前节点的邻接顶点 int Q[MAX_VERTEX_NUM]; int front = 0; int rear = 0; int i,j,k; printf("%c ",AG.vertices[s]); visit[s] = 1; Q[rear++] = s; //遍历队列 while(front < rear){ i = Q[front++]; for(p = AG.vertices[i].firstarc;p;p=p->nextarc){ j = p->adjvex; if(visit[j] == 0){ printf("%c ",AG.vertices[j].vexdata); visit[j] = 1; Q[rear++] = j; } } } }

算法说明:  

        对有具有n个顶点和e条边的连通图,由于每一个基点均需要入队1次,所以while语句需要履行n次,对邻接矩阵而言,内循环搜索邻接点时一样需要履行n次,故BFS_MG的时间复杂度为O(n^2);对邻接表而言,内循环的次数取决于各顶点的边表结点的总个数,所以BFS_AG的时间复杂度为O(n+e)。

        可以看出,广度优先遍历需要1个辅助队列,和标志数组,故空间复杂度为O(n)。

      

完全代码:

           用邻接矩阵实现广度优先遍历的完全代码:

/* ============================================================================ Name : Graph.c Author : jesson20121020 Version : 1.0 Description : create Graph using Adjacency Matrix, Ansi-style ============================================================================ */ #include <stdio.h> #include <stdlib.h> #define MAX_VEX_NUM 50 typedef char VertexType; typedef enum { DG, UDG } GraphType; typedef struct { VertexType vexs[MAX_VEX_NUM]; int arcs[MAX_VEX_NUM][MAX_VEX_NUM]; int vexnum, arcnum; GraphType type; } MGraph; //设置图中顶点访问标志 int visit[MAX_VEX_NUM]; /** * 根据名称得到指定顶点在顶点集合中的下标 * vex 顶点 * return 如果找到,则返回下标,否则,返回0 */ int getIndexOfVexs(char vex, MGraph *MG) { int i; for (i = 1; i <= MG->vexnum; i++) { if (MG->vexs[i] == vex) { return i; } } return 0; } /** * 创建邻接矩阵 */ void create_MG(MGraph *MG) { int i, j, k; int v1, v2, type; char c1, c2; printf("Please input graph type DG(0) or UDG(1) :"); scanf("%d", &type); if (type == 0) MG->type = DG; else if (type == 1) MG->type = UDG; else { printf("Please input correct graph type DG(0) or UDG(1)!"); return; } printf("Please input vexmun : "); scanf("%d", &MG->vexnum); printf("Please input arcnum : "); scanf("%d", &MG->arcnum); getchar(); for (i = 1; i <= MG->vexnum; i++) { printf("Please input %dth vex(char):", i); scanf("%c", &MG->vexs[i]); getchar(); } //初始化邻接矩阵 for (i = 1; i <= MG->vexnum; i++) { for (j = 1; j <= MG->vexnum; j++) { MG->arcs[i][j] = 0; } } //输入边的信息,建立邻接矩阵 for (k = 1; k <= MG->arcnum; k++) { printf("Please input %dth arc v1(char) v2(char) : ", k); scanf("%c %c", &c1, &c2); v1 = getIndexOfVexs(c1, MG); v2 = getIndexOfVexs(c2, MG); if (MG->type == 1) MG->arcs[v1][v2] = MG->arcs[v2][v1] = 1; else MG->arcs[v1][v2] = 1; getchar(); } } /** * 打印邻接矩阵和顶点信息 */ void print_MG(MGraph MG) { int i, j; if(MG.type == DG){ printf("Graph type: Direct graph "); } else{ printf("Graph type: Undirect graph "); } printf("Graph vertex number: %d ",MG.vexnum); printf("Graph arc number: %d ",MG.arcnum); printf("Vertex set: "); for (i = 1; i <= MG.vexnum; i++) printf("%c ", MG.vexs[i]); printf(" Adjacency Matrix: "); for (i = 1; i <= MG.vexnum; i++) { j = 1; for (; j < MG.vexnum; j++) { printf("%d ", MG.arcs[i][j]); } printf("%d ", MG.arcs[i][j]); } } /** * 初始化顶点访问标志 **/ void init_Visit(){ int i; for(i = 0;i < MAX_VEX_NUM;i++) visit[i] = 0; } /** * 广度遍历图 **/ void BFS_MG(MGraph MG,int s){ //清空访问标志 init_Visit(); //定义队列,用于保存当前节点的邻接顶点 int Q[MAX_VEX_NUM]; int front = 0; int rear = 0; int i,j,k; printf("%c ",MG.vexs[s]); visit[s] = 1; Q[rear++] = s; //遍历队列 while(front < rear){ i = Q[front++]; for (j = 1; j <= MG.vexnum;j++){ if(visit[j] == 0 && MG.arcs[i][j] == 1){ printf("%c ",MG.vexs[j]); visit[j] = 1; Q[rear++] = j; } } } } /** * 主函数 */ int main(void) { MGraph MG; create_MG(&MG); print_MG(MG); printf(" The result of BFS: "); BFS_MG(MG,1); return EXIT_SUCCESS; }

          

           用邻接表实现广度优先遍历的完全代码:

/* ============================================================================ Name : ALGraph.c Author : jesson20121020 Version : Copyright : Your copyright notice Description : Graph using linkList, Ansi-style ============================================================================ */ #include <stdio.h> #include <stdlib.h> #include <stdio.h> #define MAX_VERTEX_NUM 50 typedef enum { DG, UDG } GraphType; typedef char VertexType; //表节点 typedef struct ArcNode { int adjvex; //邻接节点 int weight; //边权重 struct ArcNode *nextarc; //下1个节点指针 } ArcNode, *ArcPtr; //头节点 typedef struct { VertexType vexdata; int id; ArcPtr firstarc; } VNode; //头节点数组 typedef struct { VNode vertices[MAX_VERTEX_NUM]; int vexnum, arcnum; GraphType type; } ALGraph; int visit[MAX_VERTEX_NUM]; /** * 根据顶点字符得到在顶点数组中的下标 */ int getIndexOfVexs(char vex, ALGraph *AG) { int i; for (i = 1; i <= AG->vexnum; i++) { if (AG->vertices[i].vexdata == vex) { return i; } } return 0; } /** * 创建邻接表 */ void create_AG(ALGraph *AG) { ArcPtr p,q; int i, j, k, type; VertexType v1, v2; printf("Please input graph type UG(0) or UDG(1) :"); scanf("%d", &type); if (type == 0) AG->type = DG; else if (type == 1) AG->type = UDG; else { printf("Please input correct graph type UG(0) or UDG(1)!"); return; } printf("please input vexnum:"); scanf("%d", &AG->vexnum); printf("please input arcnum:"); scanf("%d", &AG->arcnum); getchar(); for (i = 1; i <= AG->vexnum; i++) { printf("please input the %dth vex(char) : ", i); scanf("%c", &AG->vertices[i].vexdata); getchar(); AG->vertices[i].firstarc = NULL; } for (k = 1; k <= AG->arcnum; k++) { printf("please input the %dth arc v1(char) v2(char) :", k); scanf("%c %c", &v1, &v2); i = getIndexOfVexs(v1, AG); j = getIndexOfVexs(v2, AG); //根据图的类型创建邻接表 //方法1,插入到链表头 /* if (AG->type == DG) { //有向图 p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = j; p->nextarc = AG->vertices[i].firstarc; AG->vertices[i].firstarc = p; } else { //无向图 p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = j; p->nextarc = AG->vertices[i].firstarc; AG->vertices[i].firstarc = p; p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = i; p->nextarc = AG->vertices[j].firstarc; AG->vertices[j].firstarc = p; } */ //方法2,插入到链表尾 if (AG->type == DG) { //有向图 p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = j; //表为空 if(AG->vertices[i].firstarc == NULL){ AG->vertices[i].firstarc = p; } else{ //找最后1个表节点 q = AG->vertices[i].firstarc; while(q->nextarc != NULL){ q = q->nextarc; } q->nextarc = p; } p->nextarc = NULL; } else { //无向图 p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = j; //表为空 if(AG->vertices[i].firstarc == NULL){ AG->vertices[i].firstarc = p; } else{ //找最后1个表节点 q = AG->vertices[i].firstarc; while(q->nextarc != NULL){ q = q->nextarc; } q->nextarc = p; } p->nextarc = NULL; p = (ArcPtr) malloc(sizeof(ArcNode)); p->adjvex = i; //表为空 if(AG->vertices[j].firstarc == NULL){ AG->vertices[j].firstarc = p; } else{ //找最后1个表节点 q = AG->vertices[j].firstarc; while(q->nextarc != NULL){ q = q->nextarc; } q->nextarc = p; } p->nextarc = NULL; } getchar(); } } /** * 输出图的相干信息 */ void print_AG(ALGraph AG) { ArcPtr p; int i; if (AG.type == DG) { printf("Graph type: Direct graph "); } else { printf("Graph type: Undirect graph "); } printf("Graph vertex number: %d ", AG.vexnum); printf("Graph arc number: %d ", AG.arcnum); printf("Vertex set : "); for (i = 1; i <= AG.vexnum; i++) printf("%c ", AG.vertices[i].vexdata); printf(" Adjacency List: "); for (i = 1; i <= AG.vexnum; i++) { printf("%d", i); p = AG.vertices[i].firstarc; while (p != NULL) { printf("-->%d", p->adjvex); p = p->nextarc; } printf(" "); } } /** * 初始化顶点访问标志 **/ void init_Visit(){ int i; for(i = 0;i < MAX_VERTEX_NUM;i++) visit[i] = 0; } /** * 广度遍历图 **/ void BFS_AG(ALGraph AG,int s){ ArcPtr p; //清空访问标志 init_Visit(); //定义队列,用于保存当前节点的邻接顶点 int Q[MAX_VERTEX_NUM]; int front = 0; int rear = 0; int i,j,k; printf("%c ",AG.vertices[s]); visit[s] = 1; Q[rear++] = s; //遍历队列 while(front < rear){ i = Q[front++]; for(p = AG.vertices[i].firstarc;p;p=p->nextarc){ j = p->adjvex; if(visit[j] == 0){ printf("%c ",AG.vertices[j].vexdata); visit[j] = 1; Q[rear++] = j; } } } } int main(void) { ALGraph AG; create_AG(&AG); print_AG(AG); printf(" The result of BFS: "); BFS_AG(AG,1); return EXIT_SUCCESS; }



生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生