- #include<stdio.h>
- #include<stdlib.h>
- /*邻接表的结点数据结构*/
- typedef struct ArcNode
- {
- int adjvex;
- struct ArcNode * nextArc; //指向下一结点
- } ArcNode, *AdjList;
- /*图中结点数据结构*/
- typedef struct VNode
- {
- int data; //结点的值
- AdjList firstArc; //该节点邻接表的头指针
- } VNode;
- /*图的数据结构*/
- typedef struct
- {
- VNode vertices[20]; //顶点数组
- int vexnum; //顶点个数
- } Graph;
- typedef struct QNode
- {
- int data;
- struct QNode * next;
- } QNode,*QPointer;
- typedef struct Queue
- {
- struct QNode * first;
- struct QNode * last;
- } Queue;
- /*创建队列*/
- void createQueue(Queue &Q)
- {
- QPointer p = (QPointer)malloc(sizeof(QNode));
- Q.first = Q.last = p;
- Q.first->next = Q.last->next = NULL;
- }
- /*入队*/
- void enqueue(Queue &Q,int v)
- {
- QPointer p = (QPointer)malloc(sizeof(QNode));
- p->data = v;
- p->next = NULL;
- if(Q.first->next == NULL) //队列为空的情况
- Q.first->next = p;
- else //队列非空的情况
- Q.last->next = p;
- Q.last = p;
- }
- /*判断队列是否为空*/
- int isEmpty(Queue Q)
- {
- int flag = 0;
- if(Q.first->next == NULL)
- flag = 1;
- return flag;
- }
- /*返回队首元素*/
- int getFirst(Queue Q)
- {
- if(isEmpty(Q))
- exit(0);
- return Q.first->next->data;
- }
- /*出队*/
- void dequeue(Queue &Q)
- {
- if(isEmpty(Q))
- exit(0);
- QPointer p = Q.first->next;
- Q.first->next = p->next;
- }
- void createGraph(Graph &G, int n) //引用参数要以&开头,否则运行出错,原因暂时不清楚
- {
- G.vexnum = n;
- int num;
- AdjList p;
- AdjList newNode;
- int i, j;
- printf("输入每个结点的值\\n");
- for (i = 0; i < G.vexnum; i++)
- scanf("%d", &G.vertices[i].data); //输入每个节点的值
- for (i = 0; i < G.vexnum; i++)
- G.vertices[i].firstArc = NULL;
- for (i = 0; i < G.vexnum; i++)
- {
- printf("输入V%d的邻接表中结点个数 ", i);
- scanf("%d", &num);
- if (num != 0)
- {
- printf("输入这%d个结点: ", num);
- p = (AdjList) malloc(sizeof (ArcNode));
- scanf("%d", &p->adjvex); //输入邻接表中的头结点
- p->nextArc = NULL;
- G.vertices[i].firstArc = p; //将头结点信息赋给结点i
- for (j = 1; j < num; j++)
- {
- newNode = (AdjList) malloc(sizeof (ArcNode));
- scanf("%d", &newNode->adjvex); //输入邻接表中除头尾结点外的中间结点
- p->nextArc = newNode;
- newNode->nextArc = NULL;
- p = newNode;
- }
- }
- }
- }
- void BFS(Graph G,int v,char * color[20])
- {
- AdjList cursor = G.vertices[v].firstArc;
- int u,w;
- Queue Q;
- createQueue(Q);
- if(color[v] == "white"){
- color[v] = "gray";
- enqueue(Q,v);
- }
- while(!isEmpty(Q))
- {
- w = getFirst(Q);
- dequeue(Q);
- printf("V%d:%d\\t",w,G.vertices[w].data);
- cursor = G.vertices[w].firstArc;
- while(cursor)
- {
- u = cursor->adjvex;
- if(color[u] == "white")
- {
- color[u] = "gray";
- enqueue(Q,u);
- }
- cursor = cursor->nextArc;
- }
- color[w] = "black";
- }
- }
- void bfsSweep(Graph G,char *color[20]){
- for(int i = 0;i < 20;i++)
- color[i] = "white";
- for(int i = 0;i <G.vexnum;i++)
- BFS(G,i,color);
- }
- int main(){
- Graph G;
- int n;
- char *color[20];
- printf("输入图G中的节点的个数: ");
- scanf("%d",&n);
- createGraph(G,n);
- printf("广度优先遍历的节点的顺序为\\n");
- bfsSweep(G,color);
- }
- //该片段来自于http://www.codesnippet.cn/detail/121120137100.html
来源: http://www.codesnippet.cn/detail/121120137100.html