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)的示例代碼的詳細(xì)內(nèi)容，更多關(guān)于C++ DFS BFS的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
C++實現(xiàn)softmax函數(shù)的面試經(jīng)驗
這篇文章主要為大家介紹了C++實現(xiàn)softmax函數(shù)的面試經(jīng)驗,有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-05-05
迪杰斯特拉算法(Dijkstra)是由荷蘭計算機科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法。本文將用C++實現(xiàn)Dijkstra算法，需要的可以參考一下2022-07-07
這篇文章主要介紹了提高C++程序運行效率的10個簡單方法,包括了循環(huán)、變量、繼承等等應(yīng)用的技巧,非常具有實用價值,需要的朋友可以參考下2014-09-09
給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。問應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大？下面我們分別用回溯與分支限界方法解決2022-06-06
這篇文章主要介紹了MFC列表控件CListCtrl使用方法示范,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了C語言實現(xiàn)BF算法案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
本篇文章是C語言系列基礎(chǔ)篇，C語言中,static是用來修飾變量和函數(shù):1.修飾局部變量–>靜態(tài)局部變量2.修飾全局變量–>靜態(tài)全局變量3.修飾函數(shù)–>靜態(tài)函數(shù)2021-08-08
C語言實現(xiàn)宿舍管理系統(tǒng)課程設(shè)計
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)宿舍管理系統(tǒng)課程設(shè)計，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
Qt?QTableWidget?實現(xiàn)行選中及行懸浮高亮效果
使用Qt開發(fā)中,實現(xiàn)表格的行選中和懸浮高亮效果是一個常見需求,但Qt自帶的方法無法直接實現(xiàn),解決方案是通過子類化QStyledItemDelegate并重寫其paint函數(shù)來定制化繪制過程,本文給大家介紹Qt?QTableWidget?實現(xiàn)行選中及行懸浮高亮效果,感興趣的朋友一起看看吧2024-09-09
這篇文章主要為大家詳細(xì)介紹了C語言版飛機大戰(zhàn)游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-12-12