拓扑排序2 - webdancer's Blog

拓扑排序2

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

    前一篇,学习了根据DFS,来进行拓扑排序的方法;今天看一下,按照贪婪算法来进行拓扑排序。主要的思想:找没有入度的顶点,放到队列里面;然后,逐渐从队列里删除顶点,加入一个数组,如果产生了新的没有入度的顶点,也加入队列,重复直到队列为空。

 

#include<stdio.h>
#include<stdlib.h>
#include"graph.c"
#include"queue.c"
#define MAX 100

int indeg[MAX];
int vl[MAX];
int *q;
void topolsort(Graph g){
    int i,nv;

    nv=g->nv;
    for(i=0;i<nv;i++){
        struct node * vnode;
        vnode=g->adj[i];
        while(vnode){
            int u;
            u=vnode->v;
            indeg[u]++;
            vnode=vnode->next;
        }
    }
    q=initq(nv);
    
    for(i=0;i<nv;i++)
        if(indeg[i]==0)
            add(q,i);
            
    int iv;
    iv=0;
    while(!isempty()){
        int u;
        u=delete(q);
        vl[iv++]=u;

        struct node * unode;
        unode=g->adj[u];
        while(unode){
            int v;
            v=unode->v;
            if(!(--indeg[v]))
                add(q,v);
            unode=unode->next;
        }
    }
     
}

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

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


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

时间复杂度分析:有向图的表示采用了邻接链表,所以时间复杂度为:Θ(V+E)。 

West Bengal HS Quest 说:
2022年8月23日 20:36

West Bengal HS Guess Paper 2023, WBCHSE 12th HS Model Question Paper 2023, The West Bengal Higher School Education Board WBCHSE, West Bengal HS Question Paper 2023 Kolkata was founded in the year 1951 under a legislative act of the Government of West Bengal to administer the curriculum taught in public schools in the West Bengal state. It will conduct the exams to all the students who are pursuing their classes respectively.


登录 *


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