图的广度优先搜索（BFS）-白红宇

图的广度优先搜索（BFS）

阅读量：5912 次

发布时间：2019-06-19

本文共 3196 字，大约阅读时间需要 10 分钟。

把以前写过的图的广度优先搜索分享给大家（C语言版）

1 #include
     
        2 #include
      
         3 #define MAX_VERTEX_NUM 20  4 #define MAXQSIZE 100  5 #define OK 1  6 typedef char VertexType;  7 typedef int QElemType;  8    9 typedef struct ArcNode//边结点 10 { 11     int adjvex; 12     struct ArcNode *nextarc; 13 }ArcNode; 14  15 typedef struct VNode//定义头数组 16 { 17     VertexType data; 18     ArcNode *firstarc; 19 }VNode,AdjList[MAX_VERTEX_NUM]; 20  21 typedef struct ALGraph//定义图 22 { 23     AdjList vertices; 24     int vernum,arcnum; 25 }ALGraph; 26  27 typedef struct SqQueue 28 { 29     QElemType *base; 30     int front; 31     int rear; 32 }SqQueue; 33  34 int CreateDG(ALGraph &G) 35 { 36     int i,j,k,v1,v2; 37     ArcNode *p; 38     printf("请输入图的节点数："); 39     scanf("%d",&G.vernum ); 40     printf("请输入图的边的个数："); 41     scanf("%d",&G.arcnum); 42     for(i=0;i
       
        G.vernum||j<1||j>G.vernum) 61         { 62             printf("请输入第%d条边的一个结点：",k+1); 63             scanf("%d",&v1); 64             printf("请输入第%d条边的一个结点：",k+1); 65             scanf("%d",&v2); 66             printf("\n"); 67             i=v1; 68             j=v2; 69         } 70         p=(ArcNode *)malloc(sizeof(ArcNode)); 71         if(!p) 72         { 73             printf("分配内存失败！\n"); 74             return 0; 75         } 76         p->adjvex=j-1; 77         p->nextarc=G.vertices[i-1].firstarc; 78         G.vertices[i-1].firstarc=p; 79     } 80     return OK; 81 } 82 int InitQueue(SqQueue &Q) 83 { 84     Q.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); 85     if(!Q.base) 86     { 87         printf("队列内存失败！\n"); 88         return 0; 89     } 90     Q.front=Q.rear=0; 91     return (OK); 92 } 93  94 int EnQueue(SqQueue &Q,QElemType e) 95 { 96     if((Q.rear+1)%MAXQSIZE==Q.front) 97     { 98         printf("队列已满!\n"); 99         return 0;100     }101     Q.base[Q.rear]=e;102     Q.rear=(Q.rear+1)%MAXQSIZE;103     return (OK);104 }105 int QueueEmpty(SqQueue Q)106 {107     if(Q.front==Q.rear)108         return (OK);109     else 110         return 0;111 }112 113 int DeQueue(SqQueue &Q,QElemType &e)114 {115     if(Q.front==Q.rear)116     {117         printf("队列为空！无法删除！\n");118         return 0;119     }120     e=Q.base[Q.front];121     Q.front=(Q.front+1)%MAXQSIZE;122     return (e);123 }124 void BFSTraverse(ALGraph G)125 {126     int i,j,k;127     int visited[MAX_VERTEX_NUM];128     ArcNode *p;129     SqQueue Q;130     for(i=0;i
        
         ",G.vertices[i].data);139             EnQueue(Q,i);140             while(!QueueEmpty(Q))141             {142                 DeQueue(Q,j);143                 for(k=j,p=G.vertices[j].firstarc;p!=NULL;k=p->adjvex,p=p->nextarc)144                 {145                     if(visited[k]==0)146                     {147                         visited[k]=1;148                         printf("%c-->",G.vertices[k].data);149                         EnQueue(Q,k);150                     }151                 }152             }153         }154     }155 }156 int main()157 {158     ALGraph G;159     CreateDG(G);160     161     printf("广度优先搜索结果为\n开始-->");162     BFSTraverse(G);163     printf("结束!\n");164     return 0;165 }