`
duoerbasilu
  • 浏览: 1474399 次
文章分类
社区版块
存档分类
最新评论

拓扑排序

 
阅读更多
定义:
拓扑排序,是指将一个有向无环图E(G)中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若<u,v>∈E(G),则u在线性序列中出现在v之前的排列方式.
本质:
对一个有向无环图G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若<u,v> ∈E(G),则u在线性序列中出现在v之前.
通常,满足这种线性次序的序列叫做拓扑序列.

特点(性质):
①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的.
②若图中存在有向环,则不可能使顶点满足拓扑次序.
③一个有向无环图的拓扑序列通常表示某种方案切实可行.

④一个有向无环图可能有多个拓扑序列.

存图时可以用邻接表或者是邻接矩阵来存……

题目 :Legal or Not

//HDU3342 Legal  or Not
#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
#define N 105
using namespace std;
int map[N][N], XX[N];
int main(){
	int n , m , i , j , a , b ;
	while( cin >> n >> m , n ){
		memset( map, 0, sizeof(map) );
		memset( XX , 0, sizeof(XX) );
		for( i=1 ; i<=m ; i++){
			cin >> a >> b ;
			if(map[a][b])
                continue ;
			map[a][b] = 1 ;
			XX[b]++ ;
		}
		int flag = 1 ;
		for( int T=0 ; T<n ; T++)
		{
            for( i = 0 ;i < n ; i++ )
            {
                if( XX[i]==0 )
                {
                    XX[i]--;
                    for(j = 0 ; j < n ; j++ )
                        if(map[i][j])
                            XX[j]-- ;
                    break ;
                }
            }
            if(i>=n){
                flag = 0 ;
                break ;
            }
		}
		if(!flag)    puts("NO");
		else         puts("YES");
	}
	return 0;
}

题目:确定比赛名次

//HDU1285 确定比赛名次
#include <string.h>
#include <iostream>
using namespace std;
int map[502][502], indegree[502], m, n, pur[502];

void topsort(){
	int i , j , k=1;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++) {
			if(indegree[j]==0) {
				indegree[j]--;
				pur[k++] = j;
				for(int x=1; x<=n; x++)
					if(map[j][x])
						indegree[x]--;
				break;
			}
			if(j>n) {
				cout<<"存在环"<<endl;
				return ;
			}
		}
	}
}
int main(){
	int i, j;
	while(cin>>n>>m)	{
		memset(map,0,sizeof(map));
		memset(indegree,0,sizeof(indegree));
		int a, b;
		for(i=1; i<=m; i++){
			cin>>a>>b;
			if(!map[a][b]){
				map[a][b] = 1;
				indegree[b]++;
			}
		}
		topsort();
		for(i=1; i<=n; i++)
			if(i!=n)
				cout<<pur[i]<<" ";
			else
				cout<<pur[i]<<endl;
	}
	return 0 ;
}

题目:Reward

//HDU 2647 Reward
#include<stdio.h>
#include<vector>
#include<string.h>
#include<iostream>
#define N 10005
using namespace std;
vector<int>::iterator it;
int main(){
	int n , m , i , a , b ;
	while( cin >> n >> m){
		int  XX[N] = {0} ;
		vector <int> map[N] ;
		for( i=0 ; i<m ; i++){
			cin >> a >> b;
			map[b].push_back(a);
			XX[a]++ ;
		}
		int T = n , flag = 1 , sum=0 , mon = 888 ;
		while(T){
		    int Temp[N]={0} , k = 0 ;
            for( i = 1 ;i <= n ; i++ ){
                if( XX[i]==0 ){
                    T-- ;
                    XX[i]--;
                    Temp[k++] = i ;
                    sum += mon ;
                    if(T== 0) goto End;
                }
            }
            for( i = 0 ;i < k ; i++ )
                for( it = map[Temp[i]].begin() ; it < map[Temp[i]].end() ; it++ )
                        XX[*it]-- ;
            if(!k){
                flag = 0 ;
                break ;
            }
            mon++ ;
		}
		End:;
		if(!flag)   puts("-1");
		else   printf("%d\n",sum);
	}
	return 0;
}

题目:Sorting It All Out

// POJ1094 + NYOJ349 Sorting It All Out
//#define Judge_Online
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 27
using namespace std;
int ABC[N][N], Union[N] , Copy_Union[N] ,Ans[N];
bool flag1[N];
int n, m, flag ,Count , Count2;
void Set(char a, char b){
    int x = a-'A', y = b-'A';
    if(ABC[x][y]==0)  {
        ABC[x][y] = 1 ;
        Union[y]++ ;
        Count++;
        if(!flag1[x]){
            flag1[x] = 1 ;
            Count2++;
        }
        if(!flag1[y]){
            flag1[y] = 1 ;
            Count2++;
        }
    }
    memset(Ans,0,sizeof(Ans));
    memcpy( Copy_Union, Union, sizeof(Union) );
    int xx=Count2 ,temp = 0, aaa=0 ;
    bool sss[N] = {0} ;
    while(xx){
        int Temp[N]={0}, k=0 ;
        for(int i=0 ; i<n ; i++)
            if(!Copy_Union[i] && flag1[i]){
                Copy_Union[i]--;
                xx--;
                Ans[aaa++] = i ;
                Temp[k++] = i ;
                sss[i]=1;
                if(xx==0)
                    break ;
            }
        if(!k){
            flag = 1;
            return ;
        }
        if(k!= 1 )
            temp = 1 ;
 //       printf("%d %d  %d\n",Count2 ,xx , k) ;
        for(int i=0 ; i<k ; i++)
            for(int j=0 ; j<n ; j++ )
                if(ABC[Temp[i]][j] && !sss[j])
                    Copy_Union[j]--;
    }
    End:;
    if(!temp){
        for(int i=0 ; i<n ; i++)
            if(!sss[i])
                temp = 1 ;
        if(!temp)
            flag = 2;
    }
}
int main(){
    #ifdef Judge_Online
	freopen( "Input.txt" ,"r", stdin );
    #endif
    char a, b, op;
    while( cin >> n >> m ,m+n ){
        memset(ABC,0,sizeof(ABC));
        memset(Union,0,sizeof(Union));
        memset(flag1,0,sizeof(flag1));
        Count = 0;
        Count2 = 0;
        flag = 0;
        for( int i=1 ; i<=m ; i++ ){
            getchar();
            cin >> a >> op >> b;
            if(flag==0)
                Set( a, b);
        }
        if(!flag)
            puts("Sorted sequence cannot be determined.");
        else if(flag==1)
            printf("Inconsistency found after %d relations.\n",Count);
        else{
            printf("Sorted sequence determined after %d relations: ",Count);
            for(int i=0 ; i<n ; i++)
                printf("%c",Ans[i]+'A');
            printf(".\n");
        }
    }
	return 0;
}


终于有点感觉了,Yes!!

分享到:
评论

相关推荐

    数据结构拓扑排序课程设计.docx

    课题二 拓扑排序 2.1 问题的提出2.1 问题的提出 任务:编写函数实现图的拓扑排序。 程序所实现的功能: 建立对应的邻接表,对该图进行拓扑排序,并显示排序结果。 输入: 顶点数, 边数及各顶点信息(数据格式为整形...

    操作系统 拓扑排序算法

    任意给定一个有向图,设计一个算法,对它进行拓扑排序。拓扑排序算法思想:a.在有向图中任选一个没有前趋的顶点输出;b.从图中删除该顶点和所有以它为尾的弧;c.重复上述a、b,直到全部顶点都已输出,此时,顶点输出...

    拓扑排序 整体 拓扑排序

    拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序拓扑排序

    有向图的拓扑排序

    对于有向图进行拓扑排序,图使用邻接矩阵的存储结构。

    c语言实现图的拓扑排序

    C语言实现图的拓扑排序

    c++实现拓扑排序

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...

    简单拓扑排序——源码

    拓扑排序源码,程序简单易懂,注释详细。希望对学习数据结构的朋友有所帮助。

    拓扑排序关键路径算法C语言完整代码

    拓扑排序关键路径算法C语言完整代码,vs2013下编译运行通过

    拓扑排序-课程设计(源码、课程设计说明书)

    题目内容:输出有向网的拓扑排序序列。 拓扑排序的基本思想为: 1)从有向图中选出一个无前驱的顶点输出; 2)将此顶点和以他为起点的弧删除; 3)重复1)2)直到不存在无前驱的顶点; 4)若此时输出的顶点数小于有...

    拓扑排序与关键路径(C++版)

    拓扑排序与关键路径,在日常生活中,一项大的工程可以看作是由若干个子工程(这些子工程称为“活动” )组成的集合,这些子工程(活动)之间必定存在一些先后关系,即某些子工程(活动)必须在其它一些子工程(活动...

    数据结构课设拓扑排序源代码(教学计划安排)

    数据结构课设报告,包括完整源代码,用拓扑排序算法安排有先后制约关系的课程的教学计划。

    AOV网与拓扑排序

    C实现的拓扑排序,有详细注释,有问题的我们一起讨论

    图的最短路径、拓扑排序和关键路径

    图的最短路径、拓扑排序和关键路径相关算法描述,有c++code

    拓扑排序 数据结构 c和 C++源程序代码

    拓扑排序 数据结构 c和 C++源程序代码 拓扑排序 数据结构 c和 C++源程序代码

    基于邻接表存储的图的拓扑排序算法

    基于邻接表存储的图的拓扑排序算法,学习C++和理解数据结构很有帮助

    拓扑排序和关键路径课设

    阅读了《数据结构(C语言)》的经典著作后...本次算法课程设计运用所学的图论的拓扑排序和关键路径,去实现工程中的花费时间和顺利进行问题。拓扑排序主要用于检验工程能否施工,关键路径主要用于看出工程施工时间消耗。

    C# 图 拓扑排序

    C# 图 拓扑排序

    图(拓扑排序)

    【拓扑排序】 任务:编写函数实现图的拓扑排序。 ........................................................................................................................

    图 拓扑排序 深度搜索 广度搜索 最小生成树

    图 拓扑排序 深度搜索 广度搜索 最小生成树

    拓扑排序--课程表

    对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑...

Global site tag (gtag.js) - Google Analytics