拓扑排序 - webdancer's Blog

拓扑排序

webdancer posted @ 2011年3月21日 17:48 in 算法 with tags 算法 排序 , 1774 阅读

   对一个DAG进行拓扑排序,结果为一个所有顶点构成的线性序列。序列满足:

         对于<u,v>∈E(G),在序列中U出现在V的前面。

在算法导论中,给出的算法是:对DAG进行DFS遍历,计算每个顶点结束的时间,然后每完成一个顶点,将其加入到链表的头部。结果就是链表中的序列。

   因此,对前面的DFS实现,稍加修改就可以了。此外,注意需要对原来的无向图实现修改。

代码:

 

#include<stdio.h>
#include"search.c"
extern int f[MAXV];
int * vq;
void reverse(int * a,int n){
    int i,j;
    for(i=1,j=n-1;i<j;i++,j--){
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
}
void dfsv1(Graph g,int u){
    color[u]=GRAY;
    time++;
    d[u]=time;
    struct node * vnode;
    vnode=g->adj[u];
    while(vnode){
        int vv;
        vv=vnode->v;
        if(color[vv]==WHITE){
            p[vv]=u;
            dfsv1(g,vv);
        }
        vnode=vnode->next;
    }
    color[u]=BLACK;
    time++;
    f[u]=time;
    add(vq,u);
    //printf("%d  ",u);
}
void topolsort(Graph g){
    int i,v;
    
    v=g->nv;
    for(i=0;i<v;i++){
        color[i]=WHITE;
        p[i]=-1;
    }
    vq=initq(NUM);
    time=0;
    for(i=0;i<v;i++)
        if(color[i]==WHITE){
            dfsv1(g,i);
        }
    reverse(vq,v+1);    
}

int main(){
    Graph  g;
    int n=5;
    g=init(n);

    edge e[7];
    e[0].u=0;e[0].v=1;
    e[1].u=0;e[1].v=3;
    e[2].u=1;e[2].v=2;
    e[3].u=1;e[3].v=3;
    e[4].u=1;e[4].v=4;
    e[5].u=4;e[5].v=2;
    e[6].u=3;e[6].v=4;

    int i;
    for(i=0;i<7;i++)
        insert(g,e[i]);
    topolsort(g);
    for(i=1;i<=g->nv;i++)
        printf("%d ",vq[i]);
    printf("\n");
    return 0;
}


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee