华为开发者空间
拓扑序列（拓扑排序） 拓扑序列（拓扑排序）
文章目录摘要什么是拓扑序列拓扑序的求法摘要本文主要介绍拓扑排序，和求解拓扑排序的方法。什么是拓扑序列拓扑序列是对于有向图而言的，有向图的拓扑序是其顶点的线性排序，使得对于从顶点uuu 到顶点vvv的每个有向边uvuvuv， uuu 在排序中都在vvv之前。例如对于下图：对于上图， 存在4条边：（1,3）（1,2）（2,4）（2,3）该图的拓扑序必须要满足以下两点：每个顶点只出现...
Androids_lost_Sheep
74071人浏览 · 2020-03-31 21:07:31
Androids_lost_Sheep · 2020-03-31 21:07:31 发布
文章目录
摘要
什么是拓扑序列
拓扑序的求法
摘要
本文主要介绍拓扑序列，和求解拓扑序列的方法。
什么是拓扑序列
拓扑序列是对于有向图而言的，有向图的拓扑序是其顶点的线性排序，使得对于从顶点 u u u 到顶点 v v v的每个有向边 u v uv uv， u u u 在序列中都在 v v v之前。
例如对于下图：
对于上图， 存在4条边：（1,3）（1,2）（2,4）（2,3）
该图的拓扑序必须要满足以下两点：
每个顶点只出现一次。
对于图中的任何一条边，起点必须在终点之前。
拓扑序的求法
首先，不是所有的有向图都是有拓扑序的，只有有向无环图才有拓扑序，所以有向无环图又被称为拓扑图。
拓扑序是按照点的先后顺序排列的，也就是说入度为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
static Queue
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();
}
}
# 图论
# java
华为开发者空间 华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。
加入社区
更多推荐
·
交通银行基于HarmonyOS数字盾服务，实现大额转账安全
·
基于华为开发者空间，远程直连云开发环境部署指导手册
·
以图治链：GES在链路治理方面的应用
交通银行基于HarmonyOS数字盾服务，实现大额转账安全
在近日落幕的华为开发者大会2025（6月20日-6月22日）上，交通银行作为HarmonyOS安全合作的关键伙伴受邀出席。在大会的主题演讲上介绍了交通银行基于HarmonyOS SDK设备安全服务（Device Security Kit）中的数字盾服务，成功打造了安全盾，实现大额转账场景安全的合作成果。
华为开发者空间 基于华为开发者空间，远程直连云开发环境部署指导手册
华为开发者空间 以图治链：GES在链路治理方面的应用
华为开发者空间 7.4w 56 0 0 扫一扫分享内容
点击复制链接 分享 所有评论(0)
您需要登录才能发言
查看更多评论 欢迎加入社区
取消 确定