Depth first DFS and breadth first BFS -- traversing adjacency tables

1. Creation of adjacency table

#include<iostream>
using namespace std;
#include<queue>
#define MAXVEX 100
// Creation of adjacency table 
typedef char vextype;// Custom vertex type 
typedef int edgetype;// Customize the weight on the edge 
// Side table node 
typedef struct EdgeNode
{
    
	int index;// Save the subscript corresponding to the vertex 
	edgetype val;// Store weights 
	struct EdgeNode* next;// The chain domain that points to the next critical point 
}EdgeNode;

// Vertex table node 
typedef struct VexNode
{
    
	vextype data;// Store vertex information 
	EdgeNode* firstNode;// Side header pointer 
}VexNode,AList[MAXVEX];
// The graph structure 
typedef struct
{
    
	AList Datas;// Equivalent to an array of structures ,
	int numNodes;// Number of vertices in the graph 
	int numEdges;// The number of edges in a graph 
}MGraph;

1. Pointer to establish the adjacency table structure in the graph

//1. Pointer to establish the adjacency table structure in the graph 
void CreatGraph(MGraph* G)
{
    
	EdgeNode* p;
	cout << " Please enter the number of vertices and edges ：";
	cin >> G->numNodes >> G->numEdges;
	cout << " Please enter the data of all vertices ：" << endl;
	for (int i = 0; i < G->numNodes; i++)// Read in vertex information , Create side tables 
	{
    
		cin >> G->Datas[i].data;
		G->Datas[i].firstNode = NULL;
	}
	cout << " Please enter all edges （v1,v2） The sequence number of the top vertex ：" << endl;
	for (int k = 0; k < G->numEdges; k++)
	{
    
		int m, n;
		cin >> m >> n;
		// The degree of 
		p = new EdgeNode;
		p->index = n;
		p->next = G->Datas[m].firstNode;
		G->Datas[m].firstNode = p;
		// The degree of 
		p = new EdgeNode;
		p->index = m;
		p->next = G->Datas[n].firstNode;
		G->Datas[n].firstNode = p;
	}
}

2. Reference to establish the adjacency table structure in the graph

//2. Reference to establish the adjacency table structure in the graph 
void CreatGraph(MGraph &G)
{
    
	EdgeNode* p;
	cout << " Please enter the number of vertices and edges ：";
	cin >> G.numNodes >> G.numEdges;
	cout << " Please enter the data of all vertices ：" << endl;
	for (int i = 0; i < G.numNodes; i++)// Read in vertex information , Create side tables 
	{
    
		cin >> G.Datas[i].data;
		G.Datas[i].firstNode = NULL;
	}
	cout << " Please enter all edges （v1,v2） The sequence number of the top vertex ：" << endl;
	for (int k = 0; k < G.numEdges; k++)
	{
    
		int m, n;
		cin >> m >> n;
		// The degree of 
		p = new EdgeNode;
		p->index = n;
		p->next = G.Datas[m].firstNode;
		G.Datas[m].firstNode = p;
		// The degree of 
		p = new EdgeNode;
		p->index = m;
		p->next = G.Datas[n].firstNode;
		G.Datas[n].firstNode = p;
	}
}

2. Depth first traversal algorithm of adjacency table

//3. Depth first traversal algorithm of adjacency table 
int visit[MAXVEX] = {
     0 };
void DFS(MGraph G,int i)
{
    
	EdgeNode* p;
	visit[i] = 1;
	cout << G.Datas[i].data << " ";
	p = G.Datas[i].firstNode;
	while (p)
	{
    
		if (!visit[p->index])
			DFS(G, p->index);
		p = p->next;
	}
}
void DFST(MGraph G)
{
    
	for (int i = 0; i < G.numNodes; i++)
		visit[i] = 0;
	for (int i = 0; i < G.numNodes; i++)
		if (!visit[i])
			DFS(G, i);
}

3. Breadth first traversal algorithm of adjacency table

// 4. Breadth first traversal algorithm of adjacency table 
void BFS(MGraph G)
{
    
	queue<vextype>Q;
	EdgeNode* p;
	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.Datas[i].data<<" ";// Print vertex 
			Q.push(i);
			while (!Q.empty())
			{
    
				Q.pop();
				p = G.Datas[i].firstNode;// Find the header pointer of the edge linked list of the current vertex 
				while (p)
				{
    
					if (!visit[p->index])// If this vertex is not accessed 
					{
    
						visit[p->index] = 1;
						cout << G.Datas[p->index].data<<" ";
						Q.push(p->index);
					}
					p = p->next;
				}
			}
		}
	}
}

