基于线性表邻接矩阵结构的图的深度/广度优先搜索算法

// 图的存储和遍历

#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;

}

基于线性表邻接矩阵结构的图的深度/广度优先搜索算法

相关推荐