检查给定图是否为树

在这个问题中，给定一个无向图，我们需要检查该图是否为树。我们可以通过检查树的标准来简单地找到它。树不包含环，因此如果图中存在任何环，则它不是树。

我们可以使用另一种方法来检查：如果图是连通的并且它有 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，已访问列表用于标记是否已访问，父顶点。

输出：如果图中存在环则返回 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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

示例

#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+ 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告