检查给定图是否为树

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

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

回到顶部