//廣度優先搜索遍歷連通圖
#include <iostream>
using namespace std;
#define MVNum 100
#define MAXQSIZE 100
typedef char VerTexType;
typedef int ArcType;
bool visited[MVNum];
typedef struct {
VerTexType vexs[MVNum];
ArcType arcs[MVNum][MVNum];
int vexnum, arcnum;
}Graph;
typedef struct {
ArcType* base;
int front;
int rear;
}sqQueue;
void InitQueue(sqQueue& Q) {
Q.base = new ArcType[MAXQSIZE];
if (!Q.base)
exit(1);
Q.front = Q.rear = 0;
}
void EnQueue(sqQueue& Q, ArcType e) {
if ((Q.rear + 1) % MAXQSIZE == Q.front)
return;
Q.base[Q.rear] = e;
Q.rear = (Q.rear + 1) % MAXQSIZE;
}
bool QueueEmpty(sqQueue Q) {
if (Q.rear == Q.front)
return true;
return false;
}
void Dequeue(sqQueue& Q, ArcType& u) {
u = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;
}
int LocateVex(Graph G, VerTexType v) {
for (int i = 0;i < G.vexnum;++i)
if (G.vexs[i] == v)
return i;
return -1;
}
void CreateUDN(Graph& G) {
int i, j, k;
cout << "請輸入總頂點數，總邊數，以空格隔開:";
cin >> G.vexnum >> G.arcnum;
cout << endl;
cout << "輸入點的名稱，如a" << endl;
for (i = 0;i < G.vexnum;++i) {
cout << "請輸入第" << (i + 1) << "個點的名稱:";
cin >> G.vexs[i];
}
cout << endl;
for (i = 0;i < G.vexnum;++i) {
for (j = 0;j < G.vexnum;++i)
G.arcs[i][j] = 0;
}
cout << "輸入邊依附的頂點，如a b" << endl;
for (k = 0;k < G.vexnum;k++) {
VerTexType v1, v2;
cout << "請輸入第" << (k + 1) << "條邊依附的頂點:";
cin >> v1 >> v2;
i = LocateVex(G, v1);
j = LocateVex(G, v2);
G.arcs[i][j] = 1;
G.arcs[j][i] = G.arcs[i][j];
}
}
int FirstAdjVex(Graph G, int v) {
int i;
for (i = 0;i < G.vexnum;++i) {
if (G.arcs[v][i] == 1 && visited[i] == false)
return i;
}
return -1;
}
int NextAdjVex(Graph G, int u, int w) {
int i;
for (i = w;i < G.vexnum;++i) {
if (G.arcs[u][i] == 1 && visited[i] == false)
return i;
}
return -1;
}
void BFS(Graph G, int v) {
sqQueue Q;
ArcType u;
ArcType w;
cout << G.vexs[v] << " ";
visited[v] = true;
InitQueue(Q);
EnQueue(Q, v);
while (!QueueEmpty(Q)) {
Dequeue(Q, u);
for (w = FirstAdjVex(G, u);w >= 0;w = NextAdjVex(G, u, w)) {
if (!visited[w]) {
cout << G.vexs[w] << " ";
visited[w] = true;
EnQueue(Q, w);
}
}
}
}
int main() {
cout << "廣度優先搜索遍歷連通圖";
Graph G;
CreateUDN(G);
cout << endl;
cout << "無向連通圖G創建完成！" << endl;
cout << "請輸入遍歷連通圖的起始點：";
VerTexType c;
cin >> c;
int i;
for (i = 0;i < G.vexnum;++i) {
if (c == G.vexs[i])
break;
}
cout << endl;
while (i >= G.vexnum) {
cout << "該點不存在，請重新輸入！" << endl;
cout << "請輸入遍歷連通圖的起始點：";
cin >> c;
for (i = 0;i < G.vexnum;++i) {
if (c == G.vexs[i])
break;
}
}
cout << "廣度優先搜索遍歷連通圖結果：" << endl;
BFS(G, i);
cout << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/124300.html
標籤：其他
上一篇：深度優先搜索遍歷非連通圖