C#圖表算法之有向圖
在有向圖中，邊是單向的：每條邊連接的兩個頂點都是一個有序對，它們的鄰接性是單向的。許多應用都是天然的有向圖，如下圖。為實現添加這種單向性的限制很容易也很自然，看起來沒什么壞處。但實際上這種組合性的結構對算法有深刻的影響，使得有向圖和無向圖的處理大有不同。
1.術語
雖然我們?yōu)橛邢驁D的定義和無向圖幾乎相同（將使用的部分算法和代碼也是），但為了說明邊的方向性而產生的細小文字差異所代表的結構特性是重點。
定義：一幅有方向性的圖（或有向圖）是由一組頂點和一組有方向的邊組成的，每條有方向的邊都連著有序的一對頂點。
我們稱一條有向邊由第一個頂點指出并指向第二個頂點。在一幅有向圖中，一個頂點的出度為由該頂點指出的邊的總數；一個頂點的入度為指向該頂點的邊的總數。一條有向邊的第一個頂點稱為它的頭，第二個頂點則稱為它的尾。用 v->w 表示有向圖中一條由v 指向 w 的邊。一幅有向圖的兩個頂點的關系可能有四種：沒有邊相連；v->w; w-> v;v->w 和 w->v。
在一幅有向圖中，有向路徑由一系列頂點組成，對于其中的每個頂點都存在一條有向邊從它指向序列中的下一個頂點。有向環(huán)為一條至少含有一條邊且起點和終點相同的有向路徑。路徑或環(huán)的長度即為其中所包含的邊數。
當存在從 v 到 w 的有向路徑時，稱頂點 w 能夠由頂點 v 達到。我們需要理解有向圖中的可達性和無向圖中的連通性的區(qū)別。
2.有向圖的數據類型
有向圖API
有向圖表示
我們使用鄰接表來表示有向圖，其中邊 v -> w 表示頂點 v 所對應的鄰接鏈表中包含一個 w 頂點。這種表示方法和無向圖幾乎相同而且更明晰，因為每條邊都只會出現一次。
有向圖取反
Digraph 的 API 中還添加了一個 Reverse 方法。它返回該有向圖的一個副本，但將其中所有邊的方向反轉。在處理有向圖時這個方法有時很有用，因為這樣用例就可以找出“指向”每個頂點的所有邊，而 Adj 方法給出的是由每個頂點指出的邊所連接的所有頂點。
頂點的符號名
在有向圖中，使用符號名作為頂點也很簡單，參考SymbolGraph。
namespace Digraphs
{
public class Digraph
{
private int v;
private int e;
private List<int>[] adj;
public Digraph(int V)
{
this.v = V;
this.e = 0;
adj = new List<int>[v];
for (var i = 0; i < v; i++)
{
adj[i] = new List<int>();
}
}
public int V()
{
return v;
}
public int E()
{
return e;
}
public List<int> Adj(int v)
{
return adj[v];
}
public void AddEdge(int v, int w)
{
adj[v].Add(w);
e++;
}
public Digraph Reverse()
{
Digraph R = new Digraph(v);
for (var i = 0; i < v; i++)
foreach (var w in Adj(i))
R.AddEdge(w,i);
return R;
}
}
}3.有向圖的可達性
在無向圖中介紹的深度優(yōu)先搜索DepthFirstSearch ，解決了單點連通性的問題，使得用例可以判定其他頂點和給定的起點是否連通。使用完全相同的代碼，將其中的 Graph 替換成 Digraph 也可以解決有向圖中的單點可達性問題（給定一幅有向圖和一個起點 s ，是否存在一條從 s 到達給定頂點 v 的有向路徑？）。
在添加了一個接受多個頂點的構造函數之后，這份 API 使得用例能夠解決一個更加一般的問題 -- 多點可達性 （給定一幅有向圖和頂點的集合，是否存在一條從集合中的任意頂點到達給定頂點 v 的有向路徑？）
下面的DirectedDFS 算法使用了解決圖處理的標準范例和標準的深度優(yōu)先搜索來解決。對每個起點調用遞歸方法 Dfs ，以標記遇到的任意頂點。
namespace Digraphs
{
public class DirectedDFS
{
private bool[] marked;
public DirectedDFS(Digraph G, int s)
{
marked = new bool[G.V()];
Dfs(G,s);
}
public DirectedDFS(Digraph G, IEnumerable<int> sources)
{
marked = new bool[G.V()];
foreach (var s in sources)
{
if (!marked[s])
Dfs(G,s);
}
}
private void Dfs(Digraph G, int V)
{
marked[V] = true;
foreach (var w in G.Adj(V))
{
if (!marked[w])
Dfs(G,w);
}
}
public bool Marked(int v)
{
return marked[v];
}
}
}在有向圖中，深度優(yōu)先搜索標記由一個集合的頂點可達的所有頂點所需的時間與被標記的所有頂點的出度之和成正比。
有向圖的尋路
在無向圖中的尋找路徑的算法，只需將 Graph 替換為 Digraph 就能夠解決下面問題：
- 1.單點有向路徑：給定一幅有向圖和一個起點 s ，從 s 到給定目的頂點是否存在一條有向路徑？如果有，找出這條路徑。
- 2.單點最短有向路徑：給定一幅有向圖和一個起點 s ，從 s 到給定目的頂點 v 是否存在一條有向路徑？如果有，找出其中最短的那條（所含邊數最少）。
4.環(huán)和有向無環(huán)圖
在和有向圖相關的實際應用中，有向環(huán)特別的重要。沒有計算機的幫助，在一幅普通的有向圖中找出有向環(huán)可能會很困難。從原則上來說，一幅有向圖可能含有大量的環(huán)；在實際應用中，我們一般只重點關注其中一小部分，或者只想知道它們是否存在。
調度問題
一種應用廣泛的模型是給定一組任務并安排它們的執(zhí)行順序，限制條件是這些任務的執(zhí)行方法和開始時間。限制條件還可能包括任務的耗時以及消耗的資源。最重要的一種限制條件叫做優(yōu)先級限制，它指明了哪些任務必須在哪些任務之前完成。不同類型的限制條件會產生不同類型不同難度的調度問題。
下面以一個正在安排課程的大學生為例，有些課程是其他課程的先導課程：
如果假設該學生一次只能修一門課程，就會遇到優(yōu)先級下的調度問題：給定一組需要完成的任務，以及一組關于任務完成的先后次序的優(yōu)先級限制。在滿足限制條件的前提下應該如何安排并完成所有任務？
對于任意一個這樣的問題，我們先畫出一幅有向圖，其中頂點對應任務，有向邊對應優(yōu)先級順序。為了簡化問題，我們以整數為頂點：
在有向圖中，優(yōu)先級限制下的調度問題等價于一個基本問題--拓撲排序：給定一幅圖，將所有頂點排序，使得所有的有向邊均從排在前面的元素指向排在后面的元素（或者說明無法做到這一點）。
如圖，所有的邊都是向下的，所以清晰地表示了這幅有向圖模型所代表的有優(yōu)先級限制的調度問題的一個解決方法：按照這個順序，該同學可以滿足先導課程限制的條件下修完所有課程。
有向圖中的環(huán)
如果任務 x 必須在任務 y 之前完成，而任務 y 必須在任務 z 之前完成，但任務 z 又必須在任務 x 之前完成，那肯定是有人搞錯了，因為這三個限制條件是不可能被同時滿足的。一般來說，如果一個優(yōu)先級限制的問題中存在有向環(huán)，那么這個問題肯定是無解的。要檢查這種錯誤，需要解決 有向環(huán)檢測：給定的有向圖中包含有向環(huán)嗎？如果有，按照路徑的方向從某個頂點并返回自己來找到環(huán)上的所有頂點。
一幅有向圖中含有環(huán)的數量可能是圖的大小的指數級別，因此我們只需找到一個環(huán)即可，而不是所有環(huán)。在任務調度和其他許多實際問題中不允許出現有向環(huán)，因此有向無環(huán)圖就變得很特殊。
基于深度優(yōu)先搜索可以解決有向環(huán)檢測的問題，因為由系統維護的遞歸調用的棧表示的正是“當前”正在遍歷的有向路徑。一旦我們找到了一條有向邊 v -> w 且 w 已經存在于棧中，就找到了一個環(huán)，因為棧表示的是一條由 w 到 v 的有向路徑，而 v -> w 正好補全了這個環(huán)。如果沒有找到這樣的邊，就意味著這副有向圖是無環(huán)的。DirectedCycle 基于這個思想實現的：
namespace Digraphs
{
public class DirectedCycle
{
private bool[] marked;
private int[] edgeTo;
private Stack<int> cycle;//有向環(huán)中的所有頂點（如果存在）
private bool[] onStack;//遞歸調用的棧上的所有頂點
public DirectedCycle(Digraph G)
{
onStack = new bool[G.V()];
edgeTo = new int[G.V()];
marked = new bool[G.V()];
for (int v = 0; v < G.V(); v++)
{
if (!marked[v])
Dfs(G,v);
}
}
private void Dfs(Digraph G, int v)
{
onStack[v] = true;
marked[v] = true;
foreach (var w in G.Adj(v))
{
if (hasCycle())
return;
else if (!marked[w])
{
edgeTo[w] = v;
Dfs(G, w);
}
else if (onStack[w])
{
cycle = new Stack<int>();
for (int x = v; x != w; x = edgeTo[x])
cycle.Push(x);
cycle.Push(w);
cycle.Push(v);
}
}
onStack[v] = false;
}
private bool hasCycle()
{
return cycle != null;
}
public IEnumerable<int> Cycle()
{
return cycle;
}
}
}該類為標準的的遞歸 Dfs 方法添加了一個布爾類型的數組 onStack 來保存遞歸調用期間棧上的所有頂點。當它找到一條邊 v -> w 且 w 在棧中時，它就找到了一個有向環(huán)。環(huán)上的所有頂點可以通過 edgeTo 中的鏈接得到。
在執(zhí)行 Dfs 時，查找的是一條由起點到 v 的有向路徑。要保存這條路徑，DirectedCycle 維護了一個由頂點索引的數組onStack，以標記遞歸調用的棧上的所有頂點（在調用 Dfs 時將 onStack[ v ] 設為 true,在調用結束時將其設為 false）。DirectedCycle 同時也使用了一個edgeTo 數組，在找到有向環(huán)時返回環(huán)中的所有頂點。
頂點的深度優(yōu)先次序與拓撲排序
優(yōu)先級限制下的調度問題等價于計算有向無環(huán)圖中的所有頂點的拓撲排序：
下面算法的基本思想是深度優(yōu)先搜索正好只會訪問每個頂點一次。如果將 Dfs 的參數頂點保存在一個數據結構中，遍歷這個數據結構實際上就能訪問圖中的所有頂點，遍歷的順序取決于這個數據結構的性質以及是在遞歸調用之前還是之后進行保存。在典型的應用中，頂點一下三種排列順序：
- 前序：在遞歸調用之前將頂點加入隊列；
- 后序：在遞歸調用之后將頂點加入隊列；
- 逆后序：在遞歸調用之后將頂點壓入棧。
該類允許用例用各種順序遍歷深度優(yōu)先搜索經過得頂點。這在高級得有向圖處理算法非常有用，因為搜索得遞歸性使得我們能夠證明這段計算得許多性質。
namespace Digraphs
{
public class DepthFirstOrder
{
private bool[] marked;
private Queue<int> pre;//所有頂點的前序排列
private Queue<int> post;//所有頂點的后序排列
private Stack<int> reversePost;//所有頂點的逆后序排列
public DepthFirstOrder(Digraph G)
{
marked = new bool[G.V()];
pre = new Queue<int>();
post = new Queue<int>();
reversePost = new Stack<int>();
for (var v = 0; v < G.V(); v++)
{
if (!marked[v])
Dfs(G,v);
}
}
private void Dfs(Digraph G, int v)
{
pre.Enqueue(v);
marked[v] = true;
foreach (var w in G.Adj(v))
{
if (!marked[w])
Dfs(G,w);
}
post.Enqueue(v);
reversePost.Push(v);
}
public IEnumerable<int> Pre()
{
return pre;
}
public IEnumerable<int> Post()
{
return post;
}
public IEnumerable<int> ReversePost()
{
return reversePost;
}
}
}
一幅有向無環(huán)圖得拓撲排序即為所有頂點的逆后序排列。
拓撲排序
namespace Digraphs
{
public class Topological
{
private IEnumerable<int> order;
public Topological(Digraph G)
{
DirectedCycle cycleFinder = new DirectedCycle(G);
if (cycleFinder.HasCycle())
{
DepthFirstOrder dfs = new DepthFirstOrder(G);
order = dfs.ReversePost();
}
}
public IEnumerable<int> Order()
{
return order;
}
public bool IsDAG()
{
return order != null;
}
}
}這段使用DirectedCycle 檢測是否有環(huán)，使用DepthFirstOrder 返回有向圖的逆后序。
使用深度優(yōu)先搜索對有向無環(huán)圖進行拓撲排序所需的時間和 V+E 成正比。第一遍深度優(yōu)先搜索保證了不存在有向環(huán)，第二遍深度優(yōu)先搜索產生了頂點的逆后序排列。
在實際應用中，拓撲排序和有向環(huán)的檢測總是一起出現，因為有向環(huán)的檢測是排序的前提。例如，在一個任務調度應用中，無論計劃如何安排，其背后的有向圖中包含的環(huán)意味著存在一個必須被糾正的嚴重錯誤。因此，解決任務調度類應用通常需要一下3步：
- 1.指明任務和優(yōu)先級條件；
- 2.不斷檢測并去除有向圖中的所有環(huán)，以確保存在可行方案；
- 3.使用拓撲排序解決調度問題。
類似地，調度方案的任何變動之后都需要再次檢查是否存在環(huán)，然后再計算新的調度安排。
5.有向圖中的強連通性
如果兩個頂點 v 和 w 是相互可達的，則稱它們?yōu)閺娺B通的。也就是說，即存在一條從 v 到 w 的有向路徑，也存在一條從 w 到 v 的有向路徑。如果一幅有向圖中的任意兩個頂點都是強連通的，則稱這副有向圖也是強連通的。
下面是強連通圖的例子，可以看到，環(huán)在強連通性的理解上起著重要的作用。
強連通分量
和無向圖中的連通性一樣，有向圖中的強連通性也是一種頂點之間的等價關系：
- 自反性：任意頂點 v 和自己都是強連通的。
- 對稱性：如果 v 和 w 是強連通的，那么 w 和 v 也是。
- 傳遞性：如果 v 和 w 是強連通的且 w 和 x 也是強連通的，那么 v 和 x 也是強連通的。
作為一種等價關系，強連通性將所有頂點分為了一些等價類，每個等價類都是由相互均為強連通的頂點的最大子集組成。我們稱這些子集為強連通分量。如下圖，一個含有 V 個頂點的有向圖含有 1~ V個強連通分量——一個強連通圖只含有一個強連通分量，而一個有向無環(huán)圖則含有 V 個強連通分量。需要注意的是強連通分量的定義是基于頂點的，而不是邊。有些邊連接的兩個頂點都在同一個強連通分量中，而有些邊連接的兩個頂點則不在同一強連通分量中。
強連通分量API
設計一種平方級別的算法來計算強連通分量并不困難，單對于處理實際應用中的大型圖來說，平方級別的時間和空間需求是不可接受的。
Kosaraju算法
在有向圖中如何高效地計算強連通分量？我們只需修改無向圖連通分量的算法 CC，KosarajuCC 算法如下，它將會完成一下任務：
1.在給定的一幅有向圖 G 中，使用 DepthFirstOrder 來計算它的反向圖 GR 的逆后序排列；
2.在 G 中進行標準的深度優(yōu)先搜索，但是要按照剛才計算得到的順序而非標準的順序來訪問所有未被標記的頂點；
3.在構造函數中，所有在同一個遞歸 Dfs() 調用中被訪問到的頂點都在同一個強連通分量中，將它們按照和 CC 相同的方式識別出來。
namespace Digraphs
{
public class KosarajuCC
{
private bool[] marked;//已訪問的頂點
private int[] id;//強連通分量的標識符
private int count;//強連通分量的數量
public KosarajuCC(Digraph G)
{
marked = new bool[G.V()];
id = new int[G.V()];
DepthFirstOrder order = new DepthFirstOrder(G.Reverse());
foreach (var s in order.ReversePost())
{
if (!marked[s])
{
Dfs(G,s);
count++;
}
}
}
private void Dfs(Digraph G, int v)
{
marked[v] = true;
id[v] = count;
foreach (var w in G.Adj(v))
{
if (!marked[w])
Dfs(G,w);
}
}
public bool StronglyConnected(int v, int w)
{
return id[v] == id[w];
}
public int Id(int v)
{
return id[v];
}
public int Count()
{
return count;
}
}
}
Kosaraju 算法的預處理所需的時間和空間與 V+E 成正比且支持常數時間的有向圖強連通性的查詢。
再談可達性
在無向圖中如果兩個頂點 V 和 W 是連通的，那么就既存在一條從 v 到 w 的路徑也存在一條從 w 到 v 的路徑。在有向圖中如果兩個頂點 v 和 w 是強連通的，那么就既存在一條從 v 到 w 的路徑也存在另一條從 w 到 v 的路徑。但對于一對非強連通的頂點，也許存在一條從 v 到 w 的路徑，也許存在一條從 w 到 v 的路徑，也許兩條都不存在，但不可能兩條都存在。
頂點對的可達性：對于無向圖，等價于連通性問題；對于有向圖，它和強連通性有很大區(qū)別。 CC 實現需要線性級別的預處理時間才能支持常數時間的操作。在有向圖的相應實現中能否達到這樣的性能？
有向圖 G 的傳遞閉包是由相同的一組頂點組成的另一幅有向圖，在傳遞閉包中存在一條從 v 指向 w 的邊當且僅當在 G 中 w 是從 v 可達的。
根據約定，每個頂點對于自己都是可達的，因此傳遞閉包會含有 V 個自環(huán)。上圖只有 22 條有向邊，但它的傳遞閉包含有可能的 169 條有向邊中的 102 條。一般來說，一幅有向圖的傳遞閉包中所含的邊都比原圖中多得多。例如，含有 V 個頂點和 V 條邊的有向環(huán)的傳遞閉包是一幅含有 V 的平方條邊的有向完全圖。因為傳遞閉包一般都是稠密的，我們通常都將它們表示為一個布爾值矩陣，其中 v 行 w 列的值為 true 當且僅當 w 是從 v 可達的。與其計算一幅有向圖的傳遞閉包，不如使用深度優(yōu)先搜索來實現如下API：
下面的算法使用DirectedDFS 實現：
namespace Digraphs
{
public class TransitiveClosure
{
private DirectedDFS[] all;
public TransitiveClosure(Digraph G)
{
all = new DirectedDFS[G.V()];
for (var v = 0; v < G.V(); v++)
all[v] = new DirectedDFS(G,v);
}
public bool Reachable(int v, int w)
{
return all[v].Marked(w);
}
}
}該算法無論對于稀疏圖還是稠密圖，都是理想解決方案，但對于大型有向圖不適用，因為構造函數所需的空間和 V 的平方成正比，所需的時間和 V(V+ E) 成正比。
總結
到此這篇關于C#圖表算法之有向圖的文章就介紹到這了。希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了Unity2019 2020安裝教程,本文分步驟通過圖文并茂的形式給大家介紹Unity2019 2020安裝方法，需要的朋友可以參考下2021-05-05
C#書寫規(guī)范...2007-03-03
本文主要介紹了使用VS2019生成C#應用安裝包的方法步驟，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-05-05
Shader，中文名為著色器，對很多開發(fā)者來說它是一個神秘的存在。Shader其實就是專門用來渲染圖形的一種技術，通過shader，我們可以自定義顯卡渲染畫面的算法，使畫面達到我們想要的效果2021-06-06
這篇文章主要為大家詳細介紹了C#實現Nginx平滑加權輪詢算法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-07-07
現在已知兩個文件相對于網站根目錄的路徑，如何計算相對路徑呢，有需要的朋友可以參考一下2013-09-09
這篇文章主要介紹了C#流程控制詳解，文章圍繞主題展開詳細的內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-07-07
在 C# 中,virtual?關鍵字用于修飾方法、屬性、索引器或事件,這篇文章主要介紹了c#中的virtual方法及應用場景分析,需要的朋友可以參考下2025-03-03
這篇文章主要介紹了C#給Word不同頁面設置不同背景，文章圖文講解的很清晰，有對于這方面不懂得同學可以學習下2021-02-02
String和string的區(qū)別有哪些，想有很多朋友都不知道吧，在本文將為大家詳細介紹下，感興趣的朋友可以參考下，希望對大家有所幫助2013-10-10