ตรวจสอบว่ากราฟที่กำหนดเป็นแผนภูมิหรือไม่

ในปัญหานี้ ให้กราฟแบบไม่มีทิศทางมาหนึ่งกราฟ เราต้องตรวจสอบว่ากราฟนั้นเป็นแบบต้นไม้หรือไม่ เราสามารถค้นหาได้โดยการตรวจสอบเกณฑ์ของต้นไม้ ต้นไม้จะไม่มีวัฏจักร ดังนั้นหากมีวัฏจักรใดๆ ในกราฟ นั่นก็ไม่ใช่ต้นไม้

เราตรวจสอบได้ด้วยวิธีอื่น ถ้ากราฟเชื่อมต่อกันและมีขอบ 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.