判断一个图是否是树
判断一个图是否是树
Alogrithm:
-
如果无向图具有以下性质，则它是树。
- 没有环
- 图是连通的
-
对于无向图，我们可以使用BFS或DFS来检测以上两个性质：
-
如何检测无向图中的环？
我们可以使用 BFS 或 DFS。对于每个访问过的顶点 ‘v’，如果有一个相邻的 ‘u’ 使得 u 已经被访问过并且 u 不是 v 的父节点，那么图中存在一个环。如果没有为任何顶点找到这样的相邻点，我们就说没有环，参考在一个无向图中找环。
-
如何检查连通性？
由于图是无向图，我们可以从任何顶点开始BFS或DFS，并检查所有顶点是否可达。如果所有顶点都可达，则图连通，否则不连通。
Code:
static class Graph {int V;List<Integer>[] adj;public Graph(int V) {this.V = V;adj = new List[V];for (int i = 0; i < V; i++) {adj[i] = new LinkedList<>();}}void addEdge(int u, int v) {adj[u].add(v);adj[v].add(u);}boolean isCyclicUtil(int u, boolean[] vis, int parent) {vis[u] = true;for (int v : adj[u]) {if (!vis[v]) {if (isCyclicUtil(v, vis, u)) return true;} else if (v != parent) return true;}return false;}boolean isTree() {boolean[] vis = new boolean[V];if (isCyclicUtil(0, vis, -1)) return false;//有环则不是一棵树for (int u = 0; u < V; u++) {if (!vis[u]) return false;//存在没有访问到的节点，说明有部分节点不可达，不是一棵树}return true;}public static void main(String args[]) {// Create a graph given in the above diagramGraph g1 = new Graph(5);g1.addEdge(1, 0);g1.addEdge(0, 2);g1.addEdge(0, 3);g1.addEdge(3, 4);if (g1.isTree())System.out.println("Graph is Tree");elseSystem.out.println("Graph is not Tree");Graph g2 = new Graph(5);g2.addEdge(1, 0);g2.addEdge(0, 2);g2.addEdge(2, 1);g2.addEdge(0, 3);g2.addEdge(3, 4);if (g2.isTree())System.out.println("Graph is Tree");elseSystem.out.println("Graph is not Tree");/*** Graph is Tree* Graph is not Tree*/}
}
Reference
-
Check if a given graph is tree or not
-
在一个无向图中找环
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！