webdancer's Blog

拓扑排序2

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

 

?
拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#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)。 

算法 算法 排序 Comments(1) 2011年3月23日 21:48

拓扑排序

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

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

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

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

代码：

 

?
拓扑排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;
}

算法 算法 排序 Comments(0) 2011年3月21日 17:48

找出数组中重复次数最多的元素并打印

    题目：找出数组中重复次数最多的元素并打印。

这道题其实在做汇编实验时，已经做过了。但是当时的思路还是太简单，现在又想了一下，可以先排序，然后遍历。这样如果采用快排，时间复杂度应为：O(nlogn+n)。代码:

 

?
找出数组重复元素最多的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<stdio.h>
#include<stdlib.h>
 
int int_compare(const void * x1,const void * x2){
    int * a=(int *)x1;
    int * b=(int *)x2;
    return (*a-*b);
}
 
void findremax(int a[],int n,int *m,int *c){
    int index,count,maxc,i;
 
    index=0;
    count=1;
    maxc=count;
    //printf("%d\n",(sizeof a )/(sizeof a[0])); Error
    for(i=1;i<n;i++){
        if(a[i]==a[i-1])
            count++;
        else{
            if(count>maxc){
                maxc=count;
                index=i-1;
            }
            count=1;
        }
    }
    if(count>maxc){
        maxc=count;
        index=i-1;
    }
 
    *m=index;
    *c=maxc;
     
}
 
int main(){
    int maxindex,c;
    int a[]={1,1,2,2,3,3,3,3,4,5,6,7,7,7,7,7,7};
    int n=(sizeof a)/(sizeof a[0]);
    maxindex=0;
    c=0;
    qsort(a,n,sizeof(a[0]),int_compare);
    findremax(a,n,&maxindex,&c);
    printf("%d appears %d times.\n",a[maxindex],c);
 
    return 0;
}

总结：1.排序的应用，排序可以用来对相同的元素分类，使他们相邻，从而解决问题。

         2.语言问题：在代码中注释掉的：//printf("%d\n",(sizeof a )/(sizeof a[0])); Error。没有注意到：在函数中，a是个指针，而不是数组，分了错误，所以：在32位的机器上：(sizeof a )/(sizeof a[0])=1。

算法 算法 排序 Comments(2) 2011年3月19日 19:02

shell排序算法

shell排序算法是一种插入排序算法，直接的插入算法很简单，shell算法不同于直接插入的插入时小步挪动，而做长距离的跳动。它由Donald Shell于1959年提出。

shell算法也叫作“减少增量的排序算法”，每一遍通过增量h,使得那些相距h的记录排序。增量的序列不是固定的，确定最好的增量序列需要大量的数学知识。

shell算法：

<1>确定增量序列S[ t]。

<2>对给出的记录，按照增量序列S，进行t遍排序。

<3>对每遍进行直接插入。

 

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*为了编程方便，增量序列采用：
[n/2,n/4,......,1].实际的增量序列很是有趣。
*/
void shsort(int a[],int n){
    int i,j;
    for(i=n/2;i>=1;i/=2){
        for(j=i;j<n;j++){
            int k;
            for(k=j-i;k>=0&&a[k]>a[k+i];k-=i){
                int t=a[k];
                a[k]=a[k+i];
                a[k+i]=t;
            }
        }
    }
}  

我觉得还是挺有趣的，注意算法在利用直接插入时的方法，后面的元素不断的插入。

算法 算法 排序 Comments(0) 2010年9月22日 03:40




Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee