C#圖表算法之有向圖
在有向圖中，邊是單向的：每條邊連接的兩個頂點都是一個有序?qū)?，它們的鄰接性是單向的。許多應(yīng)用都是天然的有向圖，如下圖。為實現(xiàn)添加這種單向性的限制很容易也很自然，看起來沒什么壞處。但實際上這種組合性的結(jié)構(gòu)對算法有深刻的影響，使得有向圖和無向圖的處理大有不同。
1.術(shù)語
雖然我們?yōu)橛邢驁D的定義和無向圖幾乎相同（將使用的部分算法和代碼也是），但為了說明邊的方向性而產(chǎn)生的細小文字差異所代表的結(jié)構(gòu)特性是重點。
定義：一幅有方向性的圖（或有向圖）是由一組頂點和一組有方向的邊組成的，每條有方向的邊都連著有序的一對頂點。
我們稱一條有向邊由第一個頂點指出并指向第二個頂點。在一幅有向圖中，一個頂點的出度為由該頂點指出的邊的總數(shù)；一個頂點的入度為指向該頂點的邊的總數(shù)。一條有向邊的第一個頂點稱為它的頭，第二個頂點則稱為它的尾。用 v->w 表示有向圖中一條由v 指向 w 的邊。一幅有向圖的兩個頂點的關(guān)系可能有四種：沒有邊相連；v->w; w-> v;v->w 和 w->v。
在一幅有向圖中，有向路徑由一系列頂點組成，對于其中的每個頂點都存在一條有向邊從它指向序列中的下一個頂點。有向環(huán)為一條至少含有一條邊且起點和終點相同的有向路徑。路徑或環(huán)的長度即為其中所包含的邊數(shù)。
當(dāng)存在從 v 到 w 的有向路徑時，稱頂點 w 能夠由頂點 v 達到。我們需要理解有向圖中的可達性和無向圖中的連通性的區(qū)別。
2.有向圖的數(shù)據(jù)類型
有向圖API
有向圖表示
我們使用鄰接表來表示有向圖，其中邊 v -> w 表示頂點 v 所對應(yīng)的鄰接鏈表中包含一個 w 頂點。這種表示方法和無向圖幾乎相同而且更明晰，因為每條邊都只會出現(xiàn)一次。
有向圖取反
Digraph 的 API 中還添加了一個 Reverse 方法。它返回該有向圖的一個副本，但將其中所有邊的方向反轉(zhuǎn)。在處理有向圖時這個方法有時很有用，因為這樣用例就可以找出“指向”每個頂點的所有邊，而 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 的有向路徑？）。
在添加了一個接受多個頂點的構(gòu)造函數(shù)之后，這份 API 使得用例能夠解決一個更加一般的問題 -- 多點可達性 （給定一幅有向圖和頂點的集合，是否存在一條從集合中的任意頂點到達給定頂點 v 的有向路徑？）
下面的DirectedDFS 算法使用了解決圖處理的標(biāo)準(zhǔn)范例和標(biāo)準(zhǔn)的深度優(yōu)先搜索來解決。對每個起點調(diào)用遞歸方法 Dfs ，以標(biāo)記遇到的任意頂點。
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)先搜索標(biāo)記由一個集合的頂點可達的所有頂點所需的時間與被標(biāo)記的所有頂點的出度之和成正比。
有向圖的尋路
在無向圖中的尋找路徑的算法，只需將 Graph 替換為 Digraph 就能夠解決下面問題：
- 1.單點有向路徑：給定一幅有向圖和一個起點 s ，從 s 到給定目的頂點是否存在一條有向路徑？如果有，找出這條路徑。
- 2.單點最短有向路徑：給定一幅有向圖和一個起點 s ，從 s 到給定目的頂點 v 是否存在一條有向路徑？如果有，找出其中最短的那條（所含邊數(shù)最少）。
4.環(huán)和有向無環(huán)圖
在和有向圖相關(guān)的實際應(yīng)用中，有向環(huán)特別的重要。沒有計算機的幫助，在一幅普通的有向圖中找出有向環(huán)可能會很困難。從原則上來說，一幅有向圖可能含有大量的環(huán)；在實際應(yīng)用中，我們一般只重點關(guān)注其中一小部分，或者只想知道它們是否存在。
調(diào)度問題
一種應(yīng)用廣泛的模型是給定一組任務(wù)并安排它們的執(zhí)行順序，限制條件是這些任務(wù)的執(zhí)行方法和開始時間。限制條件還可能包括任務(wù)的耗時以及消耗的資源。最重要的一種限制條件叫做優(yōu)先級限制，它指明了哪些任務(wù)必須在哪些任務(wù)之前完成。不同類型的限制條件會產(chǎn)生不同類型不同難度的調(diào)度問題。
下面以一個正在安排課程的大學(xué)生為例，有些課程是其他課程的先導(dǎo)課程：
如果假設(shè)該學(xué)生一次只能修一門課程，就會遇到優(yōu)先級下的調(diào)度問題：給定一組需要完成的任務(wù)，以及一組關(guān)于任務(wù)完成的先后次序的優(yōu)先級限制。在滿足限制條件的前提下應(yīng)該如何安排并完成所有任務(wù)？
對于任意一個這樣的問題，我們先畫出一幅有向圖，其中頂點對應(yīng)任務(wù)，有向邊對應(yīng)優(yōu)先級順序。為了簡化問題，我們以整數(shù)為頂點：
在有向圖中，優(yōu)先級限制下的調(diào)度問題等價于一個基本問題--拓撲排序：給定一幅圖，將所有頂點排序，使得所有的有向邊均從排在前面的元素指向排在后面的元素（或者說明無法做到這一點）。
如圖，所有的邊都是向下的，所以清晰地表示了這幅有向圖模型所代表的有優(yōu)先級限制的調(diào)度問題的一個解決方法：按照這個順序，該同學(xué)可以滿足先導(dǎo)課程限制的條件下修完所有課程。
有向圖中的環(huán)
如果任務(wù) x 必須在任務(wù) y 之前完成，而任務(wù) y 必須在任務(wù) z 之前完成，但任務(wù) z 又必須在任務(wù) x 之前完成，那肯定是有人搞錯了，因為這三個限制條件是不可能被同時滿足的。一般來說，如果一個優(yōu)先級限制的問題中存在有向環(huán)，那么這個問題肯定是無解的。要檢查這種錯誤，需要解決 有向環(huán)檢測：給定的有向圖中包含有向環(huán)嗎？如果有，按照路徑的方向從某個頂點并返回自己來找到環(huán)上的所有頂點。
一幅有向圖中含有環(huán)的數(shù)量可能是圖的大小的指數(shù)級別，因此我們只需找到一個環(huán)即可，而不是所有環(huán)。在任務(wù)調(diào)度和其他許多實際問題中不允許出現(xiàn)有向環(huán)，因此有向無環(huán)圖就變得很特殊。
基于深度優(yōu)先搜索可以解決有向環(huán)檢測的問題，因為由系統(tǒng)維護的遞歸調(diào)用的棧表示的正是“當(dāng)前”正在遍歷的有向路徑。一旦我們找到了一條有向邊 v -> w 且 w 已經(jīng)存在于棧中，就找到了一個環(huán)，因為棧表示的是一條由 w 到 v 的有向路徑，而 v -> w 正好補全了這個環(huán)。如果沒有找到這樣的邊，就意味著這副有向圖是無環(huán)的。DirectedCycle 基于這個思想實現(xiàn)的：
namespace Digraphs
{
public class DirectedCycle
{
private bool[] marked;
private int[] edgeTo;
private Stack<int> cycle;//有向環(huán)中的所有頂點（如果存在）
private bool[] onStack;//遞歸調(diào)用的棧上的所有頂點
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;
}
}
}該類為標(biāo)準(zhǔn)的的遞歸 Dfs 方法添加了一個布爾類型的數(shù)組 onStack 來保存遞歸調(diào)用期間棧上的所有頂點。當(dāng)它找到一條邊 v -> w 且 w 在棧中時，它就找到了一個有向環(huán)。環(huán)上的所有頂點可以通過 edgeTo 中的鏈接得到。
在執(zhí)行 Dfs 時，查找的是一條由起點到 v 的有向路徑。要保存這條路徑，DirectedCycle 維護了一個由頂點索引的數(shù)組onStack，以標(biāo)記遞歸調(diào)用的棧上的所有頂點（在調(diào)用 Dfs 時將 onStack[ v ] 設(shè)為 true,在調(diào)用結(jié)束時將其設(shè)為 false）。DirectedCycle 同時也使用了一個edgeTo 數(shù)組，在找到有向環(huán)時返回環(huán)中的所有頂點。
頂點的深度優(yōu)先次序與拓撲排序
優(yōu)先級限制下的調(diào)度問題等價于計算有向無環(huán)圖中的所有頂點的拓撲排序：
下面算法的基本思想是深度優(yōu)先搜索正好只會訪問每個頂點一次。如果將 Dfs 的參數(shù)頂點保存在一個數(shù)據(jù)結(jié)構(gòu)中，遍歷這個數(shù)據(jù)結(jié)構(gòu)實際上就能訪問圖中的所有頂點，遍歷的順序取決于這個數(shù)據(jù)結(jié)構(gòu)的性質(zhì)以及是在遞歸調(diào)用之前還是之后進行保存。在典型的應(yīng)用中，頂點一下三種排列順序：
- 前序：在遞歸調(diào)用之前將頂點加入隊列；
- 后序：在遞歸調(diào)用之后將頂點加入隊列；
- 逆后序：在遞歸調(diào)用之后將頂點壓入棧。
該類允許用例用各種順序遍歷深度優(yōu)先搜索經(jīng)過得頂點。這在高級得有向圖處理算法非常有用，因為搜索得遞歸性使得我們能夠證明這段計算得許多性質(zhì)。
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)先搜索產(chǎn)生了頂點的逆后序排列。
在實際應(yīng)用中，拓撲排序和有向環(huán)的檢測總是一起出現(xiàn)，因為有向環(huán)的檢測是排序的前提。例如，在一個任務(wù)調(diào)度應(yīng)用中，無論計劃如何安排，其背后的有向圖中包含的環(huán)意味著存在一個必須被糾正的嚴(yán)重錯誤。因此，解決任務(wù)調(diào)度類應(yīng)用通常需要一下3步：
- 1.指明任務(wù)和優(yōu)先級條件；
- 2.不斷檢測并去除有向圖中的所有環(huán)，以確保存在可行方案；
- 3.使用拓撲排序解決調(diào)度問題。
類似地，調(diào)度方案的任何變動之后都需要再次檢查是否存在環(huán)，然后再計算新的調(diào)度安排。
5.有向圖中的強連通性
如果兩個頂點 v 和 w 是相互可達的，則稱它們?yōu)閺娺B通的。也就是說，即存在一條從 v 到 w 的有向路徑，也存在一條從 w 到 v 的有向路徑。如果一幅有向圖中的任意兩個頂點都是強連通的，則稱這副有向圖也是強連通的。
下面是強連通圖的例子，可以看到，環(huán)在強連通性的理解上起著重要的作用。
強連通分量
和無向圖中的連通性一樣，有向圖中的強連通性也是一種頂點之間的等價關(guān)系：
- 自反性：任意頂點 v 和自己都是強連通的。
- 對稱性：如果 v 和 w 是強連通的，那么 w 和 v 也是。
- 傳遞性：如果 v 和 w 是強連通的且 w 和 x 也是強連通的，那么 v 和 x 也是強連通的。
作為一種等價關(guān)系，強連通性將所有頂點分為了一些等價類，每個等價類都是由相互均為強連通的頂點的最大子集組成。我們稱這些子集為強連通分量。如下圖，一個含有 V 個頂點的有向圖含有 1~ V個強連通分量——一個強連通圖只含有一個強連通分量，而一個有向無環(huán)圖則含有 V 個強連通分量。需要注意的是強連通分量的定義是基于頂點的，而不是邊。有些邊連接的兩個頂點都在同一個強連通分量中，而有些邊連接的兩個頂點則不在同一強連通分量中。
強連通分量API
設(shè)計一種平方級別的算法來計算強連通分量并不困難，單對于處理實際應(yīng)用中的大型圖來說，平方級別的時間和空間需求是不可接受的。
Kosaraju算法
在有向圖中如何高效地計算強連通分量？我們只需修改無向圖連通分量的算法 CC，KosarajuCC 算法如下，它將會完成一下任務(wù)：
1.在給定的一幅有向圖 G 中，使用 DepthFirstOrder 來計算它的反向圖 GR 的逆后序排列；
2.在 G 中進行標(biāo)準(zhǔn)的深度優(yōu)先搜索，但是要按照剛才計算得到的順序而非標(biāo)準(zhǔn)的順序來訪問所有未被標(biāo)記的頂點；
3.在構(gòu)造函數(shù)中，所有在同一個遞歸 Dfs() 調(diào)用中被訪問到的頂點都在同一個強連通分量中，將它們按照和 CC 相同的方式識別出來。
namespace Digraphs
{
public class KosarajuCC
{
private bool[] marked;//已訪問的頂點
private int[] id;//強連通分量的標(biāo)識符
private int count;//強連通分量的數(shù)量
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 算法的預(yù)處理所需的時間和空間與 V+E 成正比且支持常數(shù)時間的有向圖強連通性的查詢。
再談可達性
在無向圖中如果兩個頂點 V 和 W 是連通的，那么就既存在一條從 v 到 w 的路徑也存在一條從 w 到 v 的路徑。在有向圖中如果兩個頂點 v 和 w 是強連通的，那么就既存在一條從 v 到 w 的路徑也存在另一條從 w 到 v 的路徑。但對于一對非強連通的頂點，也許存在一條從 v 到 w 的路徑，也許存在一條從 w 到 v 的路徑，也許兩條都不存在，但不可能兩條都存在。
頂點對的可達性：對于無向圖，等價于連通性問題；對于有向圖，它和強連通性有很大區(qū)別。 CC 實現(xiàn)需要線性級別的預(yù)處理時間才能支持常數(shù)時間的操作。在有向圖的相應(yīng)實現(xiàn)中能否達到這樣的性能？
有向圖 G 的傳遞閉包是由相同的一組頂點組成的另一幅有向圖，在傳遞閉包中存在一條從 v 指向 w 的邊當(dāng)且僅當(dāng)在 G 中 w 是從 v 可達的。
根據(jù)約定，每個頂點對于自己都是可達的，因此傳遞閉包會含有 V 個自環(huán)。上圖只有 22 條有向邊，但它的傳遞閉包含有可能的 169 條有向邊中的 102 條。一般來說，一幅有向圖的傳遞閉包中所含的邊都比原圖中多得多。例如，含有 V 個頂點和 V 條邊的有向環(huán)的傳遞閉包是一幅含有 V 的平方條邊的有向完全圖。因為傳遞閉包一般都是稠密的，我們通常都將它們表示為一個布爾值矩陣，其中 v 行 w 列的值為 true 當(dāng)且僅當(dāng) w 是從 v 可達的。與其計算一幅有向圖的傳遞閉包，不如使用深度優(yōu)先搜索來實現(xiàn)如下API：
下面的算法使用DirectedDFS 實現(xiàn)：
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);
}
}
}該算法無論對于稀疏圖還是稠密圖，都是理想解決方案，但對于大型有向圖不適用，因為構(gòu)造函數(shù)所需的空間和 V 的平方成正比，所需的時間和 V(V+ E) 成正比。
總結(jié)
到此這篇關(guān)于C#圖表算法之有向圖的文章就介紹到這了。希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了C#中l(wèi)ock死鎖的用法,對于共享資源的訪問及C#程序設(shè)計的安全性而言,有著非常重要的意義！需要的朋友可以參考下2014-08-08
UGUI?可視化創(chuàng)建以及關(guān)聯(lián)事件很方便,?動態(tài)創(chuàng)建可以利用創(chuàng)建好的?Prefab?進行實例化,?只是在關(guān)聯(lián)事件上有些復(fù)雜,這篇文章主要介紹了Unity?UGUI?按鈕綁定事件的?4?種方式,需要的朋友可以參考下2022-01-01
下面小編就為大家?guī)硪黄P(guān)于C#中排序函數(shù)的總結(jié)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-05-05
亂碼視頻效果可能很多人都在抖音看到過，即把一個短視頻，轉(zhuǎn)成數(shù)字、字母等亂碼組成的形式進行播放。本文將用C#實現(xiàn)一下這一效果，感興趣的可以了解一下2023-01-01
這篇文章主要介紹了C# 實現(xiàn)特殊字符快速轉(zhuǎn)碼，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-01-01
C#獲取DataTable對象狀態(tài)DataRowState
這篇文章介紹了C#獲取DataTable對象狀態(tài)DataRowState的方法，文中通過示例代碼介紹的非常詳細。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-02-02
這篇文章主要為大家詳細介紹了C#合并及拆分PDF文件的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-01-01
這篇文章主要介紹了C# 程序自刪除實現(xiàn)方法，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
本文將詳細介紹SQL語句刪除和添加外鍵、主鍵的方法，需要的朋友可以參考下2012-11-11
這篇文章主要為大家詳細介紹了unity使用鏈表實現(xiàn)貪吃蛇游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04