資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查給定圖是否為樹
在這個問題中，給定一個無向圖，我們需要檢查該圖是否為樹。我們可以透過檢查樹的標準來簡單地找到它。樹不包含環，因此如果圖中存在任何環，則它不是樹。
我們可以使用另一種方法來檢查它，如果圖是連通的並且它有 V-1 條邊，它可能是一棵樹。這裡 V 是圖中頂點的數量。
輸入和輸出
Input: The adjacency matrix. 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 Output: The Graph is a tree
演算法
isCycle(u, visited, parent)
輸入：起始頂點 u，visited 列表用於標記是否已訪問，父頂點。
輸出：如果圖中存在環則返回 True。
Begin mark u as visited for all vertex v which are adjacent with u, do if v is visited, then if isCycle(v, visited, u) = true, then return true else if v ≠ parent, then return true done return false End
isTree(graph)
輸入：無向圖。
輸出：當圖是樹時返回 True。
Begin define a visited array to mark which node is visited or not initially mark all node as unvisited if isCycle(0, visited, φ) is true, then //the parent of starting vertex is null return false if the graph is not connected, then return false return true otherwise End
示例
#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0},
{1, 0, 1, 0, 0},
{1, 1, 0, 0, 0},
{1, 0, 0, 0, 1},
{0, 0, 0, 1, 0}
};
bool isCycle(int u, bool visited[], int parent) {
visited[u] = true; //mark v as visited
for(int v = 0; v<NODE; v++) {
if(graph[u][v]) {
if(!visited[v]) { //when the adjacent node v is not visited
if(isCycle(v, visited, u)) {
return true;
}
} else if(v != parent) { //when adjacent vertex is visited but not parent
return true; //there is a cycle
}
}
}
return false;
}
bool isTree() {
bool *vis = new bool[NODE];
for(int i = 0; i<NODE; i++)
vis[i] = false; //initialize as no node is visited
if(isCycle(0, vis, -1)) //check if there is a cycle or not
return false;
for(int i = 0; i<NODE; i++) {
if(!vis[i]) //if there is a node, not visited by traversal, graph is not connected
return false;
}
return true;
}
int main() {
if(isTree())
cout << "The Graph is a Tree.";
else
cout << "The Graph is not a Tree.";
}輸出
The Graph is a Tree.
更新於： 2020年6月16日
4K+ 瀏覽量
廣告