[置頂] 圖論（一）：DFS，BFS，鄰接鏈表，并查集
來源：程序員人生 發(fā)布時間：2016-06-17 08:44:57 閱讀次數(shù)：2414次
本文總結(jié)了圖的深度優(yōu)先搜索，圖的廣度優(yōu)先搜索，鄰接鏈表和鄰接矩陣的實現(xiàn)，并查集的實現(xiàn)。
0），豫備知識
基礎(chǔ)辭匯：有向圖，無向圖，帶權(quán)有向圖，帶權(quán)無向圖，有向圖中<Vi, Vj>:即Vi--->Vj,弧尾--->弧頭，無向圖中相鄰記為(Vi, Vj)，頂點有窮集合V+邊的有窮集合E。
圖的兩種實現(xiàn)方式：1，鄰接矩陣：edge[n][n]表示有n個結(jié)點，數(shù)組內(nèi)容為權(quán)值大小或是不是存在邊(∞表示無邊，權(quán)值或1表示有邊，0表示結(jié)點到結(jié)點本身)；
2，鄰接鏈表：針對稀疏矩陣較適合，為圖的每一個頂點都建立1個單鏈表，第i個單鏈表中保存與結(jié)點Vi所有相鄰結(jié)點信息(無向圖)或弧尾結(jié)點信息(有向圖)，和邊信息。
1），圖的深度優(yōu)先搜索(DFS)
深度優(yōu)先算法的主要思想是：首先以1個未被訪問過的頂點作為起始頂點，沿當(dāng)前頂點的邊走到未訪問過的頂點；當(dāng)沒有未訪問過的頂點時，則回到上1個頂點，繼續(xù)摸索訪問別的頂點，直到所有的頂點都被訪問過。明顯，深度優(yōu)先遍歷是沿著圖的某1條分支遍歷直到末端，然后回溯，再沿著另外一條進行一樣的遍歷。
例1：以下圖為例，從結(jié)點1開始DFS，程序的算法思想是：在主函數(shù)中初始化連接矩陣，調(diào)用dfs(1) ---> 設(shè)置變量cnt，將cnt等于結(jié)點個數(shù)作為dfs遞歸的臨界條件 ---> 設(shè)置標(biāo)志mark[n],鐺鐺前訪問結(jié)點的邊指向的下1結(jié)點未被訪問時，進行dfs調(diào)度訪問(結(jié)點的相鄰結(jié)點的訪問順序為標(biāo)號由小到大的順序)
/***先輸入n個結(jié)點，m條邊，以后輸入無向圖的m條邊，以后對上圖輸出DFS遍歷的結(jié)點順序***/
#include <iostream>
#include <iomanip>
#define nmax 110
#define inf 999999999
using namespace std;
int n, m, cnt, edge[nmax][nmax], mark[nmax];//結(jié)點數(shù)，邊數(shù)，計數(shù)值，鄰接矩陣，結(jié)點訪問標(biāo)記
void dfs(int cur){
cnt++;
/***operation***/
if(cnt == 1)
cout << cur;
else
cout << setw(3) << cur;
/***operation***/
if(cnt == n) return;
else{
int i;
for(i = 1; i <= n; i++){
if(edge[cur][i] == 1 && mark[i] == 0){
mark[i] = 1;
dfs(i);
}
}
return;
}
}
int main(){
while(cin >> n >> m && n != 0){
//初始化鄰接矩陣
int i, j;
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
edge[i][j] = inf;
}
edge[i][i] = 0;
}
int a, b;
while(m--){
cin >> a >> b;
edge[a][b] = edge[b][a] = 1;
}
//以dnf(1)為出發(fā)點開始遞歸遍歷
memset(mark, 0, sizeof(mark));
cnt = 0;
mark[1] = 1;
dfs(1);
cout << endl;
}
return 0;
}
程序運行結(jié)果：
例2：下面是城市的地圖，注意是單向圖，求城市1到城市5的最短距離
程序思路：從1號城市動身，可到達2號城市和5號城市，若依照1到n的順序則先訪問2號城市；訪問完2號城市后，由于2號城市可到達的城市有3號和5號城市，我們訪問3號城市；爾后，3號城市可到達1號，4號城市，由于1號城市已被訪問過，我們訪問4號城市；4號城市又可到達5號城市，我們最后訪問5號城市。但是，1->2->3->4->5其實不1定是最短路徑，我們需要撤除5號城市的訪問標(biāo)記，返回到4號城市，由于經(jīng)過4號城市已訪問過5號城市而又沒有其他城市可訪問；再返回到3號城市，經(jīng)過3號城市訪問過4號城市，則看看能否訪問5號城市，不能則再返回到2號城市，這時候2號城市有路徑直達5號城市，即1->2->5.....如此折回再前進，直至找到所有1號城市能到達5號城市的路徑，取其中的最小值。
/***先輸入n個結(jié)點，m條邊，以后輸入有向圖的m條邊，邊的前兩元素表示起始結(jié)點，第3個值表權(quán)值，輸出1號城市到n號城市的最短距離***/
/***算法的思路是訪問所有的深度遍歷路徑，需要在深度遍歷返回時將訪問標(biāo)志置0***/
#include <iostream>
#include <iomanip>
#define nmax 110
#define inf 999999999
using namespace std;
int n, m, minPath, edge[nmax][nmax], mark[nmax];//結(jié)點數(shù)，邊數(shù)，最小路徑，鄰接矩陣，結(jié)點訪問標(biāo)記
void dfs(int cur, int dst){
/***operation***/
/***operation***/
if(minPath < dst) return;//當(dāng)前走過路徑大于之前最短路徑，沒必要再走下去
if(cur == n){//臨界條件
if(minPath > dst) minPath = dst;
return;
}
else{
int i;
for(i = 1; i <= n; i++){
if(edge[cur][i] != inf && edge[cur][i] != 0 && mark[i] == 0){
mark[i] = 1;
dfs(i, dst+edge[cur][i]);
mark[i] = 0;
}
}
return;
}
}
int main(){
while(cin >> n >> m && n != 0){
//初始化鄰接矩陣
int i, j;
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
edge[i][j] = inf;
}
edge[i][i] = 0;
}
int a, b;
while(m--){
cin >> a >> b;
cin >> edge[a][b];
}
//以dnf(1)為出發(fā)點開始遞歸遍歷
memset(mark, 0, sizeof(mark));
minPath = inf;
mark[1] = 1;
dfs(1, 0);
cout << minPath << endl;
}
return 0;
}
程序運行結(jié)果以下：
2），圖的廣度優(yōu)先搜索(BFS)
廣度優(yōu)先遍歷的主要思想是：首先以1個未被訪問過的頂點作為起始頂點，訪問其所有相鄰的頂點，然后對每一個相鄰的頂點，再訪問它們相鄰的未被訪問過的頂點，直到所有頂點都被訪問過，遍歷結(jié)束。
例1：根據(jù)1）例1中的無向圖，輸出其廣度優(yōu)先搜索順序。
程序主要思想：結(jié)點1入隊 ---> while根據(jù)隊列非空進行循環(huán) ---> 出隊并將相鄰結(jié)點入隊，另外需要設(shè)置計數(shù)值cnt，每次出隊時加1。
/***先輸入n個結(jié)點，m條邊，以后輸入無向圖的m條邊，邊的兩元素表示起始結(jié)點***/
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
#define nmax 110
#define inf 999999999
queue<int> que;
int n, m, mark[nmax], edge[nmax][nmax], cnt;
int main(){
while(cin >> n >> m && n != 0){
int i, j;
//初始化鄰接鏈表
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
edge[i][j] = inf;
}
edge[i][i] = 0;
}
int a, b;
while(m--){
cin >> a >> b;
edge[a][b] = edge[b][a] = 1;
}
while(!que.empty()) que.pop();
memset(mark, 0, sizeof(mark));
//開始廣度優(yōu)先遍歷
int head;
cnt = 0;
mark[1] = 1;
que.push(1);
while(!que.empty()){
head = que.front();
que.pop();
/***operation***/
cnt++;
if(cnt == 1)
cout << head;
else
cout << setw(3) << head;
/***operation***/
for(i = 1; i <= n; i++){
if(edge[head][i] == 1 && mark[i] == 0){
mark[i] = 1;
que.push(i);
}
}
}
cout << endl;
if(cnt != n) cout << "The original image is not connected.\n";
}
return 0;
}
程序運行結(jié)果以下：
例2：以下圖，需要坐飛機從1號城市到5號城市，求最小的轉(zhuǎn)機次數(shù)
/***先輸入n個結(jié)點，m條邊，動身城市，終點城市，以后輸入無向圖的m條邊，邊的兩元素表示起始結(jié)點***/
/***需要構(gòu)建結(jié)點結(jié)構(gòu)體Node，寄存結(jié)點編號和遍歷層數(shù),每次for循環(huán)時該層數(shù)在上1層基礎(chǔ)上加1***/
#include <iostream>
#include <queue>
using namespace std;
#define nmax 110
#define inf 999999999
struct Node{
int node;
int cnt;
};
queue<Node> que;
int m, n, edge[nmax][nmax], mark[nmax], startNum, endNum;
int main(){
while(cin >> n >> m >> startNum >> endNum && n != 0){
bool tag = false;
//初始化鄰接矩陣
int i, j;
for(i = 1; i <= n; i++){
for(j = 1; j <= n; j++){
edge[i][j] = inf;
}
edge[i][i] = 0;
}
while(m--){
cin >> i >> j;
edge[i][j] = edge[j][i] = 1;
}
//開始廣度優(yōu)先遍歷
memset(mark, 0, sizeof(mark));
while(!que.empty()) que.pop();
Node tmp;
tmp.node = startNum;
tmp.cnt = 0;
que.push(tmp);
mark[tmp.node] = 1;
while(!que.empty()){
Node head = que.front();
que.pop();
Node temp;
for(i = 1; i <= n; i++){
if(edge[head.node][i] == 1 && mark[i] == 0){
temp.node = i;
temp.cnt = head.cnt + 1;
que.push(temp);//注意寫在if語句里面
mark[temp.node] = 1;
if(temp.node == endNum){
tag = true;
cout << temp.cnt << endl;
break;
}
}
}
if(tag)
break;
}
}
return 0;
}
程序運行結(jié)果以下：
3），鄰接鏈表和鄰接矩陣的實現(xiàn)
鄰接表由表頭結(jié)點(結(jié)點信息)和表結(jié)點(邊信息)兩部份組成，其中圖中每一個頂點均對應(yīng)1個存儲在數(shù)組中的表頭結(jié)點。以下為帶權(quán)有向圖：
例1：鄰接鏈表中每一個頂點均對應(yīng)1個存儲在數(shù)組中的表頭結(jié)點，為簡化，每一個鄰接結(jié)點結(jié)構(gòu)體只包括下1相鄰結(jié)點編號和邊權(quán)，使用標(biāo)準(zhǔn)模板vector編程實現(xiàn)。另外也可由鄰接矩陣實現(xiàn)，上圖實現(xiàn)以下：
/*****了解邊信息結(jié)構(gòu)體和鄰接鏈表的實現(xiàn),并在實現(xiàn)好基礎(chǔ)上增加刪除1些邊，以后再用鄰接矩陣實現(xiàn)，學(xué)習(xí)erase,push_back,setw的用法*****/
#include <iostream>
#include <iomanip>
#include <vector>
#define inf ⑴//設(shè)置無窮大為⑴，表示無邊
using namespace std;
int n;
//邊信息，包括連接結(jié)點編號和邊的權(quán)重
struct Edge{
int adjNodeNum;
int edgeWeight;
};
struct Node{//結(jié)點信息
int nodeNum;
char data;
}node[110];
vector<Edge> adjList[110]; //鄰接鏈表，該圖最多有110個結(jié)點
int adjMatrix[110][110];//鄰接矩陣
void initAdjList(){
int i;
for(i = 0; i < n; i++) adjList[i].clear();//清空--->構(gòu)建--->具體操作
Edge tmp0[2], tmp1[2], tmp2, tmp3[3];
tmp0[0].adjNodeNum = 1; tmp0[0].edgeWeight = 1;
tmp0[1].adjNodeNum = 2; tmp0[1].edgeWeight = 4;
node[0].data = 'A'; node[0].nodeNum = 0;
adjList[0].push_back(tmp0[0]); adjList[0].push_back(tmp0[1]);
tmp1[0].adjNodeNum = 2; tmp1[0].edgeWeight = 2;
tmp1[1].adjNodeNum = 3; tmp1[1].edgeWeight = 9;
node[1].data = 'B'; node[1].nodeNum = 1;
adjList[1].push_back(tmp1[0]); adjList[1].push_back(tmp1[1]);
tmp2.adjNodeNum = 3; tmp2.edgeWeight = 6;
node[2].data = 'D'; node[2].nodeNum = 2;
adjList[2].push_back(tmp2);
tmp3[0].adjNodeNum = 0; tmp3[0].edgeWeight = 3;
tmp3[1].adjNodeNum = 1; tmp3[1].edgeWeight = 5;
tmp3[2].adjNodeNum = 2; tmp3[2].edgeWeight = 8;
adjList[3].push_back(tmp3[0]); adjList[3].push_back(tmp3[1]); adjList[3].push_back(tmp3[2]);
node[3].data = 'C'; node[3].nodeNum = 3;
}
void output(){
int i, j;
for(i = 0; i < n; i++){
cout << node[i].nodeNum << setw(2) << node[i].data;
for(j = 0; j < adjList[i].size(); j++){
cout << setw(6) << adjList[i][j].adjNodeNum << setw(2) << adjList[i][j].edgeWeight;
}
cout << setw(9) << "NULL" << endl;
}
}
void makeChange(){
cout << "make some changes......:\n";
Edge temp;
temp.adjNodeNum = 3; temp.edgeWeight = 5;
adjList[0].push_back(temp);//鄰接表0中增加1個元素
adjList[3].erase(adjList[3].begin()+1, adjList[3].begin()+3);//鄰接表3中刪除兩個元素
}
void initMatrix(){
int i, j;
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
adjMatrix[i][j] = inf;
}
adjMatrix[i][i] = 0;
}
adjMatrix[0][1] = 1; adjMatrix[0][2] = 4; adjMatrix[1][2] = 2;
adjMatrix[1][3] = 9; adjMatrix[2][3] = 6; adjMatrix[3][0] = 3;
adjMatrix[3][1] = 5; adjMatrix[3][2] = 8;
}
void output1(){
int i, j;
cout << "output the adjacency matrix:\n";
for(i = 0; i < n; i++){
for(j = 0; j < n; j++){
if(j == 0) cout << adjMatrix[i][j];
else cout << setw(3) << adjMatrix[i][j];
}
cout << endl;
}
}
int main(){
n = 4;
initAdjList();
output();
makeChange();
output();
initMatrix();
output1();
return 0;
}
程序運行結(jié)果以下：
4），并查集的實現(xiàn)
并查集：用1棵樹上的結(jié)點來表示在1個集合中的數(shù)字，如以下{1,2,3,4}和{5,6}，再用每一個結(jié)點中的內(nèi)容表示其雙親結(jié)點，如Tree[N]，則Tree[1] = ⑴, Tree[2] = 1, Tree[6] = 5......
如果想要合并這兩棵樹棵樹，則可令Tree[5] = ⑴變成Tree[5] = 1。以下：
對，以下1種特殊情況，需要在查找樹的根節(jié)點時，加以1定的束縛與優(yōu)化，將遍歷過的元素的雙親結(jié)點設(shè)為根節(jié)點，以下：
例1：并查集的實現(xiàn)
/****實現(xiàn)并查集的數(shù)組組成，找根節(jié)點，合并兩個集合，緊縮路徑************************/
#include <iostream>
#include <iomanip>
using namespace std;
int Set[110];
int Tree[110];
//使用查找函數(shù)來尋覓x所在樹的根節(jié)點
int findRoot(int x){
if(Tree[x] == ⑴) return x;
else
return findRoot(Tree[x]);
}
//使用緊縮路徑的查找函數(shù)來查找x所在樹的根節(jié)點,只緊縮x到root所查找的路徑
int findRoot1(int x){
if(Tree[x] == ⑴) return x;
else{
int tmp = findRoot1(Tree[x]);
Tree[x] = tmp;
return tmp;//層層返回
}
}
//使用非遞歸方式
int findRoot_(int x){
while(Tree[x] != ⑴) x = Tree[x];
return x;
}
int findRoot_1(int x){
int tmp = x;
while(Tree[x] != ⑴) x = Tree[x];
while(Tree[tmp] != ⑴) {tmp = Tree[tmp]; Tree[tmp] = x;}//tmp先保存父節(jié)點方便while循環(huán)，再對數(shù)組內(nèi)容做改變
return x;
}
int main(){
int n1, n2;//集合1，2的元素個數(shù)
cout << "Please input the number of set1 and the number of set2:\n";
while(cin >> n1 >> n2){
int i = 0, j;
//輸入集合1和2的數(shù)組表，第1行代表元素，第2行代表元素的雙親結(jié)點
cout << "Please input set1(first line is node, second line is its father node):\n";
for(i = 0; i < n1; i++) cin >> Set[i];
for(i = 0; i < n1; i++) cin >> Tree[Set[i]];
cout << "Please input set2(first line is node, second line is its father node):\n";
for(i = n1 ; i < n1 + n2; i++) cin >> Set[i];
for(i = n1 ; i < n1 + n2; i++) cin >> Tree[Set[i]];
//輸入集合1和集合2中的1個元素，找出各自的根節(jié)點
cout << "Please input two nodes of the two sets (and output its root node):\n";
int sub1, sub2;
cin >> sub1 >> sub2;
cout << "It's root node is: " << findRoot(sub1) << " " << findRoot(sub2) << endl;
//合并集合1和集合2，并顯示
cout << "Merge two trees:\n";
Tree[findRoot1(sub2)] = findRoot1(sub1);
for(i = 0; i < n1 + n2; i++) cout << setw(2) <<Set[i];
cout << endl;
for(i = 0; i < n1 + n2; i++) cout << setw(2) << Tree[Set[i]];
cout << endl;
cout << "Please input the number of set1 and the number of set2:\n";
}
}
程序運行結(jié)果以下：
例2：暢通工程
/****輸入城鎮(zhèn)數(shù)n和道路數(shù)m，再輸入每條道路連通的城鎮(zhèn)(城鎮(zhèn)從1開始編號)，看最少需再修幾條路使全部城鎮(zhèn)連通;若輸入n且n=0結(jié)束輸入***********/
/****初始化n個并查集，爾后每輸入1條道路，就將關(guān)聯(lián)的兩個城鎮(zhèn)加入同1并查集，最后由獨立的并查集個數(shù)⑴即為所求答案*********************/
#include <iostream>
using namespace std;
int Tree[1100];
int findRoot(int x){
if(Tree[x] == ⑴) return x;
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
int main(){
int n, m;
while(cin >> n && n!= 0){
cin >> m;
int i;
for(i = 1; i <= n; i++)//初始化n個并查集
Tree[i] = ⑴;
int a, b;
for(i = m; i >= 1; i--){//處理m條道路，合并并查集
cin >> a >> b;
a = findRoot(a);
b = findRoot(b);
if(a != b) Tree[b] = a; //此處必須先進行比較，如果a，b相同，則會使根節(jié)點不為⑴，致使并查集總數(shù)變少
}
int count = 0;
for(i = 1; i <= n; i++)//計算剩余獨立的并查集
if(Tree[i] == ⑴) ++count;
cout << "Need to build the number of roads is: " << count - 1 << endl;
}
}
程序運行結(jié)果以下：
例3：More Is Better
/***有1000 0000個小朋友，隨機選擇朋友關(guān)系，每次選中兩個人，且朋友關(guān)系具有傳遞性，當(dāng)選擇m次后，輸出最大朋友關(guān)系人數(shù)或1**********************/
/***思路與暢通工程類似，初始化并查集，對每次選擇進行并查集合并，由于需要計算最大并查集元素個數(shù)，需要初始化每一個sum[i]=1，每次合并都進行累加便可**/
/***先輸入關(guān)系次數(shù)m，再順次輸入這m組關(guān)系****/
#include <iostream>
using namespace std;
#define num 10000001
int Tree[num];
int Sum[num];
int findRoot(int x){
if(Tree[x] == ⑴) return x;
else{
int tmp = findRoot(Tree[x]);
Tree[x] = tmp;
return tmp;
}
}
int main(){
int m;
while(cin >> m && m != 0){
int i;
for(i = 1; i < num; i++) {Tree[i] = ⑴; Sum[i] = 1;}
int a, b;
while(m--){
cin >> a >> b;
a = findRoot(a);
b = findRoot(b);
if(a != b) {Tree[b] = a; Sum[a] += Sum[b];}
}
int max = 1;
for(i = 1; i < num; i++)
if(Sum[i] > max) max = Sum[i];
cout << "Maximum number of friends is: " << max << endl;
}
return 0;
}
程序運行結(jié)果以下：
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機掃描二維碼進行捐贈
