拓扑排序（（算法竞赛入门经典）刘汝佳）-白红宇

拓扑排序（（算法竞赛入门经典）刘汝佳）

阅读量：5917 次

发布时间：2019-06-19

本文共 6795 字，大约阅读时间需要 22 分钟。

转载请注明出处：

viewmode=contents

【分析】（小白）

把每一个变量看成一个点，“小于”关系看成有向边，则我们得到了一个有向图。这样，我们的任务实际上是把一个图的全部结点排序，使得每一条有向边（u,v）相应的u都排在v的前面。在图论中，这个问题称为拓扑排序。

不难发现：假设图中存在有向环，则不存在拓扑排序，反之则存在。我们把不包括有向环的有向图称为有向无环图。能够借助dfs函数完毕拓扑排序：在訪问完一个结点之后把它加到当前拓扑排序的首部。

一、输出随意一种满足优先条件的就可以：

代码例如以下：

#include 
     
      #include 
      
       #define MAXN 517int G[MAXN][MAXN];int c[MAXN],topo[MAXN];int t;int n, m;bool dfs(int u){	c[u] = -1;	for(int v = 1; v <= n; v++)	{		if(G[u][v])		{			if(c[v] < 0)				return false;			else if(!c[v] && !dfs(v))				return false;		}	}	c[u] = 1;	topo[--t] = u;	return true;}bool toposort(){	t = n;	memset(c,0,sizeof(c));	for(int u = 1; u <= n; u++)	{		if(!c[u])		{			if(!dfs(u))				return false;		}	}	return true;}int main(){	int a, b;	int i;	while(~scanf("%d%d",&n,&m))	{		for(i = 0; i < m; i++)		{			scanf("%d%d",&a,&b);			G[a][b] = 1;		}		if(toposort())		{			bool ok = true;			for(i = 0; i < n; i++)			{				if(ok)				{					printf("%d",topo[i]);					ok = false;				}				else					printf(" %d",topo[i]);			}		}		printf("\n");	}	return 0;}

这里用到了一个c数组,c[u]=0表示从来没有訪问过（从来没有调用过dfs（u））；c[u]=1表示已经訪问过。而且还递归訪问过它的全部子孙（即dfs（u）曾被调用过。并已返回）。c[u]=-1表示正在訪问（即递归调用dfs（u）正在栈帧中，尚未返回）。

二、输出满足条件且要求输出时字典序小的在前：

此时须要用到优先队列；

拓扑排序

首先统计每一个结点的入度。将度为0的结点编号放入

队列（此题放入优先队列中）中。

然后进行循环：

取出队头结点，视作边的起点。

然后“删除与该点相连的边”，代码就是将这个图中的该边还有一个结点（即终点）的入度减一。

假设减一以后，终点的入度变为了0，那么将终点的编号入队列。

推断队列是否为空。若不空，则回到1

优先队列

C++ STL中有优先队列的类——priority_queue<T>。默认优先队列是值越大，优先级越高。所以比方priority_queue<int> q。

这里面的元素是降序排列的。

假设我们要实现升序须要重载。

priority_queue
     
      
       ,greater
       
         > q;

