共计 1724 个字符,预计需要花费 5 分钟才能阅读完成。
#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 CreateUDG(Graph &G){
int i , j , k;
cout <<"总顶点数 总边数:";
cin >> G.vexnum >> G.arcnum;
for(i = 0; i < G.vexnum; ++i){cout << "第" << (i+1) << "个点的名称:";
cin >> G.vexs[i];
}
for(i = 0; i < G.vexnum; ++i)
for(j = 0; j < G.vexnum; ++j)
G.arcs[i][j] = 0;
for(k = 0; k < G.arcnum;++k){
VerTexType v1 , v2;
cout << "第" << (k + 1) << "条边附丽的顶点:";
cin >> v1 >> v2;
i = LocateVex(G, v1); j = LocateVex(G, v2);
G.arcs[j][i] = G.arcs[i][j] = 1;
}
}
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(){
Graph G;
CreateUDG(G);
cout << "遍历无向图的起始点:";
VerTexType c;
cin >> c;
int i;
for(i = 0 ; i < G.vexnum ; ++i){if(c == G.vexs[i])
break;
}
cout << "广度优先搜寻遍历无向图:";
BFS(G , i);
return 0;
}
正文完