检查给定图是否为树

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，给出了一个无向图，我们必须检查该图是否为树。我们可以通过检查树的条件来简单地找到它。一棵树将不包含循环，因此，如果图中有任何循环，则它不是一棵树。

我们可以使用另一种方法来检查它，如果图形已连接并且具有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。

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（图）

输入： 无向图。

输出：图形为树时为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 << "图是一棵树。";
   else
      cout << "图不是树。";
}

输出结果

图是一棵树。

以上是 检查给定图是否为树 的全部内容， 来源链接： utcz.com/z/352403.html

回到顶部