当前位置:网站首页>BFS realizes breadth first traversal of adjacency matrix (with examples)
BFS realizes breadth first traversal of adjacency matrix (with examples)
2022-07-07 00:59:00 【Demo Dragon】
1. The establishment of adjacency matrix
#include<iostream>
using namespace std;
#include<queue>
#include<stdbool.h>
// Creation of adjacency matrix
typedef char vextype;// Vertex type customization
typedef int edgetype;// Custom weights on the edge
#define MAXVEX 100// Maximum number of vertices
#define MAXS 66666// Represents infinity
typedef struct
{
vextype vexs[MAXVEX];// Vertex table
edgetype arc[MAXVEX][MAXVEX];// Adjacency matrix
int numNodes;// Current number of vertices
int numEdges;// Current number of sides
}MGraph;
1. The adjacency matrix representation of undirected network graph is established by reference
//1. The adjacency matrix representation of undirected network graph is established by reference
void CreatGraph(MGraph& G)
{
cout << " Please enter the number of vertices and edges :";
cin >> G.numNodes >> G.numEdges;
cout << " Please enter all vertex information :" << endl;
for (int i = 0; i < G.numNodes; i++)
cin >> G.vexs[i];
for (int i = 0; i < G.numNodes; i++)
for (int j = 0; j < G.numNodes; j++)
G.arc[i][j] = 0;
cout << " Please enter the edges composed of vertices and their weights :" << endl;
for (int i = 0; i < G.numEdges; i++)
{
int w, m, n;
cin >> m >> n >> w;
G.arc[m][n] = w;
G.arc[n][m] = G.arc[m][n];
}
}
2. The pointer establishes the adjacency matrix representation of undirected network graph
//2. The pointer establishes the adjacency matrix representation of undirected network graph
void CreatGraph(MGraph* G)
{
cout << " Please enter the number of vertices and edges :";
cin >> G->numNodes >> G->numEdges;
cout << " Please enter all vertex information :" << endl;
for (int i = 0; i < G->numNodes; i++)
cin>>G->vexs[i];
for (int i = 0; i < G->numNodes; i++)
for (int j = 0; j < G->numNodes; j++)
G->arc[i][j] = 0;
cout << " Please enter the edges composed of vertices and their weights :" << endl;
for (int i = 0; i < G->numEdges; i++)
{
int w, m, n;
cin >> m >> n >> w;
G->arc[m][n] = w;
G->arc[n][m] = G->arc[m][n];
}
}
2. Print adjacency matrix
// Print adjacency matrix
void PrintGraph(MGraph G)
{
int len = G.numNodes;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
cout << G.arc[i][j] << " ";
}
cout << endl;
}
}
3. Depth first recursive algorithm of adjacency matrix
//3. Depth first recursive algorithm of adjacency matrix
#define MAXVEX 100
int visit[MAXVEX] = {
0 };
void DFS(MGraph G, int i)
{
cout << G.vexs[i] << " ";
visit[i] = 1;
for (int j = 0; j < G.numNodes; j++)
{
if (!visit[j] && G.arc[i][j] != 0)
{
DFS(G, j);
}
}
}
void DFST(MGraph G)
{
for (int i = 0; i < G.numNodes; i++)
visit[i] = 0;
for (int i = 1; i < G.numNodes; i++)
{
if(!visit[i])
DFS(G, i);
}
}
4. Breadth first traversal algorithm of adjacency matrix
// Breadth first traversal algorithm of adjacency matrix
void BFS(MGraph G)
{
queue<vextype> Q;
for (int i = 0; i < G.numNodes; i++)
visit[i] = 0;
for (int i = 0; i < G.numNodes; i++){
if (!visit[i]){
visit[i] = 1;
cout << G.vexs[i] << " ";
Q.push(i);
while (!Q.empty()){
Q.pop();
for (int j = 0; j < G.numNodes; j++)
if (G.arc[i][j] != 0 && visit[j] == 0){
visit[j] = 1;
cout << G.vexs[j] << " ";
Q.push(j);
}
}
}
}
}
5. Test case
#include<iostream>
using namespace std;
#include<queue>
#include<stdbool.h>
// Creation of adjacency matrix
typedef char vextype;// Vertex type customization
typedef int edgetype;// Custom weights on the edge
#define MAXVEX 100// Maximum number of vertices
#define MAXS 66666// Represents infinity
typedef struct
{
vextype vexs[MAXVEX];// Vertex table
edgetype arc[MAXVEX][MAXVEX];// Adjacency matrix
int numNodes;// Current number of vertices
int numEdges;// Current number of sides
}MGraph;
//1. The adjacency matrix representation of undirected network graph is established by reference
void CreatGraph(MGraph& G)
{
cout << " Please enter the number of vertices and edges :";
cin >> G.numNodes >> G.numEdges;
cout << " Please enter all vertex information :" << endl;
for (int i = 0; i < G.numNodes; i++)
cin >> G.vexs[i];
for (int i = 0; i < G.numNodes; i++)
for (int j = 0; j < G.numNodes; j++)
G.arc[i][j] = 0;
cout << " Please enter the edges composed of vertices and their weights :" << endl;
for (int i = 0; i < G.numEdges; i++)
{
int w, m, n;
cin >> m >> n >> w;
G.arc[m][n] = w;
G.arc[n][m] = G.arc[m][n];
}
}
//2. The pointer establishes the adjacency matrix representation of undirected network graph
/*void CreatGraph(MGraph* G) { cout << " Please enter the number of vertices and edges :"; cin >> G->numNodes >> G->numEdges; cout << " Please enter all vertex information :" << endl; for (int i = 0; i < G->numNodes; i++) cin>>G->vexs[i]; for (int i = 0; i < G->numNodes; i++) for (int j = 0; j < G->numNodes; j++) G->arc[i][j] = 0; cout << " Please enter the edges composed of vertices and their weights :" << endl; for (int i = 0; i < G->numEdges; i++) { int w, m, n; cin >> m >> n >> w; G->arc[m][n] = w; G->arc[n][m] = G->arc[m][n]; } }*/
//3. Depth first recursive algorithm of adjacency matrix
#define MAXVEX 100
int visit[MAXVEX] = {
0 };
void DFS(MGraph G, int i)
{
cout << G.vexs[i] << " ";
visit[i] = 1;
for (int j = 0; j < G.numNodes; j++)
{
if (!visit[j] && G.arc[i][j] != 0)
{
DFS(G, j);
}
}
}
void DFST(MGraph G)
{
for (int i = 0; i < G.numNodes; i++)
visit[i] = 0;
for (int i = 1; i < G.numNodes; i++)
{
if(!visit[i])
DFS(G, i);
}
}
// Print adjacency matrix
void PrintGraph(MGraph G)
{
int len = G.numNodes;
for (int i = 0; i < len; i++)
{
for (int j = 0; j < len; j++)
{
cout << G.arc[i][j] << " ";
}
cout << endl;
}
}
// Breadth first traversal algorithm of adjacency matrix
void BFS(MGraph G)
{
queue<vextype> Q;
for (int i = 0; i < G.numNodes; i++)
visit[i] = 0;
for (int i = 0; i < G.numNodes; i++)
{
if (!visit[i])
{
visit[i] = 1;
cout << G.vexs[i] << " ";
Q.push(i);
while (!Q.empty()){
Q.pop();
for (int j = 0; j < G.numNodes; j++)
if (G.arc[i][j] != 0 && visit[j] == 0)
{
visit[j] = 1;
cout << G.vexs[j] << " ";
Q.push(j);
}
}
}
}
}
int main()
{
MGraph G;
CreatGraph(G);
cout << " Print adjacency matrix " << endl;
PrintGraph(G);
cout << " The depth first traversal result of the adjacency matrix is :" << endl;
DFST(G);
cout << "\n The breadth first traversal result of the adjacency matrix is :" << endl;
BFS(G);
}
test result
边栏推荐
- 【批处理DOS-CMD命令-汇总和小结】-字符串搜索、查找、筛选命令(find、findstr),Find和findstr的区别和辨析
- Notes of training courses selected by Massey school
- Dr selection of OSPF configuration for Huawei devices
- 用tkinter做一个简单图形界面
- paddlehub应用出现paddle包报错的问题
- Attention slam: a visual monocular slam that learns from human attention
- ZYNQ移植uCOSIII
- 深度学习框架TF安装
- Batch obtain the latitude coordinates of all administrative regions in China (to the county level)
- Distributed cache
猜你喜欢
equals()与hashCode()
Summary of being a microservice R & D Engineer in the past year
第七篇,STM32串口通信编程
Mujoco Jacobi - inverse motion - sensor
Activereportsjs 3.1 Chinese version | | | activereportsjs 3.1 English version
批量获取中国所有行政区域经边界纬度坐标(到县区级别)
.class文件的字节码结构
Threejs image deformation enlarge full screen animation JS special effect
Attention slam: a visual monocular slam that learns from human attention
alexnet实验偶遇:loss nan, train acc 0.100, test acc 0.100情况
随机推荐
【软件逆向-自动化】逆向工具大全
Basic information of mujoco
Levels - UE5中的暴雨效果
详解OpenCV的矩阵规范化函数normalize()【范围化矩阵的范数或值范围(归一化处理)】,并附NORM_MINMAX情况下的示例代码
JS+SVG爱心扩散动画js特效
Installation and testing of pyflink
做微服务研发工程师的一年来的总结
Deeply explore the compilation and pile insertion technology (IV. ASM exploration)
Return to blowing marshland -- travel notes of zhailidong, founder of duanzhitang
Five different code similarity detection and the development trend of code similarity detection
接口(接口相关含义,区别抽象类,接口回调)
[software reverse automation] complete collection of reverse tools
Explain in detail the matrix normalization function normalize() of OpenCV [norm or value range of the scoped matrix (normalization)], and attach norm_ Example code in the case of minmax
A brief history of deep learning (I)
ZABBIX 5.0: automatically monitor Alibaba cloud RDS through LLD
【JVM调优实战100例】05——方法区调优实战(下)
View remote test data and records anytime, anywhere -- ipehub2 and ipemotion app
. Bytecode structure of class file
【JokerのZYNQ7020】AXI_ EMC。
[牛客] [NOIP2015]跳石头