新建 文本文档.txt

这个是数据结构几个重要的实验,大家方便的话可以

一个复杂的工程通常可以分解成一组小任务的集合，完成这些小任务意味着整个工程的完成。例如，汽车装配工程可分解为以下任务：将底盘放上装配线，装轴，将座位装在底盘上，上漆，装刹车，装门等等。任务之间具有先后关系，例如在装轴之前必须先将底板放上装配线。任务的先后顺序可用有向图表示——称为顶点活动（ 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 |< q3 , q2 为q1 便是V的一个候选顶点。若q4 不在V中，否则，q3 q3）是有向图的边且q4 使（q4 ≠q1，则必存在q4 是有向图中的一个环路；若q3 则q1 不在V中，若q3="q1" q2）使得q3 是可加入V的候选顶点。同样，必有边（q3 q1 不在V中，否则， q1）且q2 不在V中，有向图中必包含边（ 且没有候选顶点能加入V中，因此至少有一个顶点q1> 

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)。所以，若利用邻接矩阵，

程序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 ) ; } 

} 

// 把入度为０的顶点压入堆栈 

LinkedStack 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); 

} 

7.5.2 拓扑排序   
1.什么叫拓扑排序   
      将AOV网中各个顶点排列成一个有序序列,使得所有前驱和后继关系都能得到满足,尔那些没有次序关的顶点,在拓扑排序的序列中可以插到任意位置.也可说拓扑排序是对非线形结构的有向图进行线形化的重要手段.   
2.拓扑排序的方法   
        由A0V网选取某个没有前驱的顶点,排到序列中,凡取出某顶点,即将它与它相关联的边从图中删掉,随着边的删除,又会有无前驱的顶点,重复如此进行,直到全部顶点都排到序列中去.
   

 
有时候我们会遇到一类问题：  
 
我们需要完成一系列任务，但  
完成A  任务前，需先完成  B,  
完成B  任务前，需先完成  C,D,  
完成E  任务后，才能完成  F,  
完成F  任务前，才能完成  D,G,  
......  
 
怎样确定一个合理合法的完成任务的顺序呢？解决这类问题的算法称为  拓扑排序。  
 
 
一个有向无环图的拓扑排序是一个图中所有顶点组成的序列，并满足如下条件：  
如果图中存在有向边(u,v),则序列中u一定在v之前。  
 
 
算法1：  
1、对有向无环图调用深度优先搜索过程。  
2、每搜索到一个顶点，将其加入栈顶。  
3、返回栈顶指针。  
 
算法完成后，依次取出栈中元素，就是拓扑排序的。  
 
 
算法2：  
 1、选择图G中一个没有直接前趋的顶点v,输出。  
 2、删除v,及从它出发的有向边。    
 3、如G中还有顶点，重复1，2；否则停止。  
 
不错的拓扑排序- -
                                       

void Topsort(Mgraph *g,int in[]){
 int s=-1,i,j,count=0;
 for(i=0;i<Max;i++){
  if(in[i]==0){
   in[i]=s;
   s=i;
  }
 }
  
 while(s!=-1){     
  cout<<"V"<<s<<"->";     
  count++;    
  i=s;     
  s=in[s];     
  for(j=0;j<Max;j++){       
   if(g->arcs[i][j]){         
    in[j]--;         
    if(in[j]==0){           
     in[j]=s;          
     s=j;
    }
   }
  }
 }
 if(count<Max) cout<<"error :"<<endl;
}


#include<stdio.h>
#include<iostream.h>
#define Max 5
typedef struct{
 int arcs[Max][Max];
}Mgraph;
void input(Mgraph *g){
 int i,j;
 cout<<"please input edges i,j:"<<endl;
 for(i=0;i<Max;i++){
  for(j=0;j<Max;j++){
   g->arcs[i][j]=0;
  }
 }
 do{
  cin>>i>>j;
  if(i==-1&&j==-1) break;
  if(i<0||i>=Max||j<0||j>=Max){
   cout<<"please again:"<<endl;
   continue;
  }
  g->arcs[i][j]=1;
 }while(1);
}
void output(Mgraph *g){
 int i,j;
 for(i=0;i<Max;i++){
  for(j=0;j<Max;j++){
   cout<<g->arcs[i][j]<<" ";
  }
  cout<<endl;
 }

}

void cal_in(Mgraph *g,int in[]){
 int i,j;
 for(i=0;i<Max;i++){
  in[i]=0;
 }
 for(i=0;i<Max;i++){
  for(j=0;j<Max;j++){
   if(g->arcs[i][j]) in[j]++;
  }
 }
}


