拓撲演算法

1. 拓撲排序的應用

一個復雜的工程通常可以分解成一組小任務的集合，完成這些小任務意味著整個工程的完成。例如，汽車裝配工程可分解為以下任務：將底盤放上裝配線，裝軸，將座位裝在底盤上，上漆，裝剎車，裝門等等。任務之間具有先後關系，例如在裝軸之前必須先將底板放上裝配線。任務的先後順序可用有向圖表示——稱為頂點活動（ 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);

}

2. 簡單拓撲排序演算法c語言

#include <stdio.h>
#include <stdlib.h>
#define TURE 1
#define FALSE 0
//圖相關----------------------
typedef int ArcCell; /*對於無權圖，用1或0表示是否相鄰；對帶權圖，則為權值類型*/
typedef int booleanType; //狀態變數
typedef struct
{
ArcCell **arcs; /*鄰接矩陣*/
int vexnum; /*圖的頂點數和弧數*/
} MGraph; /*（Adjacency Matrix Graph）*/
//-----------------------------

MGraph G; //圖
booleanType *visited; //建立標志數組(全局量）

int GetGraph(MGraph *G); //建立鄰接矩陣
int SearchNoEn(MGraph *G); //尋找沒有入度的結點。如果沒有，返回-1，否則返回其位置
booleanType Iscircle(MGraph *G); //判斷是否有環。有則返回1，無返回0
int main()
{
GetGraph(&G);
if(Iscircle(&G))
{
printf("YES\n");
}
else
{
printf("NO\n");
}
return 0;
}

int GetGraph(MGraph *G) //建立鄰接矩陣
{
int i, j, v;
scanf("%d", &(G->vexnum));
G->arcs = (ArcCell**)malloc(sizeof(ArcCell*) * G->vexnum);
for(i = 0; i < G->vexnum; i++)
{
G->arcs[i] = (ArcCell*)malloc(sizeof(ArcCell) * G->vexnum);
} //建立二維動態數組

for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
scanf("%d", G->arcs[i] + j);
}
} //輸入數據

visited = (booleanType*)malloc(sizeof(booleanType) * G->vexnum); //分配標志數組
for(v = 0; v < G->vexnum; v++) //初始化
{
visited[v] = FALSE;
}
return 0;
}//GetGraph

int SearchNoEn(MGraph *G) //尋找沒有入度的結點。如果沒有，返回-1，否則返回其位置
{
int i, j;
for(i = 0; i < G->vexnum; i++)
{
for(j = 0; j < G->vexnum; j++)
{
if(G->arcs[j][i] == 1)
{
break;
}
if(visited[i] != TURE && j == G->vexnum - 1)
{
return i;
}
}
}
return -1;
}

booleanType Iscircle(MGraph *G) //判斷是否有環。有則返回1，無返回0
{
int i, j;
int count = G->vexnum;
i = SearchNoEn(G);
for(; i != -1; i = SearchNoEn(G))
{
for(j = 0; j < G->vexnum; j++)
{
G->arcs[i][j] = 0;
}
visited[i] = TURE;
count--;
}
if(count != 0)
{
return 1;
}
return 0;
}

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

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行，每行一個單詞。

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

