[자료구조] 그래프 (Graph)

그래프: 연결된 객체들 사이의 관계를 표현할 수 있는 자료구조

객체들이 서로 복잡하게 연결되어 있는 구조를 표현할 때 이러한 구조를 표현할 수 있는 가장 훌륭한 논리적 도구가 그래프이다.

• 지하철 노선도: 가장 대표적인 그래프의 예시
• 항공 노선도
• 전기회로

그래프는 정점(Vertex)과 간선(Edge)로 이루어진다.
정점 A와 B를 연결하는 간선은 (A, B)와 같이 정점의 쌍으로 표현하며, 그래프를 수학적으로 표현하고 싶다면 G = (V, E)와 같이 나타낼 수 있다.

---

그래프의 종류

이미지 출처:  https://en.m.wikipedia.org/wiki/File:Undirected_graph.svg

1) 무방향 그래프: 간선에 방향이 표시되지 않은 그래프. 따라서 하나의 간선은 양방향으로 갈 수 있는 길을 의미하므로 (A, B)와 (B, A)는 동일한간선이다.

이미지 출처:  https://en.wikipedia.org/wiki/Directed_graph

2) 방향 그래프: 간선에 방향이 존재하는 그래프. 간선은 화살표로 표시되며, 한 쪽 방향으로만 갈 수 있다. 따라서 <A, B>와 <B, A>는 서로 다른 간선이다.

이미지 출처:  https://en.wikipedia.org/wiki/Weighted_network

3) 가중치 그래프: 간선에 비용이나 가중치가 할당된 그래프. 정점 사이의 연결 정보 뿐만 아니라 연결에 필요한 비용을 함께 표현할 수 있다.


4) 부분 그래프: 그래프 G를 구성하는 정점의 집합 V(G)와 간선의 집합 E(G)의 부분 집합으로 이루어진 그래프.

---

그래프 용어

• 인접 정점: 간선에 의해 직접 연결된 정점
• 정점의 차수: 그 정점에 연결된 간선의 수.
  방향 그래프에서는 집입 차수와 진출 차수로 구분된다.
• 경로: 간선을 따라 갈 수 있는 길
• 경로의 길이: 경로를 구성하는 데 사용된 간선의 수
• 단순 경로: 경로 중에서 반복되는 간선이 없는 경로
• 사이클: 단순 경로의 시작 정점과 종료 정점이 같은 경우
• 연결 그래프: 모든 정점들 사이에 경로가 존재하는 그래프
• 트리: 사이클을 가지지 않는 연결 그래프
• 완전 그래프: 모든 정점에 간선이 존재하는 그래프
• 희소 그래프: 간선의 수가 비교적 적은 그래프
• 밀집 그래프: 간선의 수가 비교적 많은 그래프

그래프의 표현

그래프는 인접 행렬과 인접 리스트를 통해 표현할 수 있다.

이미지 출처:  https://mathworld.wolfram.com/AdjacencyMatrix.html

인접 행렬을 통해 표현한 경우

이미지 출처:  https://www.softwaretestinghelp.com/graph-implementation-cpp/

인접 리스트를 통해 표현한 경우

파이썬의 경우 파이썬의 리스트를 이용하면 굉장히 간단하게 표현된다. 또한 객체를 이용해 묶어서 인접 리스트를 표현하면 훨씬 쉽게 나타낼 수 있다.

---

그래프의 탐색

• 깊이 우선 탐색: 탐색이 그 정점과 인접한 정점들 중에서 아직 방문하지 않은 정점으로만 이루어지는 탐색.
  만약 어떤 정점에서 더 이상 방문하지 않은 인접 정점이 없으면 가장 마지막에 만났던 정점으로 되돌아가서 다시 방문하지 않은 정점으로 들어가는 것을 반복한다.
• 너비 우선 탐색: 큐를 이용하여 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색.

import collections

def dfs(graph, start, visited=set()): # 깊이 우선 탐색
    if start not in visited:
        visited.add(start)
        print(start, end=' ')
        nbr = graph[start] - visited
        for v in nbr:
            dfs(graph, v, visited)
            
def bfs(graph, start): # 너비 우선 탐색
    visited = set([start])
    queue = collections.deque([start]) # 파이썬에서 기본으로 제공되는 덱 클래스
    while queue:
        vertex = queue.popleft()
        print(vertex, end=' ')
        nbr = graph[vertex] - visited
        for v in nbr:
            visited.add(v)
            queue.append(v)

mygraph = { '0' : set(['1']),
 # 그래프를 구현해준다.
            '1' : set(['0', '2', '3']),
            '2' : set(['1', '4']),
            '3' : set(['1', '4', '5']),
            '4' : set(['2', '3']),
            '5' : set(['3', '6', '7']),
            '6' : set(['5', '7']),
            '7' : set(['5', '6', '8', '9']),
            '8' : set(['7', '9']),
            '9' : set(['7']) }

start = '3'
dfs(mygraph, start) # 깊이 우선 탐색
bfs(mygraph, start) # 너비 우선 탐색

 

 

작성일자: 2023-03-14