주어진 그래프가 트리인지 확인

이 문제에서는 하나의 무방향 그래프가 제공되며 그래프가 트리인지 확인해야 합니다. 트리의 기준을 확인하면 간단히 찾을 수 있습니다. 트리에는 주기가 포함되지 않으므로 그래프에 주기가 있으면 트리가 아닙니다.

다른 접근 방식을 사용하여 확인할 수 있습니다. 그래프가 연결되어 있고 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, 방문 여부를 표시하는 방문 목록, 부모 정점.

출력: 그래프에 주기가 있으면 참입니다.

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(그래프)

입력: 무방향 그래프.

출력: 그래프가 트리인 경우 참입니다.

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.