拓撲演算法題
⑴ 求拓撲排序演算法的詳細講解
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行，每行一個單詞。
輸出文件：僅一行，可能的字母順序。
(圖不好粘貼）
⑵ 拓撲排序 編程
*/
#include <stdio.h>
#include <malloc.h>
// 輸出有向圖的一個拓撲序列。實現演算法7.12的程序
// 圖的鄰接表存儲表示
#define MAX_NAME 3 // 頂點字元串的最大長度+1
#define MAX_VERTEX_NUM 20
typedef int InfoType; // 存放網的權值
typedef char VertexType[MAX_NAME]; // 字元串類型
typedef enum{DG,DN,AG,AN}GraphKind; // {有向圖,有向網,無向圖,無向網}
typedef struct ArcNode
{
int adjvex; // 該弧所指向的頂點的位置
struct ArcNode *nextarc; // 指向下一條弧的指針
InfoType *info; // 網的權值指針）
}ArcNode; // 表結點
typedef struct VNode
{
VertexType data; // 頂點信息
ArcNode *firstarc; // 第一個表結點的地址,指向第一條依附該頂點的弧的指針
}VNode,AdjList[MAX_VERTEX_NUM];// 頭結點
typedef struct
{
AdjList vertices;
int vexnum,arcnum; // 圖的當前頂點數和弧數
int kind; // 圖的種類標志
}ALGraph;
// 若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// 採用鄰接表存儲結構,構造沒有相關信息的圖G(用一個函數構造4種圖)。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w; // 權值
VertexType va,vb;
ArcNode *p;
printf("請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): ");
scanf("%d",&(*G).kind);
printf("請輸入圖的頂點數和邊數:（空格）\n");
scanf("%d%d", &(*G).vexnum, &(*G).arcnum);
printf("請輸入%d個頂點的值(<%d個字元):\n",(*G).vexnum,MAX_NAME);
for(i = 0; i < (*G).vexnum; ++i) // 構造頂點向量
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) // 網
printf("請順序輸入每條弧(邊)的權值、弧尾和弧頭(以空格作為間隔):\n");
else // 圖
printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");
for(k = 0;k < (*G).arcnum; ++k) // 構造表結點鏈表
{
if((*G).kind==1||(*G).kind==3) // 網
scanf("%d%s%s",&w,va,vb);
else // 圖
scanf("%s%s",va,vb);
i = LocateVex(*G,va); // 弧尾
j = LocateVex(*G,vb); // 弧頭
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) // 網
{
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 圖
p->nextarc = (*G).vertices[i].firstarc; // 插在表頭
(*G).vertices[i].firstarc = p;
if((*G).kind >= 2) // 無向圖或網,產生第二個表結點
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
if((*G).kind == 3) // 無向網
{
p->info = (int*)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; // 無向圖
p->nextarc = (*G).vertices[j].firstarc; // 插在表頭
(*G).vertices[j].firstarc = p;
}
}
return 1;
}
// 輸出圖的鄰接表G。
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("有向圖\n");
break;
case DN: printf("有向網\n");
break;
case AG: printf("無向圖\n");
break;
case AN: printf("無向網\n");
}
printf("%d個頂點：\n",G.vexnum);
for(i = 0; i < G.vexnum; ++i)
printf("%s ",G.vertices[i].data);
printf("\n%d條弧(邊):\n", G.arcnum);
for(i = 0; i < G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while(p)
{
if(G.kind <= 1) // 有向
{
printf("%s→%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == DN) // 網
printf(":%d ", *(p->info));
}
else // 無向(避免輸出兩次)
{
if(i < p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == AN) // 網
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("\n");
}
}
// 求頂點的入度，演算法7.12、7.13調用
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; // 賦初值
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; // 棧類型
#define STACK_INIT_SIZE 10 // 存儲空間初始分配量
#define STACKINCREMENT 2 // 存儲空間分配增量
// 棧的順序存儲表示 P46
typedef struct SqStack
{
SElemType *base; // 在棧構造之前和銷毀之後，base的值為NULL
SElemType *top; // 棧頂指針
int stacksize; // 當前已分配的存儲空間，以元素為單位
}SqStack; // 順序棧
// 構造一個空棧S。
int InitStack(SqStack *S)
{
// 為棧底分配一個指定大小的存儲空間
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲分配失敗
(*S).top = (*S).base; // 棧底與棧頂相同表示一個空棧
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}
// 若棧S為空棧（棧頂與棧底相同的），則返回1，否則返回0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}
// 插入元素e為新的棧頂元素。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base >= (*S).stacksize) // 棧滿，追加存儲空間
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); // 存儲分配失敗
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// 這個等式的++ * 優先順序相同，但是它們的運算方式，是自右向左
return 1;
}
// 若棧不空，則刪除S的棧頂元素，用e返回其值，並返回1；否則返回0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// 這個等式的++ * 優先順序相同，但是它們的運算方式，是自右向左
return 1;
}
// 演算法7.12 P182
// 有向圖G採用鄰接表存儲結構。若G無迴路,則輸出G的頂點的一個拓撲序
// 列並返回1, 否則返回0。
int TopologicalSort(ALGraph G)
{
int i,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree); // 對各頂點求入度indegree[0..vernum-1]
InitStack(&S); // 初始化棧
for(i=0;i<G.vexnum;++i) // 建零入度頂點棧S
if(!indegree[i])
Push(&S,i); // 入度為0者進棧
count=0; // 對輸出頂點計數
while(!StackEmpty(S))
{
// 棧不空
Pop(&S,&i);
printf("%s ",G.vertices[i].data); // 輸出i號頂點並計數
++count;
for(p=G.vertices[i].firstarc;p;p=p->nextarc)
{
// 對i號頂點的每個鄰接點的入度減1
k=p->adjvex;
if(!(--indegree[k])) // 若入度減為0,則入棧
Push(&S,k);
}
}
if(count<G.vexnum)
{
printf("此有向圖有迴路\n");
return 0;
}
else
{
printf("為一個拓撲序列。\n");
return 1;
}
}
int main()
{
ALGraph f;
printf("請選擇有向圖\n");
CreateGraph(&f);
Display(f);
TopologicalSort(f);
system("pause");
return 0;
}
/*
輸出效果：
請選擇有向圖
請輸入圖的類型(有向圖:0,有向網:1,無向圖:2,無向網:3): 0
請輸入圖的頂點數和邊數:（空格）
4 4
請輸入4個頂點的值(<3個字元):
a
b
c
d
請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):
a b
a c
b d
c d
有向圖
4個頂點：
a b c d
4條弧(邊):
a→c a→b
b→d
c→d
a b c d 為一個拓撲序列。
請按任意鍵繼續. . .
*/
⑶ 2.網路的拓撲圖如圖所示,使用距離矢量路由演算法。路由器e收到的矢量如下:來自
你畫的圖上不是菱形,你後面又說是菱形,還有你這里BDE的矢量裡面那麼多數字代表什麼意思啊?不太明白埋棚你的意思.不過距離適量的工作方式就是每個人都通告自己本畢耐地和手液春學到的路由,然後其他人就選距離最小的度量,也就是基於傳聞的路由協議.