拓撲演算法

① 程序、演算法與拓撲結構之間的關系

你說的拓撲結構應該是數據結構吧

那麼程序=演算法+數據結構

② 網路拓撲圖 如何和優化演算法聯系起來

遺傳學不太懂，拓撲圖常應用於網路，編程基於流程圖，如果你能把網路拓撲圖以流程圖的形式表繪制出來的話，你的程序不就出來了嗎？

③ 拓撲排序的應用

一個復雜的工程通常可以分解成一組小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務之間具有先後關系，例如在裝軸之前必須先將底板放上裝配線。任務的先後順序可用有向圖表示——稱為頂點活動（ Activity On Vertex, AOV）網路。有向圖的頂點代表任務，有向邊(i, j) 表示先後關系：任務j 開始前任務i 必須完成。圖1 - 4顯示了六個任務的工程，邊（ 1 , 4）表示任務1在任務4開始前完成，同樣邊（ 4 , 6）表示任務4在任務6開始前完成，邊（1 , 4）與（4 , 6）合起來可知任務1在任務6開始前完成，即前後關系是傳遞的。由此可知，邊（1 , 4）是多餘的，因為邊（1 , 3）和（3 , 4）已暗示了這種關系。

在很多條件下，任務的執行是連續進行的，例如汽車裝配問題或平時購買的標有「需要裝配」的消費品（自行車、小孩的鞦韆裝置，割草機等等）。我們可根據所建議的順序來裝配。在由任務建立的有向圖中，邊（ i, j）表示在裝配序列中任務i 在任務j 的前面，具有這種性質的序列稱為拓撲序列（topological orders或topological sequences)。根據任務的有向圖建立拓撲序列的過程稱為拓撲排序（topological sorting）。圖1 - 4的任務有向圖有多種拓撲序列，其中的三種為1 2 3 4 5 6，1 3 2 4 5 6和2 1 5 3 4 6，序列1 4 2 3 5 6就不是拓撲序列，因為在這個序列中任務4在3的前面，而任務有向圖中的邊為（ 3 , 4），這種序列與邊（ 3 , 4）及其他邊所指示的序列相矛盾。可用貪婪演算法來建立拓撲序列。演算法按從左到右的步驟構造拓撲序列，每一步在排好的序列中加入一個頂點。利用如下貪婪准則來選擇頂點：從剩下的頂點中，選擇頂點w，使得w 不存在這樣的入邊（ v,w），其中頂點v 不在已排好的序列結構中出現。注意到如果加入的頂點w違背了這個准則（即有向圖中存在邊（ v,w）且v 不在已構造的序列中），則無法完成拓撲排序，因為頂點v 必須跟隨在頂點w 之後。貪婪演算法的偽代碼如圖1 3 - 5所示。while 循環的每次迭代代表貪婪演算法的一個步驟。

現在用貪婪演算法來求解圖1 - 4的有向圖。首先從一個空序列V開始，第一步選擇V的第一個頂點。此時，在有向圖中有兩個候選頂點1和2，若選擇頂點2，則序列V = 2，第一步完成。第二步選擇V的第二個頂點，根據貪婪准則可知候選頂點為1和5，若選擇5，則V = 2 5。下一步，頂點1是唯一的候選，因此V = 2 5 1。第四步，頂點3是唯一的候選，因此把頂點3加入V

得到V = 2 5 1 3。在最後兩步分別加入頂點4和6 ，得V = 2 5 1 3 4 6。

1. 貪婪演算法的正確性

為保證貪婪演算法算的正確性，需要證明： 1) 當演算法失敗時，有向圖沒有拓撲序列； 2) 若

演算法沒有失敗，V即是拓撲序列。2) 即是用貪婪准則來選取下一個頂點的直接結果， 1) 的證明見定理1 3 - 2，它證明了若演算法失敗，則有向圖中有環路。若有向圖中包含環qj qj + 1.qk qj , 則它沒有拓撲序列，因為該序列暗示了qj 一定要在qj 開始前完成。

定理1-2 如果圖1 3 - 5演算法失敗，則有向圖含有環路。

證明注意到當失敗時| V |<n, 且沒有候選頂點能加入V中，因此至少有一個頂點q1 不在V中，有向圖中必包含邊（ q2 , q1）且q2 不在V中，否則， q1 是可加入V的候選頂點。同樣，必有邊（q3 , q2）使得q3 不在V中，若q3 = q1 則q1 q2 q3 是有向圖中的一個環路；若q3 ≠q1，則必存在q4 使（q4 , q3）是有向圖的邊且q4 不在V中，否則，q3 便是V的一個候選頂點。若q4 為q1 , q2 , q3 中的任何一個，則又可知有向圖含有環，因為有向圖具有有限個頂點數n，繼續利用上述方法，最後總能找到一個環路。

