图的广度优先伪代码实现-c++
2021/9/26 20:11:32
本文主要是介绍图的广度优先伪代码实现-c++,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
/* 图的广度优先算法(邻接矩阵的存储结构,无权图): 1. 算法思想: 1. 访问顶点 2. visited[i]置为true 3. 入队 4. - 出队 - 访问所有的邻接顶点,置true,入队,重复步骤4 2. 回顾循环队列: 1. 基本的结构: - 为了便于区分 front = rear是表示当前队列是满的还是空的,使用了带有一个空位置的队列 2. 队列满的条件: - (rear + 1) / maxsize == front; 3. 队列空的条件: - frint == raer; */ # include<iostream> # include<string> using namespace std; # define MAX 30 bool visited[MAX]; int queue[MAX - 1]; struct Matrix{ char vex[MAX]; int arc[MAX][MAX]; int vexnum, arcnum; }; struct Queue{ int element[MAX]; int front; int rear; }; void initQueue(Queue * q){ q->front = q->rear=0; return; } int enterQueue(Queue * q, int x){ if ((q->rear + 1) % MAX == q->front) return false; q->element[q->rear] = x; q->rear = (q->rear + 1) % MAX; return true; } int isEmptyQueue(Queue q){ if (q.front == q.rear) return false; else return true; } int deleteQueue(Queue * q, int * x){ if (q->rear == q->front) return false; * x = q->element[q->front]; q->front = (q->front + 1) % MAX; return true; } int location(Matrix * g, char data){ for (int i = 0; i < g->vexnum; i++){ if (g->vex[i] == data) return i; } return -1; } void createMatrix(Matrix * g){ char data1, data2; cout << "请输入顶点数和边数:" << endl; cin >> g -> vexnum >> g -> arcnum; cout << "请输入各个顶点的值: "; for(int i = 0; i < g -> vexnum; i++) cin >> g -> vex[i]; for (int k = 0; k < g -> arcnum; k++){ cout << "请输入第" << k + 1 << "条边的值: " << endl; cin >> data1 >> data2; int i = location(g, data1); int j = location(g, data2); if (i != -1 && j != -1){ g -> arc[i][j] = 1; g -> arc[j][i] = 1; }else{ cout << "输入有误,请重新输入"; } } return; } int firstAdjNode(Matrix g, int x){ for (int i = 0; i < g.vexnum; i++){ if(g.arc[x][i] != 0){ return i; } } return -1; } int nextAdjNode(Matrix g, int x, int w){ for (int i = w + 1; i < g.vexnum; i++){ if (g.arc[x][i] != 0){ return i; } } return -1; } void breadthSearch(Matrix g, int i){ int x; Queue q; q.front = q.rear = 0; cout << g.vex[i] << endl; visited[i] = true; enterQueue(&q, i); while (isEmptyQueue(q)){ deleteQueue(&q, &x); int w = firstAdjNode(g, x); while (w != -1){ if (visited[w] == false){ cout << g.vex[w] << endl; visited[w] = true; enterQueue(&q, w); } w = nextAdjNode(g, x, w); } } return; } void tranverseGraph(Matrix g){ for (int i = 0; i < MAX; i++) visited[i] = false; for(int i = 0; i < g.vexnum; i++){ if (!visited[i]) breadthSearch(g, i); } return; } int main(){ Matrix m; for (int i = 0; i < MAX; i++) for (int j = 0; j < MAX; j++) m.arc[i][j] = 0; createMatrix(&m); for (int i = 0; i < m.vexnum; i++){ for (int j = 0; j < m.vexnum; j++) cout << m.arc[i][j] << " "; cout << endl; } cout << "---------------------------------" << endl; tranverseGraph(m); return 0; }
这篇关于图的广度优先伪代码实现-c++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28pyqt 怎么打包整个项目-icode9专业技术文章分享
- 2024-09-28laravel Commands 创建带有参数的 Artisan 命令的步骤和示例-icode9专业技术文章分享
- 2024-09-28antd怎么实现渲染tiff图片-icode9专业技术文章分享
- 2024-09-28英文半角中划线和中文全角的中划线有什么区别-icode9专业技术文章分享
- 2024-09-28nvm npm 和node 他们之间有什么关系-icode9专业技术文章分享
- 2024-09-28Node Version Manager (nvm)使用教程-icode9专业技术文章分享
- 2024-09-28nvm命令太慢,是什么原因-icode9专业技术文章分享
- 2024-09-28Kotlin 如何增加、删除和修改 MutableStateFlow 中的值。-icode9专业技术文章分享
- 2024-09-28Kotlin的stateFlow.update 写法介绍-icode9专业技术文章分享
- 2024-09-28kotlin 怎么获取当前时间格式-icode9专业技术文章分享