拓扑算法

① 程序、算法与拓扑结构之间的关系

你说的拓扑结构应该是数据结构吧

那么程序=算法+数据结构

② 网络拓扑图 如何和优化算法联系起来

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

③ 拓扑排序的应用

一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ 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