알고리즘 03 - (자료구조 02) Que - “방문한 노드”란 무엇인가?

“방문한 노드”란?

“방문한 노드”는 그래프 탐색 과정에서 이미 탐색한 정점(노드)을 의미합니다.
이 탐색은 그래프의 정점(Vertex)을 대상으로 이루어지며, 노드를 중복 탐색하지 않도록 하기 위해 방문 여부를 기록합니다.

---

그래프와 노드의 정의

• 그래프(Graph):
  • 정점(Vertex)과 간선(Edge)으로 구성된 데이터 구조.
  • 예: ( G = (V, E) ), 여기서 ( V )는 정점 집합, ( E )는 간선 집합.
• 노드(Node):
  • 그래프의 정점(Vertex)으로, 데이터를 표현하는 단위입니다.
  • 예를 들어, 사람 간의 관계를 표현하는 그래프에서 사람은 노드가 됩니다.
• 인덱스와 노드의 차이:
  • 노드: 그래프의 정점을 의미하며, 고유한 값(1, 2, 3 등)으로 나타냅니다.
  • 인덱스: 노드를 배열이나 리스트로 표현할 때 해당 노드의 위치를 나타내는 숫자입니다.

---

“방문한 노드”의 의미

1. 그래프 탐색 중 방문 여부를 기록:
   • 한 번 방문한 노드를 다시 탐색하지 않기 위해 기록합니다.
   • BFS, DFS 탐색에서 이를 통해 중복 탐색 방지와 무한 루프 방지를 수행.
2. 인덱스가 아니라 노드의 값:
   • 방문한 노드는 그래프의 정점을 의미합니다.
   • 예를 들어, 그래프 ( G = {1: [2, 3], 2: [4]} )에서 방문한 노드는 1, 2, 3처럼 그래프의 노드 값을 나타냅니다.

---

예제

그래프

graph = {1: [2, 3], 2: [4], 3: [5], 4: [], 5: []}

BFS 탐색

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드 집합
    queue = deque([start])  # 탐색할 노드 큐

    while queue:
        node = queue.popleft()  # 큐에서 노드 꺼내기
        if node not in visited:
            visited.add(node)  # 방문한 노드로 기록
            print(f"방문한 노드: {node}")
            queue.extend(graph[node])  # 인접 노드 큐에 추가

bfs(graph, 1)

출력

방문한 노드: 1
방문한 노드: 2
방문한 노드: 3
방문한 노드: 4
방문한 노드: 5

---

“방문한 노드”와 인덱스의 관계

1. 노드와 인덱스의 매핑:
   • 노드는 그래프의 정점으로, 그래프 표현 방식에 따라 다릅니다.
   • 배열로 표현된 그래프에서 노드는 배열의 인덱스로 나타날 수 있습니다.

   예:

   graph = [[1, 2], [3], [3], []]  # 노드 0, 1, 2, 3
   

   여기서:

   • 노드 0의 인접 노드는 [1, 2]입니다.
   • “방문한 노드”는 배열의 인덱스를 의미할 수 있습니다.
2. 딕셔너리 기반 그래프:
   • 그래프를 딕셔너리로 표현하면, 노드는 키(key) 값입니다.
   • “방문한 노드”는 딕셔너리의 키로 접근할 수 있습니다.

   예:

   graph = {1: [2, 3], 2: [4], 3: [5], 4: [], 5: []}
   

   여기서:

   • “방문한 노드”는 1, 2, 3, 4, 5와 같은 노드 값입니다.

---

정리

• “방문한 노드”는 그래프의 정점(Vertex)을 의미하며, 인덱스는 특정 구현 방식에서 노드를 식별하는 방법 중 하나일 뿐입니다.
• 탐색 중 방문 여부를 기록하여 중복 탐색을 방지하고, 알고리즘의 효율성을 높입니다.