[置頂] 圖論（一）：DFS，BFS，鄰接鏈表，并查集
來源：程序員人生 發布時間：2016-06-17 08:44:57 閱讀次數：2425次
本文總結了圖的深度優先搜索，圖的廣度優先搜索，鄰接鏈表和鄰接矩陣的實現，并查集的實現。
0），豫備知識
基礎辭匯：有向圖，無向圖，帶權有向圖，帶權無向圖，有向圖中<Vi, Vj>:即Vi--->Vj,弧尾--->弧頭，無向圖中相鄰記為(Vi, Vj)，頂點有窮集合V+邊的有窮集合E。
圖的兩種實現方式：1，鄰接矩陣：edge[n][n]表示有n個結點，數組內容為權值大小或是不是存在邊(∞表示無邊，權值或1表示有邊，0表示結點到結點本身)；
2，鄰接鏈表：針對稀疏矩陣較適合，為圖的每一個頂點都建立1個單鏈表，第i個單鏈表中保存與結點Vi所有相鄰結點信息(無向圖)或弧尾結點信息(有向圖)，和邊信息。
1），圖的深度優先搜索(DFS)
深度優先算法的主要思想是：首先以1個未被訪問過的頂點作為起始頂點，沿當前頂點的邊走到未訪問過的頂點；當沒有未訪問過的頂點時，則回到上1個頂點，繼續摸索訪問別的頂點，直到所有的頂點都被訪問過。明顯，深度優先遍歷是沿著圖的某1條分支遍歷直到末端，然后回溯，再沿著另外一條進行一樣的遍歷。
例1：以下圖為例，從結點1開始DFS，程序的算法思想是：在主函數中初始化連接矩陣，調用dfs(1) ---> 設置變量cnt，將cnt等于結點個數作為dfs遞歸的臨界條件 ---> 設置標志mark[n],鐺鐺前訪問結點的邊指向的下1結點未被訪問時，進行dfs調度訪問(結點的相鄰結點的訪問順序為標號由小到大的順序)
/***先輸入n個結點，m條邊，以后輸入無向圖的m條邊，以后對上圖輸出DFS遍歷的結點順序***/
#include <iostream>
#include <iomanip>
#define nmax 110
#define inf 999999999
using namespace std;
int n, m, cnt, edge[nmax][nmax], mark[nmax];//結點數，邊數，計數值，鄰接矩陣，結點訪問標記
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)為出發點開始遞歸遍歷
memset(mark, 0, sizeof(mark));
cnt = 0;
mark[1] = 1;
dfs(1);
cout << endl;
}
return 0;
}
程序運行結果：
例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號城市的訪問標記，返回到4號城市，由于經過4號城市已訪問過5號城市而又沒有其他城市可訪問；再返回到3號城市，經過3號城市訪問過4號城市，則看看能否訪問5號城市，不能則再返回到2號城市，這時候2號城市有路徑直達5號城市，即1->2->5.....如此折回再前進，直至找到所有1號城市能到達5號城市的路徑，取其中的最小值。
/***先輸入n個結點，m條邊，以后輸入有向圖的m條邊，邊的前兩元素表示起始結點，第3個值表權值，輸出1號城市到n號城市的最短距離***/
/***算法的思路是訪問所有的深度遍歷路徑，需要在深度遍歷返回時將訪問標志置0***/
#include <iostream>
#include <iomanip>
#define nmax 110
#define inf 999999999
using namespace std;
int n, m, minPath, edge[nmax][nmax], mark[nmax];//結點數，邊數，最小路徑，鄰接矩陣，結點訪問標記
void dfs(int cur, int dst){
/***operation***/
/***operation***/
if(minPath < dst) return;//當前走過路徑大于之前最短路徑，沒必要再走下去
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)為出發點開始遞歸遍歷
memset(mark, 0, sizeof(mark));
minPath = inf;
mark[1] = 1;
dfs(1, 0);
cout << minPath << endl;
}
return 0;
}
程序運行結果以下：
2），圖的廣度優先搜索(BFS)
廣度優先遍歷的主要思想是：首先以1個未被訪問過的頂點作為起始頂點，訪問其所有相鄰的頂點，然后對每一個相鄰的頂點，再訪問它們相鄰的未被訪問過的頂點，直到所有頂點都被訪問過，遍歷結束。
例1：根據1）例1中的無向圖，輸出其廣度優先搜索順序。
程序主要思想：結點1入隊 ---> while根據隊列非空進行循環 ---> 出隊并將相鄰結點入隊，另外需要設置計數值cnt，每次出隊時加1。
/***先輸入n個結點，m條邊，以后輸入無向圖的m條邊，邊的兩元素表示起始結點***/
#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));
//開始廣度優先遍歷
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;
}
程序運行結果以下：
例2：以下圖，需要坐飛機從1號城市到5號城市，求最小的轉機次數
/***先輸入n個結點，m條邊，動身城市，終點城市，以后輸入無向圖的m條邊，邊的兩元素表示起始結點***/
/***需要構建結點結構體Node，寄存結點編號和遍歷層數,每次for循環時該層數在上1層基礎上加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;
}
//開始廣度優先遍歷
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;
}
程序運行結果以下：
3），鄰接鏈表和鄰接矩陣的實現
鄰接表由表頭結點(結點信息)和表結點(邊信息)兩部份組成，其中圖中每一個頂點均對應1個存儲在數組中的表頭結點。以下為帶權有向圖：
例1：鄰接鏈表中每一個頂點均對應1個存儲在數組中的表頭結點，為簡化，每一個鄰接結點結構體只包括下1相鄰結點編號和邊權，使用標準模板vector編程實現。另外也可由鄰接矩陣實現，上圖實現以下：
/*****了解邊信息結構體和鄰接鏈表的實現,并在實現好基礎上增加刪除1些邊，以后再用鄰接矩陣實現，學習erase,push_back,setw的用法*****/
#include <iostream>
#include <iomanip>
#include <vector>
#define inf ⑴//設置無窮大為⑴，表示無邊
using namespace std;
int n;
//邊信息，包括連接結點編號和邊的權重
struct Edge{
int adjNodeNum;
int edgeWeight;
};
struct Node{//結點信息
int nodeNum;
char data;
}node[110];
vector<Edge> adjList[110]; //鄰接鏈表，該圖最多有110個結點
int adjMatrix[110][110];//鄰接矩陣
void initAdjList(){
int i;
for(i = 0; i < n; i++) adjList[i].clear();//清空--->構建--->具體操作
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;
}
程序運行結果以下：
4），并查集的實現
并查集：用1棵樹上的結點來表示在1個集合中的數字，如以下{1,2,3,4}和{5,6}，再用每一個結點中的內容表示其雙親結點，如Tree[N]，則Tree[1] = ⑴, Tree[2] = 1, Tree[6] = 5......
如果想要合并這兩棵樹棵樹，則可令Tree[5] = ⑴變成Tree[5] = 1。以下：
對，以下1種特殊情況，需要在查找樹的根節點時，加以1定的束縛與優化，將遍歷過的元素的雙親結點設為根節點，以下：
例1：并查集的實現
/****實現并查集的數組組成，找根節點，合并兩個集合，緊縮路徑************************/
#include <iostream>
#include <iomanip>
using namespace std;
int Set[110];
int Tree[110];
//使用查找函數來尋覓x所在樹的根節點
int findRoot(int x){
if(Tree[x] == ⑴) return x;
else
return findRoot(Tree[x]);
}
//使用緊縮路徑的查找函數來查找x所在樹的根節點,只緊縮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先保存父節點方便while循環，再對數組內容做改變
return x;
}
int main(){
int n1, n2;//集合1，2的元素個數
cout << "Please input the number of set1 and the number of set2:\n";
while(cin >> n1 >> n2){
int i = 0, j;
//輸入集合1和2的數組表，第1行代表元素，第2行代表元素的雙親結點
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個元素，找出各自的根節點
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";
}
}
程序運行結果以下：
例2：暢通工程
/****輸入城鎮數n和道路數m，再輸入每條道路連通的城鎮(城鎮從1開始編號)，看最少需再修幾條路使全部城鎮連通;若輸入n且n=0結束輸入***********/
/****初始化n個并查集，爾后每輸入1條道路，就將關聯的兩個城鎮加入同1并查集，最后由獨立的并查集個數⑴即為所求答案*********************/
#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相同，則會使根節點不為⑴，致使并查集總數變少
}
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;
}
}
程序運行結果以下：
例3：More Is Better
/***有1000 0000個小朋友，隨機選擇朋友關系，每次選中兩個人，且朋友關系具有傳遞性，當選擇m次后，輸出最大朋友關系人數或1**********************/
/***思路與暢通工程類似，初始化并查集，對每次選擇進行并查集合并，由于需要計算最大并查集元素個數，需要初始化每一個sum[i]=1，每次合并都進行累加便可**/
/***先輸入關系次數m，再順次輸入這m組關系****/
#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;
}
程序運行結果以下：
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