void Topsort(Mgraph *g,int in[]){
 int s=-1,i,j,count=0;
 for(i=0;i<Max;i++){
  if(in[i]==0){
   in[i]=s;
   s=i;
  }
 }
  
 while(s!=-1){     
  cout<<"V"<<s<<"->";     
  count++;    
  i=s;     
  s=in[s];     
  for(j=0;j<Max;j++){       
   if(g->arcs[i][j]){         
    in[j]--;         
    if(in[j]==0){           
     in[j]=s;          
     s=j;
    }
   }
  }
 }
 if(count<Max) cout<<"error :"<<endl;
}

void main(){
 Mgraph g;
 int indegree[Max];
    input(&g);
 output(&g);
 cal_in(&g,indegree);
 cout<<endl;
 Topsort(&g,indegree);
 cout<<endl;

}

用邻接矩阵表示图的拓扑排序算法
hengzhen BY - 2006-6-7 6:31:00
＃i nclude<stdio.h>
＃i nclude<stdlib.h>
#define MAXVEX 100
#define TRUE 1
#define FALSE 0

typedef char VexType;
typedef int AdjType;
typedef struct {
    int n; /* 图的顶点个数 */
    /*VexType vexs[MAXVEX];*/ /* 顶点信息 */
    AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */
} GraphMatrix;

typedef struct {
    /*VexType vexs[MAXVEX];*/ /* 顶点信息 */ 
    int vexsno[MAXVEX]; /* 顶点在顶点表中的下标值 */
} Topo;

/* 求出图中所有顶点的入度 */
/* 方法是搜索整个邻接表 */
void findInDegree(GraphMatrix* g, int *inDegree) {
    int i, j;       
    for (i = 0; i < g->n; i++) {
        inDegree[i] = 0;
        for (j = 0; j < g->n; j++)
            if (g->arcs[j][i]) ++inDegree[i];
    }
}

void makeNewAOV(GraphMatrix* g, int p, int* indegree, int* top) {
    int k;
    for (k = 0; k < g->n; k++)/* 删除以该顶点为起点的边 */
        if (g->arcs[p][k]) {
            indegree[k]--;
            if (indegree[k] == 0) {         /* 将新的入度为零的边入栈 */
                indegree[k] = *top;
                *top = k; 
            }
        }
}

int topoSort(GraphMatrix * paov, Topo * ptopo) {
    int i, j, nodeno = 0, top = -1;
    int indegree[MAXVEX];

    findInDegree(paov, indegree); /* 求出图中所有顶点的入度 */

    for (i = 0; i < paov->n; i++)
        if (indegree[i] == 0) {          /* 将入度为零的顶点入栈 */ 
            indegree[i] = top; top = i;
        }

    while (top != -1) {                           /* 栈不为空 */
        j = top;
        top = indegree[top];               /* 取出当前栈顶元素 */
        /*ptopo->vexs[nodeno] = paov->vexs[j];*/ /* 将该元素输出到拓扑序列中 */
        ptopo->vexsno[nodeno++] = j;
        /* 取该元素边表中的第一个边结点 */
        /* 删除该结点,构造新的AOV网 */
        /* 对indegree数组进行修改 */
        makeNewAOV(paov, j, indegree, &top);
    }
    if (nodeno < paov->n) {        /* AOV网中存在回路 */
        printf("The aov network has a cycle\n");
        return FALSE;
    }
    return TRUE;
}

/* 构造邻接矩阵*/
GraphMatrix* makeMatrix(){
    GraphMatrix* p;
    int i,j;
    p = (GraphMatrix*)malloc(sizeof(GraphMatrix));
    p->n = 9;
    for (i = 0; i < p->n; i++)
        for (j = 0; j < p->n; j++)
            p->arcs[i][j] = 0;
    p->arcs[0][2] = 1;
    p->arcs[0][7] = 1;
    p->arcs[1][2] = 1;
    p->arcs[1][3] = 1;
    p->arcs[1][4] = 1;
    p->arcs[2][3] = 1;
    p->arcs[3][5] = 1;
    p->arcs[3][6] = 1;
    p->arcs[4][5] = 1;
    p->arcs[7][8] = 1;
    p->arcs[8][6] = 1;
    return p;
}

Topo topo;

int main(){
    int i;
    GraphMatrix* p;
    p = makeMatrix();
    if (topoSort(p, &topo) == TRUE)
        for (i = 0; i < p->n; i++)
            printf("%d ", topo.vexsno[i]);
    return 0;
}