C++實現(xiàn)圖的遍歷算法(DFS,BFS)的示例代碼
圖的定義
圖由頂點集V(G)和邊集E(G)組成，記為G=(V,E)。其中E(G)是邊的有限集合，邊是頂點的無序?qū)Γo向圖）或有序?qū)Γㄓ邢驁D）。對于有向圖來說，E(G)是有向邊（也稱弧(Arc)）的有限集合，弧是頂點的有序?qū)?，記?lt;v,w>，v、w是頂點，v為弧尾（箭頭根部），w為弧頭（箭頭處）。對于無向圖來說，E(G)是邊的有限集合，邊是頂點的無序?qū)?，記?v, w)或者(w, v)，并且(v, w)=(w,v)。
圖的相關(guān)術(shù)語
①頂點(Vertex)：圖中的數(shù)據(jù)元素。
②頂點v的度：與v相關(guān)聯(lián)的邊的數(shù)目；
③頂點v的出度：以v為起點有向邊數(shù)；
④頂點v的入度：以v為終點有向邊數(shù)。
⑤邊：頂點之間的邏輯關(guān)系用邊來表示，邊集可以是空的。
⑥無向邊(Edge)：若頂點V1到V2之間的邊沒有方向，則稱這條邊為無向邊。
⑦無向圖(Undirected graphs)：圖中任意兩個頂點之間的邊都是無向邊。（A,D）=（D,A）
⑧有向邊：若從頂點V1到V2的邊有方向，則稱這條邊為有向邊，也稱弧(Arc)。用<V1,V2>表示，V1為狐尾(Tail)，V2為弧頭(Head)。（V1，V2）≠（V2，V1）。
⑨有向圖(Directed graphs)：圖中任意兩個頂點之間的邊都是有向邊。
注意：無向邊用“（）”，而有向邊用“< >”表示。
⑩簡單圖：圖中不存在頂點到其自身的邊，且同一條邊不重復(fù)出現(xiàn)。
?無向完全圖：無向圖中，任意兩個頂點之間都存在邊。
?有向完全圖：有向圖中，任意兩個頂點之間都存在方向互為相反的兩條弧。
?稀疏圖：有很少條邊。
?稠密圖：有很多條邊。
?權(quán)（Weight）：與圖的邊或弧相關(guān)的數(shù)。
?網(wǎng)（Network）：帶權(quán)的圖。
?連通圖：圖中任意兩個頂點都是連通的。
?極大連通子圖：該子圖是G連通子圖，將G的任何不在該子圖的頂點加入，子圖將不再連通。
?極小連通子圖：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖都將不再連通。
圖的創(chuàng)建(鄰接矩陣)---結(jié)構(gòu)體
typedef struct
{
//用來存放頂點
int vexs[MAX];
//二維數(shù)組：用來存放兩點之間的關(guān)系
int arcs[MAX][MAX];
//圖的頂點數(shù)和邊數(shù)
int vexsum, arcsnum;
}AMGraph,*StrAMGraph;
圖的創(chuàng)建(鄰接矩陣)---鄰接矩陣的創(chuàng)建
int locate(AMGraph&G, int n)
{
for (int i = 0; i < G.vexsum; i++)
{
if (G.vexs[i] == n)
{
return i;
}
}
}
//創(chuàng)建鄰接矩陣
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;
}
}圖的創(chuàng)建(鄰接表)---結(jié)構(gòu)體
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;圖的創(chuàng)建(鄰接表)---鄰接表的創(chuàng)建
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;
}
}對鄰接矩陣進行深度優(yōu)先遍歷
//對鄰接矩陣進行深度優(yōu)先遍歷
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]);
}
}
}
對鄰接矩陣進行廣度優(yōu)先遍歷
queue<int> qu;
//對鄰接矩陣進行廣度優(yōu)先遍歷
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);
}
}
}
}對鄰接表進行深度優(yōu)先遍歷
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;對鄰接表進行廣度優(yōu)先遍歷
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;
}
}
}整體代碼
#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 << "對圖進行廣度優(yōu)先遍歷的結(jié)果為" << endl;
BFS(G, 1);
return 0;
}注意 ：這里的代碼是創(chuàng)建一個鄰接矩陣來對圖進行廣度優(yōu)先遍歷，對圖進行深度優(yōu)先遍歷以及臨界表實現(xiàn)對圖進行廣度優(yōu)先遍歷，對圖進行深度優(yōu)先遍歷大家都可以通過上面的代碼塊進行自由組合實現(xiàn)，這里就不進行一一實現(xiàn)。
結(jié)果展示
以上就是C++實現(xiàn)圖的遍歷算法(DFS,BFS)的示例代碼的詳細內(nèi)容，更多關(guān)于C++ DFS BFS的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了C++名稱空間特性，文章圍繞C++名稱空間特性的相關(guān)資料展開詳細內(nèi)容，需要的小伙伴可以參考一下下文具體內(nèi)容，希望對你的學(xué)習(xí)有所幫助2022-01-01
C語言實現(xiàn)學(xué)生信息管理系統(tǒng)(單鏈表)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)學(xué)生信息管理系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
Qt實現(xiàn)SqlRelationalTable關(guān)聯(lián)表組件
在Qt中我們可以通過拖拽的方式將不同組件放到指定的位置,實現(xiàn)圖形化開發(fā)極大的方便了開發(fā)效率,本章將重點介紹SqlRelationalTable關(guān)聯(lián)表組件的常用方法及靈活運用,感興趣的可以了解一下2023-12-12
全網(wǎng)最接地氣的C語言野指針介紹，此處對于野指針與空指針知識點做一些簡要的介紹，作者實屬初學(xué)，難免文章中有內(nèi)容理解不到位或者有不當(dāng)之處，還請朋友們不吝指正，希望大家多多給予支持2021-11-11
在本篇文章里小編給大家整理的是關(guān)于c語言逗號表達式的運算規(guī)則知識點，需要的朋友們可以學(xué)習(xí)參考下。2020-03-03
C++判斷主機是否處于聯(lián)網(wǎng)狀態(tài)
這篇文章主要為大家詳細介紹了C++判斷主機是否處于聯(lián)網(wǎng)狀態(tài)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
C?語言提供了豐富的操作符，有：算術(shù)操作符，移位操作符，位操作符，賦值操作符，單目操作符，關(guān)系操作符，邏輯操作符，條件操作符等。接下了讓我們詳細了解掌握它2022-05-05
這篇文章主要介紹了C++判斷矩形相交的方法,涉及C++針對平面坐標(biāo)數(shù)學(xué)運算的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
如何將C語言代碼轉(zhuǎn)換為應(yīng)用程序(也就是編譯)
有時候我們將讓我們的c語言代碼保存為一個exe方便，方便使用，實際就是我們俗說的編譯2013-07-07
這篇文章主要利用Matlab實現(xiàn)繪制獨特的表白動圖，文中的示例代碼講解詳細，對我們學(xué)習(xí)Matlab有一定的幫助，感興趣的小伙伴可以了解一下2022-05-05