The adjacency table of graph is created

Adjacency table when the graph is sparse , namely Use when the edge is less than the square of the vertex
If it is a weighted network , Then add the corresponding weight field

#include<iostream>
using namespace std;
const int MAX = 20;
typedef char VertexType;// Vertex data type 
// Side table node 
struct EdgeNode 
{
    
	int adjvex;// Store information of other arcs , That is, the subscript of the corresponding vertex 
	EdgeNode* next;// Point to next 
};
// Vertex table node 
typedef struct VertexNode 
{
    
	VertexType data;// Data fields 
	EdgeNode* firstedge;// Pointer to the domain 
}AdjList[MAX];
// chart 
typedef struct Graph
{
    
	AdjList adjlist;// Vertex array 
	int numVertexes, numEdges;// The number of points and the number of edges 
}*GraphAdjList;
void creat(GraphAdjList& g)
{
    
	g = new Graph;// Allocate space 
	int i, j, k;//for Recycle 
	cout << " Enter the number of vertices and edges \n";
	cin >> g->numVertexes >> g->numEdges;
	cout << " Enter vertex information \n";
	for (i = 0; i < g->numVertexes; i++)
	{
    
		cin >> g->adjlist[i].data;
		g->adjlist[i].firstedge = nullptr;// Initial empty 
	}
	// Create side table information 
	cout << " Enter coordinates \n";
	for (k = 0; k < g->numEdges; k++) 
	{
    
		cin >> i >> j;// Represents his coordinates , Subscript from 0 Start 
		EdgeNode* q = new EdgeNode;// The first interpolation , If you use the tail interpolation method, you need to cycle to find the last node 
		q->adjvex = j;// Storage arc head 
		q->next = g->adjlist[i].firstedge;// You can know how to write the head inserting method by drawing and analyzing 
		g->adjlist[i].firstedge = q;
		// When the graph is undirected , Continue with the following operations ; The directed graph is commented out below 
		// Undirected graph symmetric operation <i,j>,<j,i>
		EdgeNode* p = new EdgeNode;
		p->adjvex = i;
		p->next = g->adjlist[j].firstedge;
		g->adjlist[j].firstedge = p;
	}
}

Adjacent to the watch DFS Traverse

The time complexity is O（n+e）, The space complexity is O（n）, That is, the cost of stack
It is similar to the preorder traversal of a tree
It is worth noting that , A graph may be unconnected , One traverse cannot access all vertices , So there's more DFSGraphAdjList Function to ensure that all vertices can be traversed

void DFS(GraphAdjList g, int *visited,int adjvex)
{
    
	if (!g)
		return;
	visited[adjvex] = 1;
	cout << g->adjlist[adjvex].data;
	EdgeNode* p = g->adjlist[adjvex].firstedge;// Get the current vertex pointer 
	while (p)
	{
    
		if (!visited[p->adjvex])// Recursion without access 
			DFS(g,visited, p->adjvex);
		p = p->next;// Otherwise, go to the next adjacent path 
	}
}
void DFSGraphAdjList(GraphAdjList g)
{
    
	int *visited = new int[g->numVertexes];
	for (int i = 0; i < g->numVertexes; i++)// initialization 
		visited[i] = 0;
	for (int i = 0; i < g->numVertexes; i++)// Both connected and disconnected graphs can access 
		if (!visited[i])
			DFS(g, visited, i);
}

Adjacent to the watch BFS Traverse

It is similar to the sequence traversal of trees , You need to complete with the help of queues
Here we manually construct a simple circular queue

void BFS(GraphAdjList g, int* visited,int adjvex)
{
    
	if (!g)
		return;
	int queue[MAX], front=-1, rear=-1;// Construct a circular queue 
	cout << g->adjlist[adjvex].data;
	visited[adjvex] = 1;
	rear = (++rear) % MAX;// If you go out and join the team, you should add yourself first 1 Modulus array maximum , Make the most of space 
	queue[rear] = adjvex;
	while (front != rear)// The queue is not empty 
	{
    
		front = (++front) % MAX;// Leave the team to save 
		int temp = queue[front];
		EdgeNode* q = g->adjlist[temp].firstedge;// Get the current vertex pointer 
		while (q)// Non space-time cycle 
		{
    
			if (!visited[q->adjvex])// If not accessed 
			{
    
				visited[q->adjvex] = 1;// Mark the output and then join the team 
				cout << g->adjlist[q->adjvex].data;
				rear = (++rear) % MAX;
				queue[rear] = q->adjvex;
			}
			q = q->next;// Otherwise, go to the next adjacent path 
		}
	}
}
void BFSGraphAdjList(GraphAdjList g)
{
    
	int* visited = new int[g->numVertexes];
	for (int i = 0; i < g->numVertexes; i++)// initialization 
		visited[i] = 0;
	for (int i = 0; i < g->numVertexes; i++)// Both connected and disconnected graphs can access 
		if (!visited[i])
			BFS(g, visited, i);
}

Complete code

