[자료구조] 트리(Tree)와 사이클

📌 트리는 사이클을 가질 수 있는가?

➡ "아니요, 트리는 절대 사이클을 가질 수 없습니다!" 🚀
➡ 트리는 "사이클이 없는 연결 그래프"입니다.

---

🚀 1️⃣ 트리의 정의

Types of Trees in Data Structure based on the number of children

출처: https://www.geeksforgeeks.org/types-of-trees-in-data-structures/

 

📌 트리(Tree)란?

• 사이클이 없는 "연결 그래프"
• N개의 노드가 있으면, 항상 "N-1개의 간선"을 가짐
• 모든 노드가 연결되어 있으며, 경로가 유일함
• 루트(Root)에서 시작하여 부모-자식 관계로 이루어짐

📌 트리의 핵심 조건
1️⃣ 모든 노드가 연결되어 있어야 함 (즉, 한 개의 연결 요소)
2️⃣ 사이클이 없어야 함

---

🚀 2️⃣ 트리는 왜 사이클을 가질 수 없는가?

📌 트리는 "N개의 노드에 대해 항상 (N-1)개의 간선만 존재"
📌 사이클이 생기려면 최소한 N개의 간선이 필요!
📌 따라서, 트리는 절대 사이클을 포함할 수 없음.

 

🚀 4️⃣ 트리에서 사이클을 판별하는 방법

✅ DFS를 사용하여 사이클 판별

def has_cycle(node, parent):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            if has_cycle(neighbor, node):
                return True
        elif neighbor != parent:  # 부모가 아닌데 방문한 곳이면 사이클!
            return True
    return False

✅ 한 번 방문했던 노드를 다시 방문하면 사이클 발생! 🚀

 

📌 BFS로 트리에서 사이클을 판별할 수 있을까?

➡ "네! BFS(너비 우선 탐색)로도 트리에서 사이클을 판별할 수 있습니다."
➡ 하지만, DFS보다 약간 더 신경 써야 합니다.

---

🚀 1️⃣ BFS로 사이클을 판별하는 방법

✅ BFS도 그래프의 모든 노드를 방문하면서 사이클을 찾을 수 있음!
✅ 단, BFS에서는 "부모 노드를 제외한 방문한 노드"를 체크해야 함.
✅ 즉, "부모가 아닌데 이미 방문된 노드가 있으면 사이클!"

from collections import deque

def has_cycle_bfs(start, graph, visited):
    queue = deque([(start, -1)])  # (현재 노드, 부모 노드)
    visited[start] = True

    while queue:
        node, parent = queue.popleft()

        for neighbor in graph[node]:
            if not visited[neighbor]:  # 방문하지 않은 노드면 큐에 추가
                visited[neighbor] = True
                queue.append((neighbor, node))
            elif neighbor != parent:  # 부모가 아닌데 방문한 곳이면 사이클 발생
                return True

    return False

def is_tree(n, edges):
    graph = {i: [] for i in range(1, n + 1)}
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    visited = [False] * (n + 1)
    
    # BFS로 사이클 판별
    if has_cycle_bfs(1, graph, visited):  
        return "사이클이 존재함 → 트리가 아님!"
    
    # BFS 종료 후, 모든 노드가 연결되었는지 확인 (트리는 1개의 연결 요소)
    if any(not v for v in visited[1:]):
        return "모든 노드가 연결되지 않음 → 트리가 아님!"

    return "트리임! (사이클 없음, 모든 노드 연결됨)"

# ✅ 예제 테스트
edges1 = [(1, 2), (1, 3), (2, 4), (3, 5)]  # 트리 ✅
edges2 = [(1, 2), (2, 3), (3, 4), (4, 1)]  # 사이클 발생! ❌
edges3 = [(1, 2), (2, 3), (4, 5)]  # 연결 요소 2개 → 트리 아님 ❌

print(is_tree(5, edges1))  # ✅ 트리
print(is_tree(4, edges2))  # ❌ 사이클 발생
print(is_tree(5, edges3))  # ❌ 연결 안 됨

 

🚀 3️⃣ BFS로 사이클을 탐지하는 원리

📌 BFS에서도 DFS처럼 "부모 노드"를 제외한 방문 체크를 해야 함.
📌 부모가 아닌데 이미 방문된 노드가 있으면 → 사이클 발생!
📌 BFS는 너비 우선 탐색이므로, DFS처럼 깊이 있게 탐색하지 않음.

---

🚀 4️⃣ DFS vs BFS 사이클 판별 비교

 

탐색 방법		시간 복잡도	장점	단점
DFS	재귀적으로 탐색	O(N + M)	구현이 간단함	재귀 호출 제한 문제
BFS	큐(Queue)로 탐색	O(N + M)	스택 오버플로우 걱정 없음	부모 노드 체크 필요

✅ BFS도 사이클을 판별할 수 있지만, 부모 노드 체크를 해줘야 함! 🚀
✅ DFS는 기본적으로 스택을 활용하므로, 구현이 간결하고 직관적임!

---

🎯 결론

✅ "BFS도 트리에서 사이클을 판별할 수 있음!"
✅ 단, "부모 노드"를 제외한 방문 여부를 체크해야 정확함!
✅ DFS와 BFS 둘 다 가능하지만, DFS가 조금 더 간결한 코드가 됨. 🚀

 

🚀 5️⃣ 트리 vs 그래프 비교

개념	트리	일반 그래프
사이클 존재 여부	❌ 없음	✅ 가능
간선 개수	N-1개	N-1개 이상
모든 노드 연결 여부	✅ 연결 그래프	❌ 연결되지 않을 수도 있음
최단 경로 탐색	✅ DFS/BFS 가능	✅ DFS/BFS/Dijkstra 가능

✅ 트리는 항상 "사이클이 없는 연결 그래프"이다! 🚀

https://www.geeksforgeeks.org/types-of-trees-in-data-structures/

Types of Trees in Data Structures - GeeksforGeeks