L3-圖論-第08課 圖的遍歷

圖的遍歷是指，從給定圖中任意指定的頂點(稱為初始點)出發，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點，使每個頂點僅被訪問一次，這個過程稱為圖的遍歷。遍歷過程中得到的頂點序列稱為圖遍歷序列。

圖的遍歷過程中，根據搜索方法的不同，又可以劃分為兩種搜索策略：

• 深度優先搜索(DFS，Depth First Search)

• 廣度優先搜索(BFS，Breadth First Search)

深度優先搜索 DFS

DFS 全稱是(Depth First Search)，中文名是深度優先搜索，是一種用于遍歷或搜索樹或圖的算法。所謂深度優先，就是說每次都嘗試向更深的節點走。

該算法講解時常常與 BFS 并列，但兩者除了都能遍歷圖的連通塊以外，用途完全不同，很少有能混用兩種算法的情況。

DFS 最顯著的特征在于其 「遞歸調用自身」 。同時與 BFS 類似，DFS 會對其訪問過的點打上訪問標記，在遍歷圖時跳過已打過標記的點，以確保 「每個點僅訪問一次」 。符合以上兩條規則的函數，便是廣義上的 DFS。

算法思想

從頂點 vi 出發, 訪問, 標記, 找鄰接頂點 vi1

從vi1 出發, DFS訪問和它鄰接的所有頂點

轉到第一步, 直到所有和vi鄰接的頂點全部被訪問.

繼續選取圖中其他未訪問的頂點作為起始頂點, 轉到第一步.

具體地說，DFS 大致結構如下：

DFS(v) // v 可以是圖中的一個頂點，也可以是抽象的概念，如 dp 狀態等。
在 v 上打訪問標記
for u in v 的相鄰結點
if u 沒有打過訪問標記 then
DFS(u)
end
end
end

該算法通常的時間復雜度為 ，空間復雜度為 ，其中 表示點數， 表示邊數。注意空間復雜度包含了棧空間，棧空間的空間復雜度是 的。在平均 遍歷一條邊的條件下才能達到此時間復雜度，例如用前向星或鄰接表存儲圖；如果用鄰接矩陣則不一定能達到此復雜度。

參考代碼

以鏈式前向星為例:

void?dfs(int?u)?{
??cout?<"?";
??vis[u]?=?1;
??for?(int?ei?=?head[u];?ei;?ei?=?e[ei].next)?{
????if?(!vis[e[i].to])?{
??????dfs(e[i].to);
????}
??}
}

DFS 序列

DFS 序列是指 DFS 調用過程中訪問的節點編號的序列。

我們發現，每個子樹都對應 DFS 序列中的連續一段(一段區間)。

一般圖上 DFS

對于非連通圖，只能訪問到起點所在的連通分量。

對于連通圖，DFS 序列通常不唯一。

注：樹的 DFS 序列也是不唯一的。

在 DFS 過程中，通過記錄每個節點從哪個點訪問而來，可以建立一個樹結構，稱為 DFS 樹。DFS 樹是原圖的一個生成樹。

[USACO06DEC]Cow Picnic S

題目描述

The cows are having a picnic! Each of Farmer John's K (1 ≤ K ≤ 100) cows is grazing in one of N (1 ≤ N ≤ 1,000) pastures, conveniently numbered 1...N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths (no path connects a pasture to itself).

The cows want to gather in the same pasture for their picnic, but (because of the one-way paths) some cows may only be able to get to some pastures. Help the cows out by figuring out how many pastures are reachable by all cows, and hence are possible picnic locations.

K(1≤K≤100)只奶牛分散在N(1≤N≤1000)個牧場．現在她們要集中起來進餐．牧場之間有M(1≤M≤10000)條有向路連接，而且不存在起點和終點相同的有向路．她們進餐的地點必須是所有奶牛都可到達的地方．那么，有多少這樣的牧場呢？

輸入格式

Line 1: Three space-separated integers, respectively: K, N, and M

Lines 2..K+1: Line i+1 contains a single integer (1..N) which is the number of the pasture in which cow i is grazing.

Lines K+2..M+K+1: Each line contains two space-separated integers, respectively A and B (both 1..N and A != B), representing a one-way path from pasture A to pasture B.

輸出格式

Line 1: The single integer that is the number of pastures that are reachable by all cows via the one-way paths.

輸入輸出樣例

• 輸入 #1復制

2 4 4
2
3
1?2
1?4
2?3
3?4

• 輸出 #1復制

2

說明/提示

The cows can meet in pastures 3 or 4.

分析

牧場個數是 1000 個, 使用鄰接矩陣存儲空間上是沒問題的. 求所有奶牛都能到的牧場, 那就讓奶牛遍歷所有的能到達的點, 并且標記好. 那么被所有奶牛標記過的牧場就是所求的.