#include<iostream>
using namespace std;
const int MAX = 20;
typedef char VertexType;// Vertex data type 
// Side table node 
struct EdgeNode 
{
    
	int adjvex;// Store information of other arcs , That is, the subscript of the corresponding vertex 
	EdgeNode* next;// Point to next 
};
// Vertex table node 
typedef struct VertexNode 
{
    
	VertexType data;// Data fields 
	EdgeNode* firstedge;// Pointer to the domain 
}AdjList[MAX];
// chart 
typedef struct Graph
{
    
	AdjList adjlist;// Vertex array 
	int numVertexes, numEdges;// The number of points and the number of edges 
}*GraphAdjList;
void creat(GraphAdjList& g)
{
    
	g = new Graph;// Allocate space 
	int i, j, k;//for Recycle 
	cout << " Enter the number of vertices and edges \n";
	cin >> g->numVertexes >> g->numEdges;
	cout << " Enter vertex information \n";
	for (i = 0; i < g->numVertexes; i++)
	{
    
		cin >> g->adjlist[i].data;
		g->adjlist[i].firstedge = nullptr;// Initial empty 
	}
	// Create side table information 
	cout << " Enter coordinates \n";
	for (k = 0; k < g->numEdges; k++) 
	{
    
		cin >> i >> j;// Represents his coordinates , Subscript from 0 Start 
		EdgeNode* q = new EdgeNode;// The first interpolation , If you use the tail interpolation method, you need to cycle to find the last node 
		q->adjvex = j;// Storage arc head 
		q->next = g->adjlist[i].firstedge;// You can know how to write the head inserting method by drawing and analyzing 
		g->adjlist[i].firstedge = q;
		// When the graph is undirected , Continue with the following operations ; The directed graph is commented out below 
		// Undirected graph symmetric operation <i,j>,<j,i>
		EdgeNode* p = new EdgeNode;
		p->adjvex = i;
		p->next = g->adjlist[j].firstedge;
		g->adjlist[j].firstedge = p;
	}
}
void DFS(GraphAdjList g, int *visited,int adjvex)
{
    
	if (!g)
		return;
	visited[adjvex] = 1;
	cout << g->adjlist[adjvex].data;
	EdgeNode* p = g->adjlist[adjvex].firstedge;// Get the current vertex pointer 
	while (p)
	{
    
		if (!visited[p->adjvex])// Recursion without access 
			DFS(g,visited, p->adjvex);
		p = p->next;// Otherwise, go to the next adjacent path 
	}
}
void DFSGraphAdjList(GraphAdjList g)
{
    
	int *visited = new int[g->numVertexes];
	for (int i = 0; i < g->numVertexes; i++)// initialization 
		visited[i] = 0;
	for (int i = 0; i < g->numVertexes; i++)// Both connected and disconnected graphs can access 
		if (!visited[i])
			DFS(g, visited, i);
}
void BFS(GraphAdjList g, int* visited,int adjvex)
{
    
	if (!g)
		return;
	int queue[MAX], front=-1, rear=-1;// Construct a circular queue 
	cout << g->adjlist[adjvex].data;
	visited[adjvex] = 1;
	rear = (++rear) % MAX;// If you go out and join the team, you should add yourself first 1 Modulus array maximum , Make the most of space 
	queue[rear] = adjvex;
	while (front != rear)// The queue is not empty 
	{
    
		front = (++front) % MAX;// Leave the team to save 
		int temp = queue[front];
		EdgeNode* q = g->adjlist[temp].firstedge;// Get the current vertex pointer 
		while (q)// Non space-time cycle 
		{
    
			if (!visited[q->adjvex])// If not accessed 
			{
    
				visited[q->adjvex] = 1;// Mark the output and then join the team 
				cout << g->adjlist[q->adjvex].data;
				rear = (++rear) % MAX;
				queue[rear] = q->adjvex;
			}
			q = q->next;// Otherwise, go to the next adjacent path 
		}
	}
}
void BFSGraphAdjList(GraphAdjList g)
{
    
	int* visited = new int[g->numVertexes];
	for (int i = 0; i < g->numVertexes; i++)// initialization 
		visited[i] = 0;
	for (int i = 0; i < g->numVertexes; i++)// Both connected and disconnected graphs can access 
		if (!visited[i])
			BFS(g, visited, i);
}
// Output the information of adjacency table 
void printf_adjlist(GraphAdjList g) 
{
    
	EdgeNode* q;
	for (int i = 0; i < g->numVertexes; i++) {
    
		q = g->adjlist[i].firstedge;// Point to the head node 
		while (q) {
    
			cout << "<" << g->adjlist[i].data << "," << g->adjlist[q->adjvex].data << ">";
			q = q->next;
		}
	}
}
int main( ) 
{
    
	GraphAdjList g;
	creat(g);
	printf_adjlist(g);
	cout << "\nDFS:";
	DFSGraphAdjList(g);
	cout << "\nBFS:";
	BFSGraphAdjList(g);
	return 0;
}

Test data

Subscript from 0 Start , The mark in the figure is neglected