浅谈图论之拓扑排序

前言：

说起拓扑排序，第一想法就是判断一个图中有没有环。

其次就是它的思想：

1.统计所有顶点的入度。

2.把入度为0的顶点输出，同时所有以此顶点为始点的边被抹去，即此边的终点结点入度-1（队列存储）

3.如果把所有的顶点都输出了，说明此图无环，否则有环。

下面看一下它具体的实现过程：

嗯嗯，看了上面的是不是对拓扑排序有了一定的了解？

接下来，看应用：

首先对于图的结点，如果是integer，congratulation！直接就可以用inDegree[]统计入度了

但如果是String呢？   答案是map转换 HashMap<String,Integer>

其次，对于入度为0的顶点的输出有要求吗？

没有 Queue

有 PriorityQueue（优先队列）

先看一段代码普通Queue

static void topologicalSort(HashMap<String,Integer> map,ArrayList<Integer>edge[],int inDegree[],ArrayList<Integer> list,int count) { Queue<Integer>q=new LinkedList<Integer>(); Iterator<String> iterator=map.keySet().iterator(); while(iterator.hasNext()) { String key=iterator.next(); if(inDegree[map.get(key)]==0)//找到入度为0的点压入队列 q.add(map.get(key)); } while(!q.isEmpty()) { int now=q.poll(); list.add(now);//输出入度为0的点 for(int i=0;i<edge[now].size();i++) //把由此节点发出的所有边消除，即边的终点入度减一 { inDegree[edge[now].get(i)]--; if(inDegree[edge[now].get(i)]==0)//如果上次操作产生了入度为0的顶点，压入队列 q.add(edge[now].get(i)); } } if(list.size()!=count) { System.out.println("Error：存在环！"); return; } System.out.println(); for(int i=0;i<list.size();i++) { if(i==0) System.out.print(intToString(list.get(i),map)); else System.out.print(" "+intToString(list.get(i),map)); } //System.out.println(); }

其次优先队列（这里只给出其之用法，具体拓扑排序的实现，可以参考上面的代码，基本一致，这里不再详写）：

//这里只写一下优先队列的用法，即通过类继承Comparable接口，覆盖CompareTo方法使类可自比 //PriorityQueue<class> pq 就实现了PriorityQueue中元素的排序。默认从小到大 class Person implements Comparable<Person>{ public int age; Person(int age){ this.age=age; } public int compareTo(Person other){ return other.age-age;//从大到小 } } public class Main { public static void main (String[] args) { PriorityQueue<Person> q=new PriorityQueue<Person>(); Person a=new Person(10); Person b=new Person(20); q.offer(a); q.offer(b); System.out.println(q.peek().age); } }

最后呢，贴出一个经典的蓝桥杯拓扑排序题：

问题描述 锦瑟年华谁与度 莫问情归处 只影向斜阳 剑吼西风 欲把春留驻 天涯芳草无归路 回首花无数 解语自销魂 弱袂萦春 尘缘不相误 ...... 在卡勒沃夫充满文学杀伤力的声音中，身处紫荆2号楼202B的四位远近高低各不同的室友纷纷回忆起了各自波澜起伏的过去，并对长在百草园，邻有百花谷的现状表达了各自的见解。 某Q："...我小学就开窍了...她的父母说我很好，但是...今天又和北林的联系了..." 某X："...差点就成了，结果到学校了...这个方法放假了我去对我的同桌用！..." 某W："..."（千言万语不言中，有大量的故事等待考古） 某Z："...为了来清华...咱们审美观不一样，不会抢..." ...... 卡勒沃夫在这个不朽的夜话中搜集出了某人零散的历任女友资料，为了强迫某人将他出的题目的标程交出，现在卡勒沃夫需要一个能将这些零散信息整合起来的程序。伴随着雄壮委婉动人的音乐，身为程序设计快男（超女）的你降临了！卡勒沃夫正对着您做Orz状并请求着："神牛啊~请施舍给我一段程序把~偶米头发~"。。 输入格式 第一行为一个不超过5的整数T，表示数据的组数。之后每组数据的一行为一个不超过100的整数n。之后n行每行有两个用单个空格隔开的字符串（每个字符串只有英文大小写字母，长度不超过10），为两位mm的名字。每行第一个mm先于第二个mm成为某人的女友。 在这里我们假装诅咒某人不会同时被两个或两个以上mm泡，某个mm抛弃了某人后不会再吃回头草，同时卡勒沃夫深邃的洞察力使得他收集到了充足的信息以确定某人女友的先后顺序。 在小数据组中出现的人物不超过13个 输出格式 输出T行，每行对应一组数据，并按照mm们从先到后成为某人女友的顺序输出她们的名字，各个名字间用一个空格隔开。 样例输入 2 2 RY Unknown YSZ RY 3 tomorrow yestoday tomorrow today today yestoday 样例输出 YSZ RY Unknown tomorrow today yestoday

代码如下：

import java.io.*; import java.util.*; /* //example:2 2 RY Unknown YSZ RY 3 tomorrow yestoday tomorrow today today yestoday */ public class Main { static ArrayList<Integer> list=new ArrayList<Integer>();//存放结果 static ArrayList<Integer>edge[]=new ArrayList[105];//存放每个顶点对应的边 static HashMap<String,Integer> map=new HashMap<String,Integer>(); //实现string与整数标号的转换 static int inDegree[]=new int[105];//入度 static void init()//初始化 { list.clear(); map.clear(); for(int i=0;i<105;i++) edge[i] = new ArrayList<Integer>(); Arrays.fill(inDegree, 0); } static String intToString(int i,HashMap<String,Integer> map) //最后将整数标号转化为对应的值 { Iterator<String> iterator=map.keySet().iterator(); while(iterator.hasNext()) { String key=iterator.next(); if(map.get(key)==i) return key; } return null; } //拓扑排序 static void topologicalSort(HashMap<String,Integer> map,ArrayList<Integer>edge[],int inDegree[],ArrayList<Integer> list,int count) { Queue<Integer>q=new LinkedList<Integer>(); Iterator<String> iterator=map.keySet().iterator(); while(iterator.hasNext()) { String key=iterator.next(); if(inDegree[map.get(key)]==0)//找到入度为0的点压入队列 q.add(map.get(key)); } while(!q.isEmpty()) { int now=q.poll(); list.add(now);//输出入度为0的点 for(int i=0;i<edge[now].size();i++) //把由此节点发出的所有边消除，即边的终点入度减一 { inDegree[edge[now].get(i)]--; if(inDegree[edge[now].get(i)]==0)//如果上次操作产生了入度为0的顶点，压入队列 q.add(edge[now].get(i)); } } if(list.size()!=count) { System.out.println("Error：存在环！"); return; } System.out.println(); for(int i=0;i<list.size();i++) { if(i==0) System.out.print(intToString(list.get(i),map)); else System.out.print(" "+intToString(list.get(i),map)); } //System.out.println(); } public static void main(String[] args) throws IOException { BufferedReader bfr=new BufferedReader(new InputStreamReader(System.in)); String str=bfr.readLine(); String s[]=str.split(" "); int n=Integer.parseInt(s[0]); for(int i=0;i<n;i++) { str=bfr.readLine(); s=str.split(" "); int m=Integer.parseInt(s[0]); init(); int count=0; for(int j=0;j<m;j++) { str=bfr.readLine(); s=str.split(" "); String first=s[0]; String second=s[1]; //每个字符串对应一个整数代号 //System.out.println(first+" "+second); if(!map.containsKey(first)) map.put(first, count++); if(!map.containsKey(second)) map.put(second, count++); inDegree[map.get(second)]++;//second 入度加1 edge[map.get(first)].add(map.get(second)); } topologicalSort(map,edge,inDegree,list,count); } } }

emmm,总的来说拓扑排序还是很简单的，它要求的数据结构有：一个入度数组，一个顶点边的集合，其他也没什么大不了的。