ตรวจสอบว่ากราฟเป็นต้นไม้หรือไม่ (Check if Graph is Tree)

บทนำ

กำหนดกราฟไม่มีทิศทาง ต้องการตรวจสอบว่าเป็นต้นไม้ (Tree) หรือไม่ เงื่อนไขของต้นไม้: 1) ไม่มีวงจร (Cycle) 2) เชื่อมต่อ (Connected) 3) มีเส้นขอบ V-1 เส้น (V = จำนวนโหนด)

อินพุตและเอาต์พุต

Input: เมทริกซ์ติดกัน 5x5
Output: The Graph is a Tree

อัลกอริทึม

isCycle(u, visited, parent)

Input: โหนดเริ่มต้น u, visited array, โหนด parent
Output: True ถ้ามีวงจร

Begin
    mark u visited
    for โหนด v ติดกับ u do
        if v ไม่ visited then
            if isCycle(v, visited, u) return true
        else if v != parent then return true  // พบวงจร
    done
    return false
End

isTree(graph)

Input: กราฟไม่มีทิศทาง
Output: True ถ้าเป็นต้นไม้

Begin
    กำหนด visited array, mark ทุกโหนด unvisited
    if isCycle(0, visited, -1) return false  // มีวงจร
    if กราฟไม่เชื่อมต่อ (มีโหนด unvisited) return false
    return true
End

ตัวอย่างโค้ด (C++)

#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;
    for(int v = 0; v

ผลลัพธ์
The Graph is a Tree.