当前位置:网站首页>Depth first DFS and breadth first BFS -- traversing adjacency tables
Depth first DFS and breadth first BFS -- traversing adjacency tables
2022-07-05 22:14:00 【Demo Dragon】
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
边栏推荐
- Image editor for their AutoLayout environment
- 如何開發引入小程序插件
- 等到产业互联网时代真正发展成熟,我们将会看待一系列的新产业巨头的出现
- Three "factions" in the metauniverse
- C language knowledge points link
- K210 learning notes (IV) k210 runs multiple models at the same time
- 装饰器学习01
- 他们主动布局(autolayout)环境的图像编辑器
- A trip to Suzhou during the Dragon Boat Festival holiday
- Blocking protocol for concurrency control
猜你喜欢
Recovery technology with checkpoints
科技云报道荣膺全球云计算大会“云鼎奖”2013-2022十周年特别贡献奖
【愚公系列】2022年7月 Go教学课程 003-IDE的安装和基本使用
笔记本电脑蓝牙怎么用来连接耳机
K210学习笔记(四) K210同时运行多个模型
Concurrency control of performance tuning methodology
Server optimization of performance tuning methodology
"Chris Richardson microservices series" uses API gateway to build microservices
Win11 runs CMD to prompt the solution of "the requested operation needs to be promoted"
2022-07-05: given an array, you want to query the maximum value in any range at any time. If it is only established according to the initial array and has not been modified in the future, the RMQ meth
随机推荐
Business learning of mall order module
How can Bluetooth in notebook computer be used to connect headphones
Sentinel production environment practice (I)
The solution to the problem that Oracle hugepages are not used, causing the server to be too laggy
如何开发引入小程序插件
Database recovery strategy
How to add new fields to mongodb with code (all)
The American Championship is about to start. Are you ready?
Sub total of Pico development
Pl/sql basic syntax
ICMP introduction
Oracle checkpoint queue - Analysis of the principle of instance crash recovery
Wonderful review of the digital Expo | highlight scientific research strength, and Zhongchuang computing power won the digital influence enterprise award
Oracle hint understanding
Meituan dynamic thread pool practice ideas, open source
Reptile practice
Text组件新增内容通过tag_config设置前景色、背景色
科技云报道荣膺全球云计算大会“云鼎奖”2013-2022十周年特别贡献奖
Matlab draws a cute fat doll
U盘的文件无法删除文件怎么办?Win11无法删除U盘文件解决教程