鄰接矩陣

#include?
#include?
using?namespace?std;

const?int?MAXN?=?1000?+?6;

int?k,?n,?m,?ans;
int?g[MAXN][MAXN],?cow[MAXN];
int?vis[MAXN],?mk[MAXN];

int?dfs(int?x)
{
?mk[x]++;
?vis[x]?=?1;
?for?(int?i?=?1;?i?<=?n;?i++)
?{
??if?(g[x][i]?&&?vis[i]?==?0)
??{
???dfs(i);
??}
?}
}

int?main()
{
?ios::sync_with_stdio(false);
?cin?>>?k?>>?n?>>?m;

?for?(int?i?=?1;?i?<=?k;?i++)
?{
??cin?>>?cow[i];
?}

?for?(int?i?=?1;?i?<=?m;?i++)
?{
??int?x,?y;
??cin?>>?x?>>?y;
??g[x][y]?=?1;
?}

?for?(int?i?=?1;?i?<=?k;?i++)
?{
??memset(vis,?0,?sizeof(vis));
??dfs(cow[i]);
?}

?for?(int?i?=?1;?i?<=?n;?i++)
?{
??if?(mk[i]?==?k)
???ans++;
?}

?cout?<?return?0;
}

廣度優先搜索 BFS

BFS 全稱是 [Breadth First Search] 中文名是寬度優先搜索，也叫廣度優先搜索。是圖上最基礎、最重要的搜索算法之一。

所謂寬度優先。就是每次都嘗試訪問同一層的節點。如果同一層都訪問完了，再訪問下一層。

這樣做的結果是，BFS 算法找到的路徑是從起點開始的 「最短」 合法路徑。換言之，這條路所包含的邊數最小。

在 BFS 結束時，每個節點都是通過從起點到該點的最短路徑訪問的。

算法思想

偽代碼：

bfs(s) {
q = new queue()
q.push(s);
visited[s] = true
while (!q.empty()) {
u = q.pop()
for each edge(u, v) {
if (!visited[v]) {
q.push(v)
visited[v] = true
}
}
}
}

參考代碼

C++：

