欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

拓扑序列(拓扑排序)

程序员文章站 2023-12-23 17:15:21
...

摘要

本文主要介绍拓扑序列,和求解拓扑序列的方法。

什么是拓扑序列

拓扑序列是对于有向图而言的,有向图的拓扑序是其顶点的线性排序,使得对于从顶点uu 到顶点vv的每个有向边uvuvuu 在序列中都在vv之前。

例如对于下图:
拓扑序列(拓扑排序)
对于上图, 存在4条边:(1,3)(1,2)(2,4)(2,3)
该图的拓扑序必须要满足以下两点:

  1. 每个顶点只出现一次。
  2. 对于图中的任何一条边,起点必须在终点之前。

拓扑序的求法

首先,不是所有的有向图都是有拓扑序的,只有有向无环图才有拓扑序,所以有向无环图又被称为拓扑图

拓扑序是按照点的先后顺序排列的,也就是说入度为0的点一定是排在前面的,我们直接对一个图BFS一遍,BFS过程中更新每个点的入度,如果一个点的入度为0,那么就将其加入拓扑序,并且删除其与后继结点的所有边。

在读入边的时候,直接计算点的入度。

代码:

import java.io.*;
import java.util.*;

public class Main{
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
	
	static final int N = 100010;
	static int n, m, idx = 1;
	static int e[] = new int[N];
	static int ne[] = new int[N];
	static int h[] = new int[N];
	static int d[] = new int[N];
	static Queue<Integer> q = new LinkedList<>();
	static Queue<Integer> ans = new LinkedList<>();
	public static int Int(String s){return Integer.parseInt(s);}
	
	public static void add(int a, int b){
		e[idx] = b;
		ne[idx] = h[a];
		h[a] = idx++;
	}
	
	public static Boolean bfs(){
		while(!q.isEmpty()){
			int x = q.peek();
			q.poll();
			for(int i = h[x]; i != 0; i = ne[i]){ // 遍历所有后继结点
				if(--d[e[i]] == 0){// 删除当前点与后继结点的边,如果删除后
				                   //其后继结点的入度变为0,就入队
					q.add(e[i]);
					ans.add(e[i]);
				}
			}
		}
		if(ans.size() == n) return true;
		else return false;
	}
	
	public static void main(String[] args) throws IOException{
		String[] s = in.readLine().split(" ");
		n = Int(s[0]);
		m = Int(s[1]);
		
		for(int i = 0; i < m; i++){
			String s1[] = in.readLine().split(" ");
			add(Int(s1[0]), Int(s1[1]));
			
			d[Int(s1[1])] ++; // 入度加一  
		}
		
		int flag = 0;
		for(int i = 1; i <= n; i++){
			if(d[i] == 0){ // 找到入度为0的点
				q.add(i);
				ans.add(i);
				flag = 1;
			}
		}
		
		if(flag == 0)
			out.write("-1\n");
		else
		{
			if(bfs()){ // 输出拓扑序
				while(!ans.isEmpty()){
					out.write(ans.poll()+" ");
				}
			}
			else{ // 不存在拓扑序
			    out.write("-1\n");
			}
		}
		
		out.flush();
	}
}


上一篇:

下一篇: