拓扑算法

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. 网络拓扑图 如何和优化算法联系起来

遗传学不太懂，拓扑图常应用于网络，编程基于流程图，如果你能把网络拓扑图以流程图的形式表绘制出来的话，你的程序不就出来了吗？