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