Graph traversal DFS, BFS (code explanation)

Preface

         Hello everyone , Today we bring you the algorithm of graph traversal ,DFS( Depth-first traversal ),BFS( Breadth first traversal ). These two algorithms are relatively important and commonly used , But the implementation in the figure is only the most basic operation , If you want to master it completely , Still need to practice more questions . Link to relevant topics Click here to brush algorithm related topics

Catalog

Preface

Definition of graph

Related terms of graphs

  The creation of a figure ( Adjacency matrix )--- Structure

   The creation of a figure ( Adjacency matrix )--- Creation of adjacency matrix

The creation of a figure ( Adjacency list )--- Structure

  The creation of a figure ( Adjacency list )--- Creation of adjacency table

  Depth first traversal of adjacency matrix

   Breadth first traversal of adjacency matrix

Depth first traversal of the adjacency table  

  Breadth first traversal of adjacency table  

The overall code

Result display

Conclusion

Definition of graph

         The picture consists of Vertex set V(G) and Side set E(G) form , Write it down as G=(V,E). among E(G) It's a finite set of edges , Edges are unordered pairs of vertices （ Undirected graph ） Or orderly to （ Directed graph ）. For digraphs ,E(G) It's a directed edge （ Also called arc (Arc)） The finite set of , Arcs are ordered pairs of vertices , Write it down as <v,w>,v、w Is the vertex. ,v For the arc tail （ Arrow root ）,w For the arc head （ At the arrow ）. For undirected graphs ,E(G) It's a finite set of edges , Edges are unordered pairs of vertices , Write it down as (v, w) perhaps (w, v), also (v, w)=(w,v).

Related terms of graphs

① The vertices (Vertex)： The data elements in the diagram .

② The vertices v Degree ： And v Number of sides associated ;

③ The vertices v The degree of ： With v Is the number of directed edges at the starting point ;

④ The vertices v The degree of ： With v Is the number of directed edges at the end .

⑤ edge ： The logical relationship between vertices is represented by edges , Edge sets can be empty .

⑥ No to the edge (Edge)： If the summit V1 To V2 The edge between has no direction , We call this edge undirected .

⑦ Undirected graph (Undirected graphs)： The edge between any two vertices in a graph is undirected .（A,D）=（D,A）

⑧ There is a directional side ： If from the top V1 To V2 There's a direction on the side of , We call this side a directed side , Also called arc (Arc). use <V1,V2> Express ,V1 For fox tail (Tail),V2 For the arc head (Head).（V1,V2）≠（V2,V1）.

⑨ Directed graph (Directed graphs)： The edge between any two vertices in a graph is a directed edge .

                              Be careful ： It's used without direction “（）”, And there is a way to use “< >” Express .

⑩ Simple picture ： There is no edge from a vertex to itself in a graph , And the same edge does not appear repeatedly .

⑪ Undirected complete graph ： In the undirected graph , There are edges between any two vertices .

⑫ Directed complete graph ： In the directed graph , There are two arcs with opposite directions between any two vertices .

⑬ Sparse graph ： There are very few edges .

⑭ A dense picture ： There are many sides .

⑮ power （Weight）： The number related to the edge or arc of a graph .

⑯ network （Network）： Weighted graphs .

⑰ Connected graph ： Any two vertices in a graph are connected .

⑱ The picture of Tongzi in polar Dalian ： The subgraph is G Connected subgraphs , take G Any vertex of the subgraph that does not join , Subgraphs will no longer be connected .

⑲ Minimal connected subgraph ： The subgraph is G Connected subgraphs of , Delete any edge in the subgraph , Subgraphs will no longer be connected .

  The creation of a figure ( Adjacency matrix )--- Structure

typedef struct
{
	// Used to store vertices 
	int vexs[MAX];
	// Two dimensional array ： Used to store the relationship between two points 
	int arcs[MAX][MAX];
	// The number of vertices and edges of a graph 
	int vexsum, arcsnum;
}AMGraph,*StrAMGraph;

   The creation of a figure ( Adjacency matrix )--- Creation of adjacency matrix

int locate(AMGraph&G, int n)
{
	for (int i = 0; i < G.vexsum; i++)
	{
		if (G.vexs[i] == n)
		{
			return i;
		}
	}
}

// Create an adjacency matrix 
void Creat(AMGraph&G)
{
	int v1 = 0, v2 = 0, w = 0;
	cin >> G.vexsum >> G.arcsnum;
	for (int i = 0; i < G.vexsum; i++)
	{
		cin >> G.vexs[i];
	}
	for (int i = 0; i < G.vexsum; i++)
	{
		for (int j = 0; j < G.vexsum; j++)
		{
			G.arcs[i][j] = 0;
		}
	}
	for (int k = 0; k < G.arcsnum; k++)
	{
		cin >> v1 >> v2 >> w;
		int i = locate(G, v1);
		int j = locate(G, v2);
		G.arcs[i][j] = w;
	}
}

The creation of a figure ( Adjacency list )--- Structure

typedef struct ArcNode
{
	int Adjust;
	struct ArcNode *next;
}AcrNode,*StrAcrNode;


typedef struct
{
	int data;
	StrAcrNode next;
}HeadNode, *StrHeadNode;


