webdancer's Blog

拓扑排序2

    前一篇,学习了根据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)。 

拓扑排序

   对一个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;
}

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

    题目:找印。

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

 

#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。

shell排序算法

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

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

shell算法:

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

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

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

 

/*为了编程方便,增量序列采用:
[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;
			}
		}
	}
}	

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




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