2. 數據結構的選擇

為將圖1 - 5用C + +代碼來實現，必須考慮序列V的描述方法，以及如何找出可加入V的候選頂點。一種高效的實現方法是將序列V用一維數組v 來描述的，用一個棧來保存可加入V的候選頂點。另有一個一維數組I n D e g r e e，I n D e g r e e[ j ]表示與頂點j相連的節點i 的數目，其中頂點i不是V中的成員，它們之間的有向圖的邊表示為（ i, j）。當I n D e g r e e[ j ]變為0時表示j 成為一個候選節點。序列V初始時為空。I n D e g r e e[ j ]為頂點j 的入度。每次向V中加入一個頂點時，所有與新加入頂點鄰接的頂點j，其I n D e g r e e[ j ]減1。對於有向圖1 - 4，開始時I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 3 , 1 , 3 ]。由於頂點1和2的I n D e g r e e值為0，因此它們是可加入V的候選頂點，由此，頂點1和2首先入棧。每一步，從棧中取出一個頂點將其加入V，同時減去與其鄰接的頂點的I n D e g r e e值。若在第一步時從棧中取出頂點2並將其加入V，便得到了v [ 0 ] = 2，和I n D e g r e e [ 1 : 6 ] = [ 0 , 0 , 1 , 2 , 0 , 3 ]。由於I n D e g r e e [ 5 ]剛剛變為0，因此將頂點5入棧。

程序1 3 - 2給出了相應的C + +代碼，這個代碼被定義為N e t w o r k的一個成員函數。而且，它對於有無加權的有向圖均適用。但若用於無向圖（不論其有無加權）將會得到錯誤的結果，因為拓撲排序是針對有向圖來定義的。為解決這個問題，利用同樣的模板來定義成員函數AdjacencyGraph, AdjacencyWGraph，L i n k e d G r a p h和L i n k e d W G r a p h。這些函數可重載N e t w o r k中的函數並可輸出錯誤信息。如果找到拓撲序列，則Topological 函數返回t r u e；若輸入的有向圖無拓撲序列則返回f a l s e。當找到拓撲序列時，將其返回到v [ 0 :n- 1 ]中。

3. Network:Topological 的復雜性

第一和第三個f o r循環的時間開銷為(n )。若使用（耗費）鄰接矩陣,則第二個for 循環所用的時間為(n2 )；若使用鄰接鏈表,則所用時間為(n+e)。在兩個嵌套的while 循環中，外層循環需執行n次，每次將頂點w 加入到v 中，並初始化內層while 循環。使用鄰接矩陣時，內層w h i l e循環對於每個頂點w 需花費(n)的時間；若利用鄰接鏈表，則這個循環需花費dwout 的時間，因此，內層while 循環的時間開銷為(n2 )或(n+e)。所以，若利用鄰接矩陣，程序1 3 - 2的時間復雜性為(n2 )，若利用鄰接鏈表則為(n+e)。

程序13-2 拓撲排序

bool Network::Topological(int v[])

{// 計算有向圖中頂點的拓撲次序

// 如果找到了一個拓撲次序，則返回t r u e，此時，在v [ 0 : n - 1 ]中記錄拓撲次序

// 如果不存在拓撲次序，則返回f a l s e

int n = Ve r t i c e s ( ) ;

// 計算入度

int *InDegree = new int [n+1];

InitializePos(); // 圖遍歷器數組

for (int i = 1; i <= n; i++) // 初始化

InDegree[i] = 0;

for (i = 1; i <= n; i++) {// 從i 出發的邊

int u = Begin(i);

while (u) {

I n D e g r e e [ u ] + + ;

u = NextVe r t e x ( i ) ; }

}

// 把入度為0的頂點壓入堆棧

LinkedStack<int> S;

for (i = 1; i <= n; i++)

if (!InDegree[i]) S.Add(i);

// 產生拓撲次序

i = 0; // 數組v 的游標

while (!S.IsEmpty()) {// 從堆棧中選擇

int w; // 下一個頂點

S . D e l e t e ( w ) ;

v[i++] = w;

int u = Begin(w);

while (u) {// 修改入度

I n D e g r e e [ u ] - - ;

if (!InDegree[u]) S.Add(u);

u = NextVe r t e x ( w ) ; }

}

D e a c t i v a t e P o s ( ) ;

delete [] InDegree;

return (i == n);

}

④ 求拓撲排序演算法的詳細講解

3.1AOV網

在現代化管理中，人們常用有向圖來描述和分析一項工程的計劃和實施過程，一個工程常被分為多個小的子工程，這些子工程被稱為活動（Activity)，在有向圖中若以頂點表示活動，有向邊表示活動之間的先後關系，這樣的圖簡稱為AOV網。如下圖是計算機專業課程之間的先後關系：

基礎知識課程應先於其它所有課程，pascal語言課程應先於數據結構。

3. 2 拓撲排序

在AOV網中為了更好地完成工程，必須滿足活動之間先後關系，需要將各活動排一個先後次序即為拓撲排序。如上圖的拓撲排序

基礎知識；Pascal；數據結構；離散數學。或

基礎知識；離散數學Pascal；數據結構。

拓撲排序的方法和步驟：

（1）在圖中選一個沒有前趨的頂點並輸出之

（2）刪除該頂點及由它發出的各邊，直到圖中不存在沒有前趨的頂點為止。

若圖中存在迴路，拓撲排序無法進行。

以下是將一AOV網進行拓撲排序的演算法：

網採用鄰接矩陣A表示,若a[i，j]=1，表示活動i先於j，a[i，j]=0，表示活動i與j不存在先後關系。

（1）計算各頂點的入度

（2）找入度為零的點輸出之，刪除該點，且與該點關聯各點的入度減1

（3）若所有頂點都輸出完畢。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
procere init;
var
i,j:integer;
begin
read(n);
for i:=1 to n do
for j:=1 to n do
begin
read(map[i,j]);
inc(into[j]);
end;
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

3.3應用舉例與練習

例：士兵排隊問題：

有N個士兵（1<=N<=100),編號依次為1,2,...,N.隊列訓練時，指揮官要把士兵從高到矮排成一行，但指揮官只知道「1 比2 高，7 比 5高」這樣的比較結果。

輸入文件：第一行為數N（N〈=100）；表示士兵的個數。以下若干行每行兩個數A，B 表示A高於B。

輸出文件：給出一個合法的排隊序列。

程序如下：

program tppv;
const maxn=100;
var
map:array[1..maxn,1..maxn] of byte;
into:array[1..maxn] of byte;
n,i,j,k:byte;
fp:text;
procere init;
var
i,j:integer;
begin
assign(fp,'tp.txt');
reset(fp);
readln(fp,n);
fillchar(map,sizeof(map),0);
fillchar(into,sizeof(into),0);
while not(seekeof(fp)) do
begin
readln(fp,i,j);
map[i,j]=1 ;
inc(into[j]);
end;
close(fp);
end;
begin
init;
for i:=1 to n do
begin
j:=1;
while (j<=n)and(into[j]<>0) do inc(j);
write(j,' ');
into[j]:=255;
for k:=1 to n do
if map[j,k]=1 then dec(into[k]);
end;
end.

練習：

Z語言問題：Z語言的基本字母也是26個，不妨用a到z表示，但先後順序與英語不同。

現在按Z語言的順序給出了N個單詞，請依照這些單詞給出一個可能的Z語言字母順序。

輸入文件：第一行一個數N（N<=100)表示單詞的個數。

第二行到第N+1行，每行一個單詞。

輸出文件：僅一行，可能的字母順序。

