BFS realizes breadth first traversal of adjacency matrix (with examples)

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