怎样用wordpress搭建网站,wordpress的XML-RPC,泰州网站建设团队,广州网站建设q479185700棒拓扑排序-117. 软件构建
思路#xff1a;拓扑排序是经典的图论问题。给出一个有向图#xff0c;把有向图转成线性的排序就叫拓扑排序#xff0c;拓扑排序也要检测有向图是否有环#xff0c;即存在循环依赖的情况#xff0c;因为这种情况是不能做线性排序的#xff0c;所…拓扑排序-117. 软件构建
思路拓扑排序是经典的图论问题。给出一个有向图把有向图转成线性的排序就叫拓扑排序拓扑排序也要检测有向图是否有环即存在循环依赖的情况因为这种情况是不能做线性排序的所以拓扑排序也是图论中判断有向无环图的常用方法。
实现拓扑排序的算法有两种卡恩算法BFS和DFS。一般来说只需要掌握 BFS 广度优先搜索就可以了。
应用场景大学排课先上A课才能上B课上了B课才能上C课上了A课才能上D课等等要求规划出一条完整的上课顺序。
核心思想
拓扑排序时应该优先找 入度为 0 的节点只有入度为0才是出发节点。 拓扑排序的过程
找到入度为0 的节点加入结果集将该节点从图中移除 循环以上两步直到 所有节点都在图中被移除了。如果我们发现结果集元素个数 不等于 图中节点个数我们就可以认定图中一定有 有向环
代码实现
import java.util.*;
public class Main{public static void main (String[] args) {Scanner scannew Scanner(System.in);int nscan.nextInt();int mscan.nextInt();//存放文件之间的映射关系ListListInteger umapnew ArrayList();for(int i0;in;i) umap.add(new ArrayList());//文件的入度int[] inDegreenew int[n];for(int i0;im;i){int sscan.nextInt();int tscan.nextInt();umap.get(s).add(t);inDegree[t];}QueueInteger queuenew LinkedList();//找到入度为零的节点加入队列for(int i0;in;i){if(inDegree[i]0){queue.add(i);}}ListInteger resultnew ArrayList();while(!queue.isEmpty()){int curqueue.poll();result.add(cur);for(int file:umap.get(cur)){inDegree[file]--;if(inDegree[file]0) queue.offer(file);}}if(result.size()n){for(int i0;iresult.size();i){System.out.print(result.get(i));if(iresult.size()-1) System.out.print( );}}else{System.out.println(-1);}}
}dijkstra朴素版-47. 参加科学大会
最短路是图论中的经典问题即给出一个有向图一个起点一个终点问起点到终点的最短路径。
dijkstra算法在有权图权值非负数中求从起点到其他节点的最短路径算法。
dijkstra 算法可以同时求 起点到所有节点的最短路径权值不能为负数
与prim算法类似dijkstra 算法同样是贪心的思路不断寻找距离源点最近的没有访问过的节点。
dijkstra三部曲 第一步选择距离源点最近且未被访问过的节点 第二步被标记改节点已被访问 第三步更新未访问节点到源点的距离即更新minDist数组
代码实现
初始化-minDist数组数值初始化为int最大值。源点节点1 到自己的距离为0所以 minDist[1] 0此时所有节点都没有被访问过所以 visited数组都为0。
import java.util.*;
public class Main{public static void main (String[] args) {Scanner scannew Scanner(System.in);int nscan.nextInt();int mscan.nextInt();int[][] gridnew int[n1][n1];for(int i0;in;i){Arrays.fill(grid[i],Integer.MAX_VALUE);}for(int i0;im;i){int sscan.nextInt();int tscan.nextInt();int kscan.nextInt();grid[s][t]k;}int[] minDistnew int[n1];Arrays.fill(minDist,Integer.MAX_VALUE);boolean[] visitednew boolean[n1];//源点到源点的距离为0minDist[1]0;for(int i1;in;i){int cur1;int minValInteger.MAX_VALUE;for(int j1;jn;j){if(!visited[j] minDist[j]minVal){curj;minValminDist[j];}}//标记改节点已经被访问visited[cur]true;for(int j1;jn;j){if(!visited[j] grid[cur][j]!Integer.MAX_VALUE grid[cur][j]minDist[cur]minDist[j])minDist[j]grid[cur][j]minDist[cur];}}if(minDist[n]!Integer.MAX_VALUE) System.out.println(minDist[n]);else System.out.println(-1);}
}注意设置初始值的时候也要定义cur1这样当节点全都被访问过时cur为合法值。
