Graph 그래프

그래프(Graph)는 정점(Vertex)와 간선(Edge)으로 이루어진 자료구조로, 정점 간의 관계를 나타내는 데 사용된다. 그래프는 복잡한 관계나 연결을 표현하는 데 적합하며, 특히 네트워크, 소셜 미디어 연결, 경로 탐색 등의 문제를 해결할 때 유용하다.

그래프의 구성 요소

1. 정점(Vertex): 그래프의 각 점으로, 데이터가 저장되는 단위이다. 정점은 노드(Node)라고도 한다.
2. 간선(Edge): 정점 간의 연결을 나타내며, 두 정점 사이의 관계를 정의한다.

그래프의 종류

1. 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프이다. 정점 A와 B가 연결되어 있다면 A에서 B로, B에서 A로 모두 이동할 수 있다.
2. 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프로, 한 방향으로만 이동 가능하다. A에서 B로 연결된 경우, B에서 A로는 이동할 수 없을 수도 있다.
3. 가중치 그래프 (Weighted Graph): 간선에 가중치(비용)가 부여된 그래프이다. 예를 들어, 지도에서 도시 간의 거리를 가중치로 설정할 수 있다.
4. 사이클 그래프 (Cyclic Graph)와 비순환 그래프 (Acyclic Graph): 사이클이 있는 그래프는 어떤 정점에서 시작하여 다시 해당 정점으로 돌아올 수 있는 경로가 존재하는 그래프이며, 비순환 그래프는 그런 경로가 없는 그래프이다.

그래프의 표현 방법

1. 인접 행렬 (Adjacency Matrix): 그래프를 2차원 배열로 표현하며, 배열의 요소가 간선의 존재 여부를 나타낸다. 주로 간선이 많은 밀집 그래프(Dense Graph)에서 유리하다.
2. 인접 리스트 (Adjacency List): 각 정점에 연결된 정점 목록을 리스트 형태로 표현한다. 간선이 적은 희소 그래프(Sparse Graph)에서 메모리 효율이 좋다.

예제: 인접 리스트로 무방향 그래프 표현

class Graph:
    def __init__(self):
        # 그래프를 인접 리스트로 표현하기 위한 딕셔너리 초기화
        self.graph = {}

    def add_edge(self, vertex, neighbor):
        # vertex가 그래프에 없으면, 빈 리스트로 초기화하여 추가
        if vertex not in self.graph:
            self.graph[vertex] = []
        
        # neighbor가 그래프에 없으면, 빈 리스트로 초기화하여 추가
        if neighbor not in self.graph:
            self.graph[neighbor] = []
        
        # 무방향 그래프이므로 양방향 간선을 추가 (vertex에서 neighbor로)
        self.graph[vertex].append(neighbor)
        
        # 무방향 그래프이므로 양방향 간선을 추가 (neighbor에서 vertex로)
        self.graph[neighbor].append(vertex)

    def display(self):
        # 그래프의 각 정점과 연결된 정점들을 출력
        for vertex in self.graph:
            print(f"{vertex}: {self.graph[vertex]}")

# 그래프 객체 생성
g = Graph()

# 각 정점과 간선을 추가하여 그래프 구조 형성
g.add_edge('A', 'B')  # 정점 'A'와 'B' 사이에 간선 추가
g.add_edge('A', 'C')  # 정점 'A'와 'C' 사이에 간선 추가
g.add_edge('B', 'D')  # 정점 'B'와 'D' 사이에 간선 추가
g.add_edge('C', 'D')  # 정점 'C'와 'D' 사이에 간선 추가
g.add_edge('D', 'E')  # 정점 'D'와 'E' 사이에 간선 추가

# 그래프 구조를 출력
print("그래프 구조:")
g.display()

출력 결과:

그래프 구조:
A: ['B', 'C']
B: ['A', 'D']
C: ['A', 'D']
D: ['B', 'C', 'E']
E: ['D']

그래프 탐색 알고리즘

그래프에서는 탐색 알고리즘을 통해 정점을 방문하고 특정 조건에 맞는 경로를 찾을 수 있다. 주요 탐색 방법에는 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 있다.

1. 너비 우선 탐색 (BFS)

BFS는 시작 정점에서 가까운 정점부터 차례대로 방문하는 방식이다. 주로 큐(Queue) 자료구조를 사용하여 구현한다. 최단 경로 문제에 유용하다.

from collections import deque  # 큐(Queue)를 사용하기 위해 deque를 임포트

def bfs(graph, start):
    visited = set()  # 방문한 정점을 저장할 집합 초기화
    queue = deque([start])  # 탐색을 위한 큐 초기화, 시작 정점을 큐에 추가

    while queue:
        vertex = queue.popleft()  # 큐에서 가장 앞에 있는 정점을 꺼냄
        if vertex not in visited:  # 꺼낸 정점을 아직 방문하지 않았다면
            print(vertex, end=" ")  # 정점을 출력(방문 순서 확인)
            visited.add(vertex)  # 정점을 방문한 것으로 표시
            # 현재 정점에 인접한 모든 정점을 큐에 추가 (방문하지 않은 정점만 추가)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

# 그래프 예제
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print("BFS 탐색 결과:")
bfs(graph, 'A')

출력:

BFS 탐색 결과:
A B C D E F

BFS는 시작 정점(A)에서 가까운 정점(B, C)부터 차례대로 방문하며, 큐를 사용하여 방문할 정점들을 순차적으로 관리한다.

2. 깊이 우선 탐색 (DFS)

DFS는 시작 정점에서 최대한 깊숙이 들어간 후, 더 이상 갈 곳이 없으면 되돌아와 다른 경로를 탐색하는 방식이다. 스택이나 재귀를 사용해 구현할 수 있다.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()  # 방문한 정점을 저장할 집합 초기화

    print(start, end=" ")  # 시작 정점을 출력(방문 순서 확인)
    visited.add(start)  # 시작 정점을 방문한 것으로 표시

    for neighbor in graph[start]:  # 시작 정점에 인접한 모든 정점을 순회
        if neighbor not in visited:  # 인접 정점이 방문되지 않았다면
            dfs(graph, neighbor, visited)  # 인접 정점으로 DFS 재귀 호출

print("\nDFS 탐색 결과:")
dfs(graph, 'A')

출력:

DFS 탐색 결과:
A B D E F C

DFS는 시작 정점(A)에서 가능한 한 경로를 따라 깊이 탐색하며, 방문하지 않은 정점으로 이동한다. 재귀 호출을 통해 방문 경로를 추적하고, 모든 정점을 탐색한다.

그래프의 활용 예시

• 네트워크 연결: 네트워크의 컴퓨터들이 연결되어 있는지 확인하고 경로를 탐색하는 데 사용된다.
• 소셜 네트워크: 사용자 간의 친구 관계를 그래프로 표현하여 친구 추천, 관계 탐색 등을 구현할 수 있다.
• 경로 찾기: 지도에서 두 지점 간의 최단 경로나 최적 경로를 찾는 데 그래프를 사용한다.
• 웹 크롤링: 웹 페이지를 노드로, 하이퍼링크를 간선으로 연결하여 탐색하는 데 활용된다.