拓扑排序 JAVA 爱被打了一巴掌 2021-11-09 23:30 254阅读 0赞 ### **判断是否成环 JAVA 代码实现** ### import java.util.LinkedList; import java.util.Scanner; public class Hello{ static int[][]mp; static int[] indegree; static int N, M; static LinkedList<Integer> list = new LinkedList<Integer>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); M = sc.nextInt(); mp = new int[N][N]; indegree = new int[N]; for(int i = 0; i < N; i ++) { indegree[i] = 0; for(int j = 0; j < N; j ++) { mp[i][j] = 0; } } int x, y; for(int i = 0; i < M; i ++) { x = sc.nextInt(); y = sc.nextInt(); if(mp[x][y] == 0) { mp[x][y] = 1; indegree[y] ++; } } topSort(); } private static void topSort() { int cnt = 0; for(int i = 0; i < N; i ++) { if(indegree[i] == 0) { list.addFirst(i); indegree[i] = -1; } } while(!list.isEmpty()) { int p = list.removeFirst(); System.out.print(p + " "); cnt ++; for(int j = 0; j < N; j ++) { if(mp[p][j] == 1) { mp[p][j] = 0; indegree[j] --; if(indegree[j] == 0) { list.addFirst(j); indegree[j] = -1; } } } } System.out.println(); if(cnt < N) System.out.println("Cycleeeeee!"); else System.out.println("Nooooooooo!"); } } **但是上述是建立邻接矩阵的写法 当 N 太大的时候就不是很好了 所以可以用链表来存边和边的关系 会节省内存 所以以下是链表存图并判断拓扑关系** import java.util.concurrent.ArrayBlockingQueue; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Hello{ static int N, M; static int[] v; static int[] nx; static int[] h; static int[] ans; static int[] in; static int cnt, sz; static LinkedList<Integer> list = new LinkedList<Integer>(); public static void main(String[] args) { Scanner sc = new Scanner(System.in); v = new int[100010]; nx = new int[100010]; h = new int[100010]; in = new int[100010]; N = sc.nextInt(); M = sc.nextInt(); init(); for(int i = 0; i < M; i ++) { int x, y; x = sc.nextInt(); y = sc.nextInt(); add(x, y); } topSort(); } public static void init() { for(int i = 0; i < 100010; i ++) { h[i] = -1; in[i] = 0; } sz = 0; } public static void add(int a, int b) { v[sz] = b; nx[sz] = h[a]; h[a] = sz; in[b] ++; sz ++; } public static void topSort() { for(int i = 0; i < N; i ++) { if(in[i] == 0) list.addFirst(i); } while(!list.isEmpty()) { int tp = list.removeFirst(); System.out.print(tp + " "); cnt ++; for(int i = h[tp]; i != -1; i = nx[i]) { in[v[i]] --; if(in[v[i]] == 0) list.addFirst(v[i]); } } System.out.println(); if(cnt != N) System.out.println("Circleeeeeeeeee"); else System.out.println("Noooooooooo"); } } ** ** 转载于:https://www.cnblogs.com/zlrrrr/p/11097113.html
相关 拓扑排序(Java实现) 仿照前面那个c++写的,具体思路请看上一个博客,只是用Java实现了一下 class Node\{ public int adjvex; public 阳光穿透心脏的1/2处/ 2022年06月17日 06:25/ 0 赞/ 178 阅读
相关 拓扑排序 在这里我们引入AOV(Activity-On-Vertex)网,图的顶点代表活动,其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。 对于一个工程,我们首先将这 野性酷女/ 2022年06月10日 13:28/ 0 赞/ 202 阅读
相关 拓扑排序 C++版本实现 /以邻接矩阵Edge[A][B]=N存放图信息:A指向B,权值为N/ /假设不相连的边的Edge==INT_MAX/ void 淡淡的烟草味﹌/ 2022年06月09日 05:58/ 0 赞/ 334 阅读
相关 拓扑排序 什么是拓扑排序? 在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序 冷不防/ 2022年06月09日 05:57/ 0 赞/ 191 阅读
相关 拓扑排序 拓 扑 排 序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就 小鱼儿/ 2022年04月10日 08:23/ 0 赞/ 216 阅读
相关 拓扑排序 拓扑排序: 拓扑排序是根据离散数学中有关偏序与全序定义的。 ![0_1314168765l7fq.gif][] 若一个集合 X 上的关系 R 是自反的 反 淩亂°似流年/ 2021年12月23日 02:43/ 0 赞/ 301 阅读
相关 拓扑排序 JAVA 判断是否成环 JAVA 代码实现 import java.util.LinkedList; import java.util.Scanner; 爱被打了一巴掌/ 2021年11月09日 23:30/ 0 赞/ 255 阅读
相关 拓扑排序 一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程 野性酷女/ 2021年09月19日 05:04/ 0 赞/ 406 阅读
相关 拓扑排序 作用:判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst 喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 483 阅读
还没有评论,来说两句吧...