typedef struct 
{
	HeadNode arr[MAX];
	int acsrnum, vexsnum;
}ALGraph, *StrALGraph;

  The creation of a figure ( Adjacency list )--- Creation of adjacency table

int locate1(ALGraph&G, int n)
{
	for (int i = 0; i < G.vexsnum; i++)
	{
		if (G.arr[i].data == n)
		{
			return i;
		}
	}
}

void CreatALGraph(ALGraph&G)
{
	int v1 = 0, v2 = 0, w = 0;
	cin >> G.vexsnum >> G.acsrnum;
	for (int i = 0; i < G.vexsnum; i++)
	{
		cin >> G.arr[i].data;
		G.arr[i].next = NULL;
	}
	for (int k = 0; k < G.acsrnum; k++)
	{
		cin >> v1 >> v2;
		int i = locate1(G, v1);
		int j = locate1(G, v2);
		StrAcrNode p1;
		p1 = new AcrNode;
		p1->next = G.arr[i].next;
	}
}

  Depth first traversal of adjacency matrix

// Depth first traversal of adjacency matrix 
void DFS(AMGraph&G, int n)
{
	cout << G.vexs[n] << " ";
	visit[n] = 1;
	for (int i = 0; i < G.vexsum; i++)
	{
		if (G.arcs[n][i] != 1 && visit[i] != 1)
		{
			DFS(G, G.arcs[n][i]);
		}
	}
}

   Breadth first traversal of adjacency matrix

queue<int> qu;
// Breadth first traversal of adjacency matrix 
void BFS(AMGraph&G, int n)
{
	cout << G.vexs[n] << " ";
	qu.push(n);
	while (!qu.empty())
	{
		int m = qu.front();
		qu.pop();
		for (int i = 0; i < G.vexsum; i++)
		{
			if (visit[i] != 1 && G.arcs[m][i] != 1)
			{
				cout << G.vexs[i] << " ";
				visit[i] = 1;
				qu.push(i);
			}
		}
	}
}

Depth first traversal of the adjacency table  

void DFS1(ALGraph&G, int n)
{
	cout << G.arr[n].data << " ";
	visit3[n] = 1;
	StrAcrNode p1;
	p1 = G.arr[n].next;
	while (p1)
	{
		int w = p1->Adjust;
		if (visit3[w] != 1)
		{
			DFS1(G, w);
		}
		p1 = p1->next;
	}
}

queue<int> qu1;

  Breadth first traversal of adjacency table  

queue<int> qu1;
void BFS(ALGraph&G, int n)
{
	cout << G.arr[n].data << " ";
	visit4[n] = 1;
	qu1.push(n);
	StrAcrNode p1;
	p1 = G.arr[n].next;
	while (!qu1.empty())
	{
		qu1.pop();
		int w = p1->Adjust;
		while (p1)
		{
			if (visit4[w] != 1)
			{
				qu1.push(w);
				visit4[w] = 1;
			}
			p1 = p1->next;
		}
	}
}

The overall code

#include<iostream>
#include<queue>
using namespace std;
const int MAxInt = 10;
int visit[MAxInt];

typedef struct
{
	int vexs[MAxInt];
	int arcs[MAxInt][MAxInt];
	int arcnum, vexsnum;
}AMGraph;

int locate(AMGraph&G, int n)
{
	for (int i = 0; i < G.vexsnum; i++)
	{
		if (G.vexs[i] == n)
		{
			return i;
		}
	}
}

void Creat(AMGraph&G)
{
	int v1 = 0, v2 = 0, w = 0;
	cin >> G.vexsnum >> G.arcnum;
	for (int i = 0; i < G.vexsnum; i++)
	{
		cin >> G.vexs[i];
	}
	for (int i = 0; i < G.vexsnum; i++)
	{
		for (int j = 0; j < G.vexsnum; j++)
		{
			G.arcs[i][j] = MAxInt;
		}
	}
	for (int k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2 >> w;
		int i = locate(G, v1);
		int j = locate(G, v2);
		G.arcs[i][j] = w;
		G.arcs[j][i] = w;
	}
}



queue<int> qu;
void BFS(AMGraph G, int v)
{
	cout << G.vexs[v];
	qu.push(v);
	visit[v] = 1;
	while (!qu.empty())
	{
		int w = qu.front();
		qu.pop();
		for (int i = 0; i < G.vexsnum; i++)
		{
			if (visit[i] != 1 && G.arcs[w][i] != MAxInt)
			{
				cout << G.vexs[i] << " ";
				visit[i] = 1;
				qu.push(i);
			}
		}
	}
}

int main()
{
	AMGraph G;
	Creat(G);
	cout << " The result of breadth first traversal of the graph is " << endl;
	BFS(G, 1);
	return 0;
}

Be careful ： The code here is to create an adjacency matrix to traverse the graph in breadth first , The depth first traversal of the graph and the critical table realize the breadth first traversal of the graph , Depth first traversal of the graph can be achieved through free combination of the above code blocks , There is no need to implement them one by one .

Result display

Conclusion

         That's all for today , I hope I can help you , Finally, you can enter this link to practice DFS and BFS Related topics Click here to brush algorithm related topics