Basic concepts

A graph is a set of N vertices and M edges. Graphs are divided into directed graphs and undirected graphs. If a direction is specified for each edge of a graph, the resulting graph is called a directed graph, and other edges are also called directed edges. In a directed graph, the edge associated with a point can be divided into an outgoing edge and an incoming edge, and the two points associated with a directed edge can also be divided into a starting point and an ending point. A graph whose edges have no direction is called an undirected graph. Adjacency matrix is used to store graphs.

Main ideas

The first is depth first traversal. Its main idea is:

First, take an unreachable vertex as the starting vertex and walk along the edge of the current vertex to the unreachable vertex; When there is no vertex that has not been visited, return to the previous vertex and continue to explore other vertices until all vertices have been visited. That is, traverse along a branch of the graph to the end, then backtrack, and then traverse the same along another branch until all vertices are accessed.

Then comes breadth first traversal. Its main idea is:

First, take an unreachable vertex as the starting vertex to access all its adjacent vertices, and then for each adjacent vertex, access their adjacent unreachable vertices until all vertices have been accessed, and the traversal ends.

actual combat

Example 1 - wide depth first traversal of undirected graphs

The adjacency matrix is used to store the graph, and the depth first traversal and breadth first traversal graphs are used respectively.

Code implementation:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b; //n is the point and m is the edge 
int e[51][51],book[51];
int ans;
void dfs(int cur)
{
	printf("%d ",cur);
	ans++;
	if(ans==5) return;
	for(int i=1;i<=n;i++){
		if(e[cur][i]==1&&book[i]==0){
			book[i]=1;
			dfs(i);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
			else e[i][j]=99999999;
		}
	} 
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		e[a][b]=1;
		e[b][a]=1;
	}
	
	book[1]=1;
	dfs(1);
	
	return 0;
}

Code implementation:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,head=1,tail=1;
int e[51][51],book[51],que[2501];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
			else e[i][j]=99999999;
		}
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		e[a][b]=1;
		e[b][a]=1;
	}
	
	que[tail]=1;
	book[que[tail]]=1;
	tail++;
	
	while(head<tail){
		
		int	cur=que[head];
		for(int i=1;i<=n;i++){
			if(e[cur][i]==1&&book[i]==0){
				book[i]=1;
				que[tail]=i;
				tail++;
			}
		}
		
		head++;
		
		if(tail>n) break;
	}
	
	for(int i=1;i<tail;i++){
		printf("%d ",que[i]);
	}
	return 0;
}

Example 2 - depth first traversal of directed graph (city map)

Code implementation:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,c;
int e[51][51],book[51];
int mi=99999999,ans;
void dfs(int cur)
{
	if(cur==n){
//		printf("%d\n",ans);
		if(mi>ans) mi=ans;
		return;
	}
	for(int i=1;i<=n;i++){
		if(e[cur][i]!=0&&e[cur][i]!=99999999&&book[i]==0){
			book[i]=1;
			ans+=e[cur][i];
			dfs(i);
			book[i]=0;
			ans-=e[cur][i];
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
			else e[i][j]=99999999;
		}
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		e[a][b]=c;
	}
	
	book[1]=1;
	dfs(1);
	printf("%d",mi);
	return 0;
}

/*
5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3
9
*/ 

Example 3 – minimum turnaround

The first is depth first traversal. The code implementation is as follows:

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,p,q;
int e[51][51],book[51];
int mi=99999999,ans;

void dfs(int cur)
{
	if(cur==q){
		if(mi>ans) mi=ans;
		return;
	}
	for(int i=1;i<=n;i++){
		if(e[cur][i]==1&&book[i]==0){
			book[i]=1;
			ans++;
			dfs(i);
			ans--;
			book[i]=0;
		}
	}
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&p,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
			else e[i][j]=99999999;
		}
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		e[a][b]=1;
		e[b][a]=1;
	}
	
	book[1]=1;
	dfs(p);
	
	printf("%d",mi);
	return 0;
}

Then breadth first traversal, code implementation:

#include<bits/stdc++.h>
using namespace std;
int n,m,p,q;
int a,b,head=1,tail=1,flag;
int e[51][51],book[51];
struct note{
	int x;
	int step;
}que[2501];
int main()
{
	scanf("%d%d%d%d",&n,&m,&p,&q);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(i==j) e[i][j]=0;
			else e[i][j]=99999999;
		}
	}
	
	for(int i=1;i<=m;i++){
		scanf("%d%d",&a,&b);
		e[a][b]=1;
		e[b][a]=1;
	}
	
	que[tail].x=p;
	book[que[tail].x]=1;
	que[tail].step=0;
	tail++;
	
	while(head<tail){
		
		
		for(int i=1;i<=n;i++){
			
			if(e[que[head].x][i]==1&&book[i]==0){
				book[i]=1;
				que[tail].x=i;
				que[tail].step=que[head].step+1;
				tail++;
			}
			
			if(que[tail-1].x==q){
				flag=1;
				break;
			}
		}
		if(flag) break;
		head++;
	}
	printf("%d",que[tail-1].step);
	return 0;
}

Well, this is the official introduction to graph theory!