// 图的存储和遍历
#include <iostream>
using namespace std;
// ------------------------------------
// 邻接矩阵的存储以及深度和广度优先遍历
// ------------------------------------
// 邻接矩阵的存储定义
#define MAX 10000000
#define MAX_VERTEX_NUM 100
typedef enum {
DG,DN,UDG,UDN
}GraphKind; // 有向图、有向网、无向图、无向网
typedef struct {
char vexs[MAX_VERTEX_NUM];
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum, edgenum;
GraphKind kind;
}MGraph;
// 构造无向图的邻接矩阵，n个节点，e条边
void CreateUDG(MGraph &G, int n, int e) {
G.vexnum = n;
G.edgenum = e;
cout << "请输入顶点信息："<< endl;
int i, j, k;
for (i = 0; i < n; i++) {
cin >> G.vexs[i]; // 输入顶点信息
}
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
G.edges[i][j] = 0; // 矩阵初始化为0
}
}
cout << endl;
cout << "请输入边的信息：" << endl;
for (k = 0; k < e; k++) {
cin >> i >> j; // 这里需要输入对称的边，也就是输入下矩阵或者上矩阵
G.edges[i][j] = G.edges[j][i] = 1;
}
}
// 无向图的深度优先遍历
int visited[MAX_VERTEX_NUM];
void DFS(MGraph &G, int i) {
int j;
cout << G.vexs[i] << " ";
visited[i] = 1;
for (j = 0; j < G.vexnum; j++) {
if (G.edges[i][j] == 1 && visited[j] == 0) {
DFS(G, j);
}
}
}
void DFS_Traverse(MGraph &G) {
int i;
for (i = 0; i < G.vexnum; i++) {
visited[i] = 0;
}
for (i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(G, i);
}
}
}
// 无向图的广度优先遍历
// 循环队列的类型定义
const int Queue_Size = 100;
typedef struct circlQueue {
int *elem;
int rear;
int front;
int queueSize;
}circlQueue;
// 循环队列初始化
void initQueue(circlQueue &Q) {
Q.elem = new int[Queue_Size];
Q.front = Q.rear = 0;
Q.queueSize = Queue_Size;
}
// 入队列
void enterQueue(circlQueue &Q, int x) {
// 栈满
if ((Q.rear + 1) % Q.queueSize == Q.front) {
cout << "Queue OverFlow!" << endl;
}
Q.elem[Q.rear] = x;
Q.rear = (Q.rear + 1) % Q.queueSize;
}
// 出队列
void outputQueue(circlQueue &Q,int &e) {
// 栈空
if (Q.front == Q.rear) {
cout << "Queue Empty!" << endl;
}
e = Q.elem[Q.front];
Q.front = (Q.front + 1) % Q.queueSize;
}
void BFS_Traverse(MGraph &G) {
int v;
for (int i = 0; i < G.vexnum; i++) {
visited[i] = 0;
}
circlQueue Q;
initQueue(Q);
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
cout << G.vexs[i] << " ";
visited[i] = 1;
enterQueue(Q, i);
while (Q.front != Q.rear) {
outputQueue(Q, v);
for (int j = 0; j < G.vexnum; j++) {
// 将当前节点v的全部邻接节点全部访问并入队列
if (G.edges[v][j] && (!visited[j])) {
cout << G.vexs[j] << " ";
visited[j] = 1;
enterQueue(Q, j);
}
}
}
}
}
}
int main() {
MGraph G;
int n, e;
cout << "输入顶点个数：" << endl;
cin >> n;
cout << endl;
cout << "输入边的条数：" << endl;
cin >> e;
cout << endl;
CreateUDG(G, n, e);
cout << "深度优先遍历结果：" << endl;
DFS_Traverse(G);
cout << endl;
cout << "广度优先遍历结果：" << endl;
BFS_Traverse(G);
system("pause");
return 0;
}