(圖不好粘貼）

⑤ 拓撲排序的流程圖

由AOV網構造拓撲序列的拓撲排序演算法主要是循環執行以下兩步，直到不存在入度為0的頂點為止：選擇一個入度為0的頂點並輸出之；從網中刪除此頂點及所有出邊。

循環結束後，若輸出的頂點數小於網中的頂點數，則輸出「有迴路」信息，否則輸出的頂點序列就是一種拓撲序列。

由AOV網構造出拓撲序列的實際意義是：如果按照拓撲序列中的頂點次序，在開始每一項活動時，能夠保證它的所有前驅活動都已完成，從而使整個工程順序進行，不會出現沖突的情況。

(5)拓撲演算法擴展閱讀

拓撲排序（Topological Sorting）為一個有向無環圖（DAG，Directed Acyclic Graph）的所有頂點的線性序列。且該序列必須滿足下面兩個條件：每個頂點出現且只出現一次。若存在一條從頂點A到頂點B的路徑，那麼在序列中頂點A出現在頂點B的前面。

拓撲排序常用來確定一個依賴關系集中，事物發生的順序。例如，在日常工作中，可能會將項目拆分成A、B、C、D四個子部分來完成，但A依賴於B和D，C依賴於D。為了計算這個項目進行的順序，可對這個關系集進行拓撲排序，得出一個線性的序列，則排在前面的任務就是需要先完成的任務。

⑥ 拓撲排序

我認為答案錯了，這個很簡單的

⑦ 在計算機中拓撲是什麼意思

計算機中拓撲一般指的是：計算機網路的拓撲結構，即是指網上計算機或設備與傳輸媒介形成的結點與線的物理構成模式。網路的結點有兩類：一類是轉換和交換信息的轉接結點，包括結點交換機、集線器和終端控制器等；另一類是訪問結點，包括計算機主機和終端等。線則代表各種傳輸媒介，包括有形的和無形的。主要有以下幾個類型：
①匯流排拓撲結構：是將網路中的所有設備通過相應的硬體介面直接連接到公共匯流排上，結點之間按廣播方式通信，一個結點發出的信息，匯流排上的其它結點均可「收聽」到。 優點：結構簡單、布線容易、可靠性較高，易於擴充，是區域網常採用的拓撲結構。缺點：所有的數據都需經過匯流排傳送，匯流排成為整個網路的瓶頸；出現故障診斷較為困難。最著名的匯流排拓撲結構是乙太網（Ethernet）。
②星型拓撲結構：每個結點都由一條單獨的通信線路與中心結點連結。 優點：結構簡單、容易實現、便於管理，連接點的故障容易監測和排除。缺點：中心結點是全網路的可靠瓶頸，中心結點出現故障會導致網路的癱瘓。
③環形拓撲結構：各結點通過通信線路組成閉合迴路，環中數據只能單向傳輸。 優點：結構簡單、蓉以是線，適合使用光纖，傳輸距離遠，傳輸延遲確定。缺點：環網中的每個結點均成為網路可靠性的瓶頸，任意結點出現故障都會造成網路癱瘓，另外故障診斷也較困難。最著名的環形拓撲結構網路是令牌環網（Token Ring）
④ 樹型拓撲結構：是一種層次結構，結點按層次連結，信息交換主要在上下結點之間進行，相鄰結點或同層結點之間一般不進行數據交換。優點：連結簡單，維護方便，適用於匯集信息的應用要求。缺點：資源共享能力較低，可靠性不高，任何一個工作站或鏈路的故障都會影響整個網路的運行。
⑤網狀拓撲結構：又稱作無規則結構，結點之間的聯結是任意的，沒有規律。優點：系統可靠性高，比較容易擴展，但是結構復雜，每一結點都與多點進行連結，因此必須採用路由演算法和流量控制方法。目前廣域網基本上採用網狀拓撲結構。

⑧ c語言編程 拓撲演算法

i=0
A[1...n]為一個新數組
循環
尋找入度為零的點，將該點放到位置A[i]中
i=i+1
將該點出邊刪除
輸出A

⑨ 一種高效的鏈路層拓撲發現演算法

一、LLDP協議概述

隨著網路技術的發展，接入網路的設備的種類越來越多，配置越來越復雜，來自不同設備廠商的設備也往往會增加自己特有的功能，這就導致在一個網路中往往會有很多具有不同特性的、來自不同廠商的設備，為了方便對這樣的網路進行管理，就需要使得不同廠商的設備能夠在網路中相互發現並交互各自的系統及配置信息。
LLDP（Link Layer Discovery Protocol，鏈路層發現協議）就是用於這個目的的協議。LLDP定義在802.1ab中,它是一個二層協議，它提供了一種標準的鏈路層發現方式。LLDP協議使得接入網路的一台設備可以將其主要的能力，管理地址，設備標識，介面標識等信息發送給接入同一個區域網絡的其它設備。當一個設備從網路中接收到其它設備的這些信息時，它就將這些信息以MIB的形式存儲起來。
這些MIB信息可用於發現設備的物理拓撲結構以及管理配置信息。需要注意的是LLDP僅僅被設計用於進行信息通告，它被用於通告一個設備的信息並可以獲得其它設備的信息，進而得到相關的MIB信息。它不是一個配置、控制協議，無法通過該協議對遠端設備進行配置，它只是提供了關於網路拓撲以及管理配置的信息，這些信息可以被用於管理、配置的目的，如何用取決於信息的使用者。

二、LLDP結構

LLDP的框架結構如圖所示：

3. LLDP工作模式

LLDP可以工作在多種模式下：

由於LLDP可以單獨工作在發送或接收模式下，因此LLDP協議的實現需要支持單獨初始化發送或者接收功能。當工作模式發生變化時，需要根據老的/新的工作模式來關閉/打開發送或者接收的功能。

⑩ 高手解答 全拓撲排序 c語言演算法 或者 演算法思想也行啊

拓撲排序，很多時候，會作為演算法的預處理。
它是針對有向無環圖。
我空間中寫過，比較詳細。
演算法思想：
針對一個有向無環圖，求它的拓撲排序的一個簡單方法：首先找到這個圖中入度為0的頂點。把它放在序列的第一個位置，然後刪除改頂點和它的邊。得到一個新的有向無環圖，在找這個圖中入度為0的頂點。放在序列的下一個位置，然後再刪除改頂點和它的邊。。。，這個步驟重復直到圖中所有的頂點都在序列中。

詳細請看，有程序代碼和相應的圖片說明。
http://hi..com/huifeng00/blog/item/667348af89c42e044b36d6a6.html