(圖不好粘貼）

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

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

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

5. 什麼是拓撲原理

拓撲學的英文名是Topology，直譯是地誌學，也就是和研究地形、地貌相類似的有關學科。我國早期曾經翻譯成「形勢幾何學」、「連續幾何學」、「一對一的連續變換群下的幾何學」，但是，這幾種譯名都不大好理解，1956年統一的《數學名詞》把它確定為拓撲學，這是按音譯過來的。

拓撲學是幾何學的一個分支，但是這種幾何學又和通常的平面幾何、立體幾何不同。通常的平面幾何或立體幾何研究的對象是點、線、面之間的位置關系以及它們的度量性質。拓撲學對於研究對象的長短、大小、面積、體積等度量性質和數量關系都無關。

舉例來說，在通常的平面幾何里，把平面上的一個圖形搬到另一個圖形上，如果完全重合，那麼這兩個圖形叫做全等形。但是，在拓撲學里所研究的圖形，在運動中無論它的大小或者形狀都發生變化。在拓撲學里沒有不能彎曲的元素，每一個圖形的大小、形狀都可以改變。例如，前面講的歐拉在解決哥尼斯堡七橋問題的時候，他畫的圖形就不考慮它的大小、形狀，僅考慮點和線的個數。這些就是拓撲學思考問題的出發點。

拓撲性質有那些呢？首先我們介紹拓撲等價，這是比較容易理解的一個拓撲性質。

在拓撲學里不討論兩個圖形全等的概念，但是討論拓撲等價的概念。比如，盡管圓和方形、三角形的形狀、大小不同，在拓撲變換下，它們都是等價圖形。左圖的三樣東西就是拓撲等價的，換句話講，就是從拓撲學的角度看，它們是完全一樣的。

在一個球面上任選一些點用不相交的線把它們連接起來，這樣球面就被這些線分成許多塊。在拓撲變換下，點、線、塊的數目仍和原來的數目一樣，這就是拓撲等價。一般地說，對於任意形狀的閉曲面，只要不把曲面撕裂或割破，他的變換就是拓撲變幻，就存在拓撲等價。

應該指出，環面不具有這個性質。比如像左圖那樣，把環面切開，它不至於分成許多塊，只是變成一個彎曲的圓桶形，對於這種情況，我們就說球面不能拓撲的變成環面。所以球面和環面在拓撲學中是不同的曲面。

直線上的點和線的結合關系、順序關系，在拓撲變換下不變，這是拓撲性質。在拓撲學中曲線和曲面的閉合性質也是拓撲性質。

我們通常講的平面、曲面通常有兩個面，就像一張紙有兩個面一樣。但德國數學家莫比烏斯(1790～1868)在1858年發現了莫比烏斯曲面。這種曲面就不能用不同的顏色來塗滿兩個側面。

拓撲變換的不變性、不變數還有很多，這里不在介紹。

拓撲學建立後，由於其它數學學科的發展需要，它也得到了迅速的發展。特別是黎曼創立黎曼幾何以後，他把拓撲學概念作為分析函數論的基礎，更加促進了拓撲學的進展。

二十世紀以來，集合論被引進了拓撲學，為拓撲學開拓了新的面貌。拓撲學的研究就變成了關於任意點集的對應的概念。拓撲學中一些需要精確化描述的問題都可以應用集合來論述。

因為大量自然現象具有連續性，所以拓撲學具有廣泛聯系各種實際事物的可能性。通過拓撲學的研究，可以闡明空間的集合結構，從而掌握空間之間的函數關系。本世紀三十年代以後，數學家對拓撲學的研究更加深入，提出了許多全新的概念。比如，一致性結構概念、抽象距概念和近似空間概念等等。有一門數學分支叫做微分幾何，是用微分工具來研究取線、曲面等在一點附近的彎曲情況，而拓撲學是研究曲面的全局聯系的情況，因此，這兩門學科應該存在某種本質的聯系。1945年，美籍中國數學家陳省身建立了代數拓撲和微分幾何的聯系，並推進了整體幾何學的發展。

拓撲學發展到今天，在理論上已經十分明顯分成了兩個分支。一個分支是偏重於用分析的方法來研究的，叫做點集拓撲學，或者叫做分析拓撲學。另一個分支是偏重於用代數方法來研究的，叫做代數拓撲。現在，這兩個分支又有統一的趨勢。

拓撲學在泛函分析、李群論、微分幾何、微分方程額其他許多數學分支中都有廣泛的應用

6. c語言編程 拓撲演算法

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

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

一、LLDP協議概述

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

二、LLDP結構

LLDP的框架結構如圖所示：

3. LLDP工作模式

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

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

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

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

9. 課程設計 實現拓撲排序演算法

#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
typedef int ElemType;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode
{
int data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VEXTEX_NUM];
typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
typedef struct //構件棧
{
ElemType *base;
ElemType *top;
int stacksize;
}SqStack;
void InitStack(SqStack *); //函數聲明
int Pop(SqStack *, ElemType *);
void Push(SqStack *,ElemType );
int StackEmpty(SqStack *);
void CreatGraph(ALGraph *);
void FindInDegree(ALGraph , int * );
void TopologicalSort(ALGraph );
void InitStack(SqStack *S)//初始化棧
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}
int Pop(SqStack *S,ElemType *e)//出棧操作
{
if(S->top==S->base)
{return ERROR;}
*e=*--S->top;
//printf("%d\n",e);
// return e;
return 0;
}
void Push(SqStack *S,ElemType e)//進棧操作
{if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType));
if(!S->base)
{
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}*S->top++=e;
}
int StackEmpty(SqStack *S)//判斷棧是否為空
{
if(S->top==S->base)
return OK;
else
return ERROR;}
void CreatGraph(ALGraph *G)//構件圖
{int m, n, i;
ArcNode *p;
printf("請輸入頂點數和邊數:");
scanf("%d%d",&G->vexnum,&G->arcnum);
for (i = 1; i <= G->vexnum; i++)
{G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
for (i = 1; i <= G->arcnum; i++) //輸入存在邊的點集合
{
printf("\n請輸入存在邊的兩個頂點的序號:");
scanf("%d%d",&n,&m);
while (n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
{printf("輸入的頂點序號不正確 請重新輸入:");
scanf("%d%d",&n,&m);
}
p = (ArcNode*)malloc(sizeof(ArcNode));
if (p == NULL)
{printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
printf("建立的鄰接表為:\n"); //輸出建立好的鄰接表
for(i = 1; i <= G->vexnum; i++)
{
printf("%d",G->vertices[i].data);
for(p = G->vertices[i].firstarc; p; p = p->nextarc)
printf("%3d",p->adjvex);
printf("\n");
}}
void FindInDegree(ALGraph G, int indegree[])//求入度操作
{
int i;
for (i = 1; i <= G.vexnum; i++)
{
indegree[i] = 0;
}
for (i = 1; i <= G.vexnum; i++)
{while (G.vertices[i].firstarc)
{indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void TopologicalSort(ALGraph G) //進行拓撲排序
{
int indegree[M];
int i, k, n;
int count = 0;
ArcNode *p;
SqStack S;
FindInDegree(G, indegree);
InitStack(&S);
for (i = 1; i <= G.vexnum; i++)
{
printf("第%d個點的入度為%d \n", i, indegree[i]);
}
printf("\n");
for ( i = 1; i <= G.vexnum; i++)
{
if (!indegree[i])
Push(&S,i);
}
printf("進行拓撲排序輸出順序為:"); //輸出結果
while(!StackEmpty(&S))
{
Pop(&S,&n);
printf("%4d",G.vertices[n].data);
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc)
{
k = p->adjvex;
if (!(--indegree[k]))
{
Push(&S,k);
}
}

}printf("\n");

if (count < G.vexnum)
{
printf("出現錯誤\n");
}
else
{
printf("排序成功\n");
}
}
int main(void) //主函數
{
ALGraph G;
CreatGraph(&G);
TopologicalSort(G);
system("pause");
return 0;
}

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

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