4. Test cases

#include<iostream>
using namespace std;
#include<queue>
#define MAXVEX 100
// Creation of adjacency table 
typedef char vextype;// Custom vertex type 
typedef int edgetype;// Customize the weight on the edge 
// Side table node 
typedef struct EdgeNode
{
    
	int index;// Save the subscript corresponding to the vertex 
	edgetype val;// Store weights 
	struct EdgeNode* next;// The chain domain that points to the next critical point 
}EdgeNode;

// Vertex table node 
typedef struct VexNode
{
    
	vextype data;// Store vertex information 
	EdgeNode* firstNode;// Side header pointer 
}VexNode,AList[MAXVEX];
// The graph structure 
typedef struct
{
    
	AList Datas;// Equivalent to an array of structures ,
	int numNodes;// Number of vertices in the graph 
	int numEdges;// The number of edges in a graph 
}MGraph;

//1. Pointer to establish the adjacency table structure in the graph 
/*void CreatGraph(MGraph* G) { EdgeNode* p; cout << " Please enter the number of vertices and edges ："; cin >> G->numNodes >> G->numEdges; cout << " Please enter the data of all vertices ：" << endl; for (int i = 0; i < G->numNodes; i++)// Read in vertex information , Create side tables  { cin >> G->Datas[i].data; G->Datas[i].firstNode = NULL; } cout << " Please enter all edges （v1,v2） The sequence number of the top vertex ：" << endl; for (int k = 0; k < G->numEdges; k++) { int m, n; cin >> m >> n; // The degree of  p = new EdgeNode; p->index = n; p->next = G->Datas[m].firstNode; G->Datas[m].firstNode = p; // The degree of  p = new EdgeNode; p->index = m; p->next = G->Datas[n].firstNode; G->Datas[n].firstNode = p; } }*/
//2. Reference to establish the adjacency table structure in the graph 
void CreatGraph(MGraph &G)
{
    
	EdgeNode* p;
	cout << " Please enter the number of vertices and edges ：";
	cin >> G.numNodes >> G.numEdges;
	cout << " Please enter the data of all vertices ：" << endl;
	for (int i = 0; i < G.numNodes; i++)// Read in vertex information , Create side tables 
	{
    
		cin >> G.Datas[i].data;
		G.Datas[i].firstNode = NULL;
	}
	cout << " Please enter all edges （v1,v2） The sequence number of the top vertex ：" << endl;
	for (int k = 0; k < G.numEdges; k++)
	{
    
		int m, n;
		cin >> m >> n;
		// The degree of 
		p = new EdgeNode;
		p->index = n;
		p->next = G.Datas[m].firstNode;
		G.Datas[m].firstNode = p;
		// The degree of 
		p = new EdgeNode;
		p->index = m;
		p->next = G.Datas[n].firstNode;
		G.Datas[n].firstNode = p;
	}
}
//3. Depth first traversal algorithm of adjacency table 
int visit[MAXVEX] = {
     0 };
void DFS(MGraph G,int i)
{
    
	EdgeNode* p;
	visit[i] = 1;
	cout << G.Datas[i].data << " ";
	p = G.Datas[i].firstNode;
	while (p)
	{
    
		if (!visit[p->index])
			DFS(G, p->index);
		p = p->next;
	}
}
void DFST(MGraph G)
{
    
	for (int i = 0; i < G.numNodes; i++)
		visit[i] = 0;
	for (int i = 0; i < G.numNodes; i++)
		if (!visit[i])
			DFS(G, i);
}
// 4. Breadth first traversal algorithm of adjacency table 
void BFS(MGraph G)
{
    
	queue<vextype>Q;
	EdgeNode* p;
	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.Datas[i].data<<" ";// Print vertex 
			Q.push(i);
			while (!Q.empty())
			{
    
				Q.pop();
				p = G.Datas[i].firstNode;// Find the header pointer of the edge linked list of the current vertex 
				while (p)
				{
    
					if (!visit[p->index])// If this vertex is not accessed 
					{
    
						visit[p->index] = 1;
						cout << G.Datas[p->index].data<<" ";
						Q.push(p->index);
					}
					p = p->next;
				}
			}
		}
	}
}
int main()
{
    
	MGraph G;
	CreatGraph(G);
	cout << " The depth first traversal result of the adjacency table ：" << endl;
	DFST(G);
	cout << "\n The breadth first traversal result of the adjacency table ：" << endl;
	BFS(G);
}

test result