把以前写过的图的广度优先搜索分享给大家(C语言版)
1 #include<stdio.h>
2 #include<stdlib.h>
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;i++)
43 {
44 printf("请输入第%d个顶点数据:",i+1);
45 getchar();
46 scanf("%c",&G.vertices[i].data);
47 //G.vertices[i].data=i;
48 G.vertices[i].firstarc=NULL;
49 }
50 printf("请输入节点的边关系,如:结点1和结点2有边就输入1和2(每条边就输入一次):\n");
51 for(k=0;k<G.arcnum;k++)
52 {
53 printf("请输入第%d条边的一个结点:",k+1);
54 scanf("%d",&v1);
55 printf("请输入第%d条边的另一个结点:",k+1);
56 scanf("%d",&v2);
57 printf("\n");
58 i=v1;
59 j=v2;
60 while(i<1||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.vernum;i++)
131 visited[i]=0;
132 InitQueue(Q);
133 for(i=0;i<G.vernum;i++)
134 {
135 if(visited[i]==0)
136 {
137 visited[i]=1;
138 printf("%c-->",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 }
运行结果截图: