2020.12.15

1.有向圖判斷是否有環(huán)

對于圖類問題，首先利用鄰接表對圖進行表示，如圖所示：通常使用List<List>的格式存儲表示。

在本題中，輸入為[a,b]表示b指向a，所以鄰接表生成代碼為：

List<List<Integer>> edges = new ArrayList<List<Integer>>(); for (int i = 0; i < numCourses; ++i) { // numCourses為節(jié)點個數(shù)edges.add(new ArrayList<Integer>()); } for (int[] info : prerequisites) {edges.get(info[1]).add(info[0]); }

思路一：拓撲排序（bfs）

通過拓撲排序生成的節(jié)點序列，可以確定是否存在環(huán)。

構(gòu)建的鄰接表就是我們通常認(rèn)識的鄰接表，每一個結(jié)點存放的是后繼結(jié)點的集合。

該方法的每一步總是輸出當(dāng)前無前趨（即入度為零）的頂點。為避免每次選入度為 0 的頂點時掃描整個存儲空間，可設(shè)置一個隊列暫存所有入度為0的頂點。

具體做法如下：

1、在開始排序前，統(tǒng)計課程安排圖中每個節(jié)點的入度，生成 入度表 ，將入度為 0 的頂點均入隊列。

2、只要隊列非空，就從隊首取出入度為 0 的頂點，將這個頂點pre輸出到結(jié)果集（在生成拓撲排序）中，并且將這個頂點的所有鄰接點cur的入度減 1，在減 1 以后，發(fā)現(xiàn)這個鄰接點的入度為 0 ，就繼續(xù)入隊。

最后檢查結(jié)果集中的頂點個數(shù)是否和課程數(shù)相同即可。

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {int[] indegrees = new int[numCourses];List<List<Integer>> edges = new ArrayList<>();Queue<Integer> queue = new LinkedList<>();int valid = 0;for(int i = 0; i < numCourses; i++)edges.add(new ArrayList<>());// Get the indegree and adjacency of every course.for(int[] info : prerequisites) {indegrees[info[0]]++;edges.get(info[1]).add(info[0]);}// Get all the courses with the indegree of 0.for(int i = 0; i < numCourses; i++)if(indegrees[i] == 0) queue.add(i);// BFS TopSort.while(!queue.isEmpty()) {int pre = queue.poll();valid++;for(int cur : edges.get(pre))if(--indegrees[cur] == 0) queue.add(cur);}return numCourses == valid;} }

思路二：dfs

class Solution {List<List<Integer>> edges;public boolean canFinish(int numCourses, int[][] prerequisites) {edges = new ArrayList<>();boolean[] visited = new boolean[numCourses];boolean[] stack = new boolean[numCourses];for(int i = 0; i < numCourses; i++)edges.add(new ArrayList<>());for(int[] info : prerequisites) {edges.get(info[1]).add(info[0]);}for (int i=0;i<numCourses;i++) {if (!visited[i]) {if (dfs(visited,stack,i))return false;}}return true;}public boolean dfs(boolean[] visited, boolean[] stack, int i) {visited[i] = true;stack[i] = true;for (int index : edges.get(i)) {if (visited[index] && stack[index]) return true;if (visited[index]) continue;if (dfs(visited, stack, index)) return true;}stack[i] = false;return false;} }

2.判斷無向圖是否有環(huán)

思路一：并查集

/*** *利用并查集判斷無向圖中是否有環(huán)*/ public class Solution {public int[] parent;//記錄并查集元素父節(jié)點public int depth[];//記錄并查集每個元素的深度//初始化操作public Solution(int nums) {this.parent = new int[nums];this.depth = new int[nums];for(int i = 0;i<nums;i++) {parent[i] = -1;}}public int find_root(int x) {//查找x的代表元素int root = x;while(parent[root]!=-1) {root = parent[root];}return root;}public boolean union(int x,int y) {int x_root = find_root(x);int y_root = find_root(y);if(x_root == y_root) {return false;//說明有環(huán)}else {if(depth[x_root]>depth[y_root]) {//如果x_root樹更深，則把y_root加到x_root上parent[y_root] = x_root;}else if(depth[x_root]<depth[y_root]) {//如果y_root樹更深，則把x_root加到y(tǒng)_root上parent[x_root] = y_root;}else if(depth[x_root] == depth[y_root]) {//相等的情況下，加到哪個都行，相應(yīng)的數(shù)深+1parent[x_root] = y_root;depth[x_root]++;}}return true;}public static void main(String[] args) {int[][] rec = {//鄰接矩陣{0,1,0,0,0},{1,0,1,0,1},{0,1,0,1,0},{0,0,1,0,0},{0,1,0,0,0}};Solution s = new Solution(5);for(int i = 0;i<rec.length;i++) {for(int j = 0;j<i;j++) {if(rec[i][j] == 1) {boolean b = s.union(i, j);if(b == false ) {System.out.println("有環(huán)");return;}}}}System.out.println("沒有環(huán)");} }

總結(jié)

以上是生活随笔為你收集整理的2020.12.15的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。