检查给定图是否为树
在这个问题中,给出了一个无向图,我们必须检查该图是否为树。我们可以通过检查树的条件来简单地找到它。一棵树将不包含循环,因此,如果图中有任何循环,则它不是一棵树。
我们可以使用另一种方法来检查它,如果图形已连接并且具有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,已访问,父代)
输入: 起始顶点u,标记为已访问或未访问的访问列表,父顶点。
输出: 如果图中有一个循环,则为True。
Beginmark 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(图)
输入: 无向图。
输出:图形为树时为True。
Begindefine 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 << "图是一棵树。";
else
cout << "图不是树。";
}
输出结果
图是一棵树。
以上是 检查给定图是否为树 的全部内容, 来源链接: utcz.com/z/352403.html