当前位置:网站首页>Graph traversal - BFS, DFS
Graph traversal - BFS, DFS
2022-04-23 20:46:00 【baboon_ chen】
List of articles
One 、 Depth-first search (Depth First Search,DFS)
The algorithm is similar to the preorder traversal of binary tree , The access operation is performed when a vertex is passed for the first time , And record that the vertex has been accessed . The specific steps are as follows :
- Set the pointer p, Point to the top v.
- visit p Pointed vertex , And make p Points to a vertex that is adjacent to it and has not been accessed .
- If p The pointed vertex exists , Then repeat the steps (2), Otherwise, carry out the steps (4).
- Trace back to a vertex that has adjacent vertices and has not been visited in the order and direction just visited , And make p Point to this vertex . Then repeat the steps (2), Until all vertices are accessed .
Suppose there is a diagram as follows :
The data format of adjacency table is expressed as :
Assuming that the 0 Start traversing the vertices , Then the traversal node is :
0 4 2 6 7
// Other vertices from 0 I can't get to , Because the vertex 0 They are not accessible through directed edges .
// Print other vertices if necessary , Just add a cycle .
Sample code
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
#define MAX_NODE 20 // The maximum number of vertices in a graph
struct ArcNode // The table node adjacent to the linked list
{
int adjVex; // adjacent vertex The vertex sequence number of the adjacent vertex
double weight; // The weight of the arc
struct ArcNode* nextNode; // Point to the next adjacent vertex
};
struct AdjHead // Adjacent to the head node of the linked list
{
int data; // Data represented by vertices , Use a number to represent
struct ArcNode* firstNode; // Point to the first adjacent vertex
};
using AdjList = vector<AdjHead>; // Adjacency list
struct Graph
{
int vNum; // The number of vertices in a graph
AdjList adjList;
};
int visited[MAX_NODE] = {0}; // Record whether the vertices in the graph have been accessed
// Breadth First Search
void BFS(const Graph& g)
{
int visited[MAX_NODE] = {0}; // Record whether the vertices in the graph have been accessed
queue<int> q; // Create a queue
for (int i = 0; i < g.vNum; i++) {
if (visited[i] == 0) { // The vertices i Not visited
q.push(i);
cout << i << " ";
visited[i] = 1; // The vertices i Mark as visited
while(!q.empty()) { // If the queue is not empty , Then continue to take the vertex for BFS
int k = q.front();
q.pop();
ArcNode* n = g.adjList[k].firstNode;
while(n != nullptr) { // Check all and vertices k The adjacency vertex of
int j = n->adjVex;
if (visited[j] == 0) { // If adjacent vertices j Not visited , take j Join the queue
q.push(j);
cout << j << " ";
visited[j] = 1;
}
n = n->nextNode;
}
}
}
}
}
int main()
{
AdjList adjList;
adjList.resize(MAX_NODE);
ArcNode n1{4, 1.0, nullptr};
ArcNode n2{6, 1.0, nullptr};
ArcNode n3{0, 1.0, &n2};
ArcNode n4{6, 1.0, nullptr};
ArcNode n5{0, 1.0, &n4};
ArcNode n6{1, 1.0, nullptr};
ArcNode n7{7, 1.0, nullptr};
ArcNode n8{2, 1.0, &n7};
ArcNode n9{7, 1.0, nullptr};
ArcNode n10{1, 1.0, &n9};
ArcNode n11{6, 1.0, nullptr};
adjList[0] = AdjHead{0, &n1};
adjList[1] = AdjHead{1, &n3};
adjList[2] = AdjHead{2, &n5};
adjList[3] = AdjHead{3, &n6};
adjList[4] = AdjHead{4, &n8};
adjList[5] = AdjHead{5, &n10};
adjList[7] = AdjHead{7, &n11};
Graph g{8, move(adjList)};
DFS(g, 0);
//BFS(g);
return 0;
}
Algorithm complexity
The process of depth first traversing a graph is essentially the process of finding its adjacent nodes for a vertex , The time it takes depends on the storage structure . When a graph is represented by an adjacency matrix , The time needed to find the adjacency of all vertices is O(n2). When the adjacency table is used as the storage structure , The time complexity of depth first search traversal graph is O(n+e).
Two 、 Breadth first search (Breadth First Search,BFS)
Breadth first search method is : From a vertex in the graph v set out , During a visit to the v And then access v The adjacent points that have not been visited , Then access their adjacency points one by one from each of these adjacency points , And make
The adjacent point of the vertex accessed first
PrecedeThe adjacent point of the vertex to be accessed later
To be accessed , Until the adjacent points of all accessed vertices in the graph are accessed . If there are still unreachable vertices , Select another vertex in the graph that has not been accessed as the starting point , Repeat the process , Until all vertices in the graph are accessed .
Sample code
// Depth First Search
void DFS(const Graph& g, int i) {
cout << i << " "; // The access number is i The summit of
visited[i] = 1; // The tag has been accessed
ArcNode* n = g.adjList[i].firstNode; // Take the top i The first adjacent vertex of
while (n != nullptr) { // Check all and i A vertex adjacent to a vertex
int j = n->adjVex;
if (visited[j] == 0) { // If the vertex j Not visited , From the vertex j Set out for DFS
DFS(g, j);
}
n = n->nextNode; // Continue to traverse the next adjacent vertex
}
}
The output is :
0 4 2 7 6 1 3 5
Algorithm complexity
The process of traversing a graph is essentially the process of finding adjacent nodes through edges or arcs , because
BFS
AndDFS
The algorithm time complexity of traversing the graph is the same , The only difference is that the order of access to vertices is different .
版权声明
本文为[baboon_ chen]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204210546350755.html
边栏推荐
- 【SQL】字符串系列2:将一个字符串根据特定字符分拆成多行
- 中创存储|想要一个好用的分布式存储云盘,到底该怎么选
- How to do after winning the new debt? Is it safe to open an account online
- The construction and use of Fortress machine and springboard machine jumpserver are detailed in pictures and texts
- Unity ECS dots notes
- JSX syntax rules
- go slice
- XXXI` Prototype ` displays prototype properties and`__ proto__` Implicit prototype properties
- Unity asset import settings
- MySQL数据库常识之储存引擎
猜你喜欢
MySQL基础合集
3-5 obtaining cookies through XSS and the use of XSS background management system
UnhandledPromiseRejectionwarning:CastError: Cast to ObjectId failed for value
Case of the third day of go language development fresh every day project - news release system II
go interface
內網滲透之DOS命令
LeetCode 116. 填充每个节点的下一个右侧节点指针
[stack and queue topics] - sliding window
Mysql database common sense storage engine
Scripy tutorial - (2) write a simple crawler
随机推荐
内网渗透之DOS命令
Addition, deletion, modification and query of advanced MySQL data (DML)
go defer
Singleton mode
vulnhub DC:1渗透笔记
Awk print special characters
How to do after winning the new debt? Is it safe to open an account online
Flex layout
Unity asset import settings
C migration project record: modify namespace and folder name
laravel 发送邮件
High paid programmer & interview question series 91 limit 20000 loading is very slow. How to solve it? How to locate slow SQL?
Learn to C language fourth day
MySQL basic collection
C knowledge
CONDA environment management command
Cmake project under vs2019: calculating binocular parallax using elas method
Resolve the error - error identifier 'attr_ id‘ is not in camel case camelcase
BMP JPEG picture to vector image contourtrace
How many hacking methods do you know?