void?bfs(int?u)?{
??while?(!Q.empty())
????Q.pop();
??Q.push(u);
??vis[u]?=?1;
??d[u]?=?0;
??p[u]?=?-1;
??while?(!Q.empty())?{
????u?=?Q.front();
????Q.pop();
????for?(int?i?=?head[u];?i;?i?=?e[i].next)?{
??????if?(!vis[e[i].to])?{
????????Q.push(e[i].to);
????????vis[e[i].to]?=?1;
????????d[e[i].to]?=?d[u]?+?1;
????????p[e[i].to]?=?u;
??????}
????}
??}
}
void?restore(int?x)?{
??vector<int>?res;
??for?(int?v?=?x;?v?!=?-1;?v?=?p[v])?{
????res.push_back(v);
??}
??std::reverse(res.begin(),?res.end());
??for?(int?i?=?0;?i?printf("%d",?res[i]);
??puts("");
}

具體來說，我們用一個隊列 Q 來記錄要處理的節點，然后開一個 布爾數組來標記某個節點是否已經訪問過了。

開始的時候，我們把起點 s 以外的節點的 vis 值設為 0，意思是沒有訪問過。然后把起點 s 放入隊列 Q 中。

之后，我們每次從隊列 Q 中取出隊首的點 u，把 u 相鄰的所有點 v 標記為已經訪問過了并放入隊列 Q。

直到某一時刻，隊列 Q 為空，這時 BFS 結束。

在 BFS 的過程中，也可以記錄一些額外的信息。比如上面的代碼中，d 數組是用來記錄某個點到起點的距離(要經過的最少邊數)，p 數組是記錄從起點到這個點的最短路上的上一個點。

有了 d 數組，可以方便地得到起點到一個點的距離。

有了 p 數組，可以方便地還原出起點到一個點的最短路徑。上面的 restore 函數就是在做這件事：restore(x) 輸出的是從起點到 x 這個點所經過的點。

時間復雜度

空間復雜度 (vis 數組和隊列)

BFS 序列

BFS 序列通常也不唯一。

類似的我們也可以定義 BFS 樹：在 BFS 過程中，通過記錄每個節點從哪個點訪問而來，可以建立一個樹結構，即為 BFS 樹。

應用

• 在一個無權圖上求從起點到其他所有點的最短路徑。

• 在 時間內求出所有連通塊。(我們只需要從每個沒有被訪問過的節點開始做 BFS，顯然每次 BFS 會走完一個連通塊)

• 如果把一個游戲的動作看做是狀態圖上的一條邊(一個轉移)，那么 BFS 可以用來找到在游戲中從一個狀態到達另一個狀態所需要的最小步驟。

• 在一個邊權為 0/1 的圖上求最短路。(需要修改入隊的過程，如果某條邊權值為 0，且可以減小邊的終點到圖的起點的距離，那么把邊的起點加到隊列首而不是隊列尾)

• 在一個有向無權圖中找最小環。(從每個點開始 BFS，在我們即將抵達一個之前訪問過的點開始的時候，就知道遇到了一個環。圖的最小環是每次 BFS 得到的最小環的平均值。)

• 找到一定在 最短路上的邊。(分別從 a 和 b 進行 BFS，得到兩個 d 數組。之后對每一條邊 ，如果 ，則說明該邊在最短路上)

• 找到一定在 最短路上的點。(分別從 a 和 b 進行 BFS，得到兩個 d 數組。之后對每一個點 v，如果 ，則說明該點在最短路上)

• 找到一條長度為偶數的最短路。(我們需要一個構造一個新圖，把每個點拆成兩個新點，原圖的邊 變成 和 。對新圖做 BFS， 和 之間的最短路即為所求)

P5318 【深基18.例3】查找文獻

題目描述

小K 喜歡翻看洛谷博客獲取知識。每篇文章可能會有若干個(也有可能沒有)參考文獻的鏈接指向別的博客文章。小K 求知欲旺盛，如果他看了某篇文章，那么他一定會去看這篇文章的參考文獻(如果他之前已經看過這篇參考文獻的話就不用再看它了)。

假設洛谷博客里面一共有 篇文章(編號為 1 到 n)以及 條參考文獻引用關系。目前小 K 已經打開了編號為 1 的一篇文章，請幫助小 K 設計一種方法，使小 K 可以不重復、不遺漏的看完所有他能看到的文章。

這邊是已經整理好的參考文獻關系圖，其中，文獻 X → Y 表示文章 X 有參考文獻 Y。不保證編號為 1 的文章沒有被其他文章引用。

請對這個圖分別進行 DFS 和 BFS，并輸出遍歷結果。如果有很多篇文章可以參閱，請先看編號較小的那篇(因此你可能需要先排序)。

輸入格式

無

輸出格式

無

輸入輸出樣例

• 輸入 #1復制

8?9
1?2
1?3
1?4
2?5
2?6
3?7
4?7
4?8
7?8

• 輸出 #1復制

1?2?5?6?3?7?8?4
1?2?3?4?5?6?7?8

分析

文章數是 所以鄰接矩陣不能使用, 得用鄰接表或者鏈式前向星來存儲才可以. 要求輸出時從編號小的開始, 所以需要對邊進行排序.

參考代碼

#include?
#include?
#include?
#include?
#include?
using?namespace?std;

const?int?MAXN?=?1e6?+?8;
struct?Edge
{
?int?u,?v;
}?es[MAXN];
vector?hd[MAXN];
bool?vis[MAXN]?=?{0};
int?n,?m;
bool?cmp(Edge?&e1,?Edge?&e2)
{if?(e1.v?==?e2.v)return?e1.u?return?e1.v?}
void?dfs(int?x)
{
?vis[x]?=?1;
?cout?<"?";for?(int?i?=?0;?i??{
??int?point?=?es[hd[x][i]].v;if?(!vis[point])
??{
???dfs(point);
??}
?}
}
void?bfs(int?x)
{
?queue?q;
?memset(vis,?0,?sizeof(vis));
?q.push(x);
?cout?<"?";
?vis[x]?=?true;while?(!q.empty())
?{
??int?u?=?q.front();for?(int?i?=?0;?i???{
???int?point?=?es[hd[u][i]].v;if?(!vis[point])
???{
????q.push(point);
????cout?<"?";
????vis[point]?=?true;
???}
??}
??q.pop();
?}
}
int?main()
{
?ios::sync_with_stdio(false);
?cin?>>?n?>>?m;for?(int?i?=?1;?i?<=?m;?i++)
?{
??cin?>>?es[i].u?>>?es[i].v;
?}
?sort(es?+?1,?es?+?1?+?m,?cmp);for?(int?i?=?1;?i?<=?m;?i++)
??hd[es[i].u].push_back(i);
?dfs(1);
?cout?<?bfs(1);return?0;
}

題單

• P5318 【深基18.例3】查找文獻
• P3916 圖的遍歷
• P1113 雜務
• P1807 最長路
• P1127 詞鏈
• P2853 [USACO06DEC]Cow Picnic S

云帆優培訂閱號：

云帆優培服務號:

????????????????????

云帆優培老師聯系方式：

云帆老師

微信：

云帆優培介紹

總結

以上是生活随笔為你收集整理的c++ 遍历所有点且距离最短_L3图论第08课 图的遍历的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。