代码例如以下：（HDU1285）

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;bool map[517][517];int in[517];priority_queue
         
          
           ,greater
           
             > q;void toposort(int n){ for(int i=1;i<=n;i++) { if(in[i]==0)//入度为0的放入队列中 q.push(i); } int c=1; while(!q.empty()) { int v=q.top(); q.pop(); if(c!=n) { cout<
            
             <<" "; c++; } else cout<
             
              <
              
               >n>>m) { int k=0; memset(map,0,sizeof map); memset(in,0,sizeof in); while(m--) { cin>>i>>j; if(map[i][j])//去重 continue; map[i][j]=1; in[j]++; } toposort(n); }}

三、直接每次先输出入度为零的点（HDU1285）：

和二是一样的思路，仅仅是没有使用优先队列。而是使用了数组；

代码例如以下：

#include 
     
      #include 
      
       #define MAXN 517int G[MAXN][MAXN];//路径int in_degree[MAXN];//入度int ans[MAXN];int n, m, x, y;int i, j;void toposort(){	for(i = 1; i <= n; i++)	{		for(j = 1; j <= n; j++)		{			if(G[i][j])			{				in_degree[j]++;			}		}	}	for(i = 1; i <= n; i++)//从最小的開始寻找，	{//这样保证了有多个答案时序号小的先输出		int k = 1;		while(in_degree[k] != 0)//寻找入度为零的点			k++;		ans[i] = k;		in_degree[k] = -1;		//更新为-1，后边检測不受影响，相当于删除节点		for(int j = 1; j <= n; j++)		{			if(G[k][j])				in_degree[j]--;//相关联的入度减1		}	}}void init(){	memset(in_degree,0,sizeof(in_degree));	memset(ans,0,sizeof(ans));	memset(G,0,sizeof(G));}int main(){	while(~scanf("%d%d",&n,&m))	{		init();		for(i = 0; i < m; i++)		{			scanf("%d%d",&x,&y);			G[x][y] = 1;		}		toposort();		for(i = 1; i < n; i++)			printf("%d ",ans[i]);		printf("%d\n",ans[n]);	}	return 0;}

以上解说的都是二维的用的是邻接矩阵存图，仅仅适用于稠密图，数据过大就不能存了。

以下是用邻接表存图的拓扑排序，适用于大数据。稀疏图！

一、数组式邻接表：

代码例如以下：

#include 
     
      using namespace std;int ind[517];       // indegree入度个数int adj[250017];    //adjacency list邻接表位置值int adj_next[250017];//邻接表下一指针int tail[517];      //邻接表尾int main(){    int n,m,i,j,a,b;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(i = 0; i <= n; i++) 		{             tail[i] = -1;            adj[i] = -1;            adj_next[i] = -1;            ind[i] = 0;        }        for(i = 0; i < m; ++i)        {            scanf("%d%d",&a,&b);            int x = tail[a],flag = 0;            while(x != -1)  //推断是否重边            {                if(adj[x] == b)				{                    flag = 1;                    break;                }                x = adj_next[x];            }            if(!flag)//关联a的邻接表            {                adj[i] = b;                adj_next[i] = tail[a];                tail[a] = i;                ind[b] ++;            }        }        for(i = 1;i <= n; i++)//找n次        {            for(j = 1;j <= n;j++)//遍历            {                if(ind[j] == 0)//当入度为0时。说明靠前				{					ind[j] = -1;//在下次寻找入度为0时跳过                    if(i == 1)  						printf("%d",j);                    else       						printf(" %d",j);                    for(int k = tail[j]; k != -1; k = adj_next[k])//邻接位置入度减一                    {                        ind[adj[k]]--;                    }                    break;                }            }        }        printf("\n");    }    return 0;}

二、结构体（链表）式邻接表：

代码例如以下：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define maxn 505struct node{ int num; node *next;};node map[maxn];int d[maxn], n;void Insert(int a, int b);void Free();void Topsort();int main(){ int m; while(cin >> n >> m) { int i, a, b; memset(d, 0, sizeof(d)); for(i=0; i
            
             > a >> b; Insert(a, b); d[b]++; } Topsort(); Free(); } return 0;}void Insert(int a, int b){ node *newnode; newnode = (node *)malloc(sizeof(node)); newnode->num = b; newnode->next = map[a].next; map[a].next = newnode;}void Free(){ node *cur, *old; for(int i=1; i<=n; i++) { cur = map[i].next; while(cur) { old = cur; cur = cur->next; free(old); } map[i].next = NULL; }}void Topsort(){ priority_queue

, greater

> que; int nx, i; int q[maxn]={0}, k=0; node *cur; for(i=1; i<=n; i++) { if(d[i] == 0) que.push(i); } while(que.size()) { nx = que.top(), que.pop(); q[k++] = nx; cur = map[nx].next; while(cur) { nx = cur->num; d[nx] -= 1; if(d[nx] == 0) que.push(nx); cur = cur->next; } } cout << q[0]; for(i=1; i

还有一种（较特殊）：

逆排序+优先队列；（HDU4587）：

也就是HDU第一次BC的第一题！

要使小的序号尽量靠前。小的序号尽量靠前并非代表字典序。要求多种情况时，先使1靠前（可能1仅仅能在第2或第3位那么就要使它在第2位），其次2。3。。而不是在当前情况下，该位最小是哪个就输出哪个；

代码例如以下：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           using namespace std;#define N 30017int n, m;int i, j, k;int v[N],ans[N];vector
           
            P[N];void init(){ memset(ans,0,sizeof(ans)); memset(v,0,sizeof(v));}void Topsort(){ priority_queue
            
             Q; int size, t; for(i = 1; i <= n; i++) { if(v[i] == 0) Q.push(i); } while(!Q.empty()) { t = Q.top(); Q.pop(); size = P[t].size(); for(i = 0; i < size; i++)//相关联的入度减1 { v[P[t][i]]--; if(v[P[t][i]] == 0) Q.push(P[t][i]); } ans[k++] = t; }}int main(){ int T; int a, b; scanf("%d",&T); while(T--) { init(); scanf("%d%d",&n,&m); for(i = 1; i <= n; i++)//清空 { P[i].clear(); } for(i = 0; i < m; i++) { scanf("%d%d",&a,&b); v[a]++; P[b].push_back(a);//逆向建图，在b后面加入a } k = 0; Topsort(); for(i = n-1; i > 0; i--)//逆向输出 { printf("%d ",ans[i]); } printf("%d\n",ans[0]); } return 0;}

你可能感兴趣的文章