[자료구조]그래프 정리(python)

그래프에 대한 내용 정리

그래프

📖 그래프 용어

그래프: 정점과 간선의 집합으로 간선은 두 정점을 연결
표현: $G=(V, E)$로 표현
방향 그래프(Directed Graph): 간선에 방향이 있는 그래프
무방향 그래프(Undirected Graph): 간선에 방향이 없는 그래프

📖 간선 표현

$(a, b)$: 정점 a, b를 연결하는 간선
$<a, b>$: 정점 a, b를 연결하는 방향 있는 간선

📖 차수

차수(Degree)`: 정점에 인접한 정점의 수
진입 차수(in-degree): 방향 그래프에서의 정점에서 들어오는 방향의 정점의 수
진출 차수(out-degree): 방향 그래프에서의 정점에서 나가는 방향의 정점의 수

📖 경로

경로: 시작점 부터 도착점까지의 정점의 나열
ex) [a, c, b, e] >단순경로: 경로 상의 정점이 모두 다른 경로
일반적인 경로: 동일한 정점을 중복해서 방문
사이클(Cycle): 시작점과 도착점이 동일한 단순 경로

📖 추가 용어

연결성분: 그래프에서 정점들이 서로 연결되어 있는 부분
가중치 그래프: 간선에 가중치가 부여된 그래프
부분 그래프: 주어진 그래프의 정점과 간선에 일부분으로 이루어진 그래프(부분 집합)
트리: 사이클이 없는 그래프
신장 트리: 주어진 그래프가 하나의 연결 성분으로 구성되어 있을 때, 그래프의 모든
정점들을 사이클 없이 연결하는 그래프

자료구조

인접 행렬

인접 행렬은 그래프를 2차원 배열로 나타내는 방법입니다. 배열의 크기는 노드의 개수에 따라
결정됩니다.

• 구조: 그래프의 노드가 $n$개일 때, 인접 행렬은 $n \times n$ 크기의 2차원 배열을 사용합니다.
  • 행렬의 요소 $a[i][j]$는 노드 $i$와 노드 $j$ 사이에 간선이 존재하는지를 나타냅니다.
  • 가중치가 있는 그래프의 경우 $a[i][j]$는 간선의 가중치를 나타낼 수 있습니다. 가중치가 없는 경우 0 또는 1로 표시됩니다.
• 공간 복잡도: $O(n^2)$
• 장점: 특정 두 노드 사이의 간선 존재 여부를 $O(1)$ 시간에 확인할 수 있습니다.

인접 리스트

인접 리스트는 그래프를 리스트의 배열로 나타내는 방법입니다. 각 리스트는 해당 노드와
연결된 이웃 노드들을 포함합니다.

구조: 그래프의 각 노드에 대해 연결된 노드들의 리스트를 유지합니다.

• 리스트의 인덱스는 노드를 나타내며, 각 인덱스에 연결된 리스트는 이웃 노드들을 나타냅니다.
• 공간 복잡도: $O(n+e)$ (여기서 $e$는 간선의 개수)
• 장점: 공간 효율적이며, 특히 희소 그래프에서 유리합니다. 노드의 이웃을 순회하는 데 효율적입니다.

인접 리스트와 인접 행렬 혼합

희소 그래프 vs 조밀 그래프

희소그래프: 노드의 수에 비해 간선의 수가 적은 그래프

조밀그래프: 간선의 수가 최대 간선 수에 근접한 그래프

희소 그래프에 가까울수록 인접리스트가 적합, 조밀 그래프에 가까울 수록 인접 행렬이 적합

그래프 탐색

DFS

📖 정의

그래프 탐색 알고리즘 중 하나로, 출발 노드에서 시작하여 한 방향으로 가능한 한 깊게
탐색하다가 더 이상 갈 수 없으면 다른 경로를 탐색하는 방식입니다.

동작 과정

• 시작 정점에서 출발하여 인접한 정점을 방문합니다.
• 방문한 정점에서 다시 인접한 정점으로 이동하여 탐색을 계속합니다.
• 더 이상 갈 수 없는 정점에 도달하면, 이전 정점으로 되돌아가서 다른 경로를 탐색합니다.
• 모든 정점을 방문할 때까지 이 과정을 반복합니다.

구현 코드

adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1], [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]
N = len(adj_list)
visited = [None] * N  # 정점 방문 여부 확인 용

def dfs(v):
    visited[v] = True  # 정점 v 방문
    print(v, ' ', end='')  # 정점 v 방문
    for w in adj_list[v]:
        if not visited[w]:  # 정점 v에 인접한 정점으로 dfs() 재귀호출
            dfs(w)

print('DFS 방문 순서:')
for i in range(N):
    if not visited[i]:
        dfs(i)  # dfs() 호출

DFS 방문 순서:
0  2  3  9  8  1  6  7  5  4

시간 복잡도 및 특징

• 탐색 순서: 한 방향으로 갈 수 있는 만큼 깊이 들어간 후, 더 이상 갈 수 없을 때 다른 경로를 탐색합니다.
• 시간 복잡도: 그래프가 인접 리스트로 표현된 경우 $O(V + E)$ (여기서 $V$는 노드의 수, $E$는 간선의 수).
• 공간 복잡도: 재귀 호출을 사용하는 경우 재귀 호출 스택의 깊이에 따라 공간이 필요합니다.

BFS

📖 정의

시작 정점에서 출발하여 인접한 모든 정점을 우선으로 방문하고, 그 다음으로 각 인접 정점의
인접 정점을 차례로 방문하는 방식

동작 방식

• 시작 정점에서 출발하여 인접한 모든 정점을 큐에 넣습니다.
• 큐에서 정점을 하나씩 꺼내어 방문하고, 해당 정점에 인접한 모든 정점을 다시 큐에 넣습니다.
• 큐가 빌 때까지 이 과정을 반복합니다.

구현 코드

adj_list = [[2, 1], [3, 0], [3, 0], [9, 8, 2, 1], [5], [7, 6, 4], [7, 5], [6, 5], [3], [3]]
N = len(adj_list)
visited = [None] * N  # 정점 방문 여부 확인 용

def bfs(i):
    queue = []  # 큐를 리스트로 구현
    visited[i] = True
    queue.append(i)
    while len(queue) != 0:
        v = queue.pop(0)  # 큐의 맨 앞에서 제거된 정점을 v가 참조하게 함
        print(v, ' ', end='')  # 정점 v 방문
        for w in adj_list[v]:
            if not visited[w]:  # v에 인접하면서 방문 안 된 정점 큐에 삽입
                visited[w] = True
                queue.append(w)

print('BFS 방문 순서:')
for i in range(N):
    if not visited[i]:
        bfs(i)  # bfs() 호출

BFS 방문 순서:
0  2  1  3  9  8  6  7  5  4

시간 복잡도 및 특징

• 탐색 순서: 시작 정점에서 가까운 정점부터 차례대로 탐색합니다.
• 시간 복잡도: 그래프가 인접 리스트로 표현된 경우 $O(V + E)$ (여기서 $V$$는 노드의 수, $E$는 간선의 수).
• 공간 복잡도: 방문해야 할 정점을 저장하기 위해 큐가 필요하며, 최악의 경우 공간 복잡도는 $O(V)$가 될 수 있습니다.

그래프 활용 예제

연결 성분 찾기

adj_list = [[3], [6, 10], [7, 11], [0, 6, 8], [13], [14], [1, 3, 8, 10, 11], [3, 6, 10, 12], [13], [4, 9], [5]]
N = len(adj_list)
CCList = []
visited = [None] * N  # 정점 방문 여부 확인 용

def dfs(v):
    visited[v] = True
    cc.append(v)  # 현재 연결성분에 정점 v 추가
    for w in adj_list[v]:
        if not visited[w]:  # 정점 v에 인접한 w로 dfs() 재귀호출
            dfs(w)

for i in range(N):
    if not visited[i]:
        cc = []  # 새로운 연결성분(cc)을 위한 초기화
        dfs(i)  # dfs() 호출로 cc 만들기
        CCList.append(cc)  # 완성된 cc를 연결성분 리스트에 추가

print('연결성분 리스트:')
print(CCList)

연결성분 리스트:
[[0, 3, 6, 1, 10, 7, 11, 8, 13, 12], [2, 9, 4], [5, 14]]

위상 정렬

📖 정의

사이클이 없는 방향 그래프에서 정점을 선형순서로 나열하는 것

1. 순방향 방법 (Kahn’s Algorithm)

• 과정:
  1. 모든 노드의 진입 차수(In-degree)를 계산합니다.
  2. 진입 차수가 0인 모든 노드를 큐에 넣습니다.
  3. 큐에서 노드를 하나씩 꺼내어 출력하고, 해당 노드와 연결된 간선을 그래프에서 제거합니다.
  4. 간선을 제거한 후에 진입 차수가 0이 된 노드를 다시 큐에 넣습니다.
  5. 큐가 빌 때까지 이 과정을 반복합니다.

2. 역방향 방법 (Depth-First Search 기반)

• 과정:
  1. 각 노드에 대해 DFS를 수행하여 탐색합니다.
  2. DFS가 끝난 노드를 스택에 쌓습니다.
  3. 모든 노드에 대해 DFS를 완료하면 스택에 쌓인 순서를 역순으로 출력합니다.

adj_list = [[1], [3, 4], [0, 1], [6], [5], [7], [7], [8], []]
N = len(adj_list)
visited = [None] * N  # 정점 방문 여부 확인 용
s = []  # 위상 정렬 결과 리스트 초기화

def dfs(v):
    visited[v] = True
    for w in adj_list[v]:
        if not visited[w]:  # 정점 v의 모든 인접한 정점이 방문되었으므로 정점 v 추가
            dfs(w)
    s.append(v)

for i in range(N):
    if not visited[i]:
        dfs(i)  # dfs() 호출로 시작

s.reverse()  # s의 역순으로 위상 정렬 결과 얻음
print('위상 정렬:')
print(s)

위상 정렬:
[2, 0, 1, 4, 5, 3, 6, 7, 8]

수행시간

• 위상 정렬 알고리즘의 수행 시간은 DFS의 수행 시간과 동일한 $O(n+m)$
• 기본적으로 DFS를 수행하며 추가로 소요되는 시간은 line 23에서 정점을 리스트에 저장하고, 모든 탐색이 끝나면 리스트를 역순으로 만드는 시간: $O(n)$
• 총 수행 시간: $O(n+m) + O(n) = O(n+m)$

이중 연결 성분

📖 정의

무방향의 연결 성분에서 임의의 두 점 사이에 적어도 두 개의 단순 경로가 존재하는 연결 성분
하나의 단순 경로 상의 어느 정점 하나가 삭제되더라도 삭제된 정점을 거치지 않는 또 다른
경로가 존재하므로 연결 성분내에서 정점들 사이의 연결이 유지됨

• 단절 정점: 연결 성분의 정점 중 하나의 정점을 삭제했을 때, 두 개 이상의 연결 성분으로 분리될 때 삭제된 정점
• 다리 간선: 간선을 제거했을 때 두 개 이상의 연결 성분으로 분리될 떄 삭제된 간선

강 연결 성분

📖 정의

방향 그래프에서 연결 성분 내의 임의의 두 점 u와 v에 대해 u에서 v로 가는 경로가 있고
동시에 v에서 u로 돌아오는 경로가 있는 연결 성분 강 연결 성분은 **단절 정점**이나 **다리 간선**을 포함하지 않는다.

• 시간 복잡도: $O(N + M)$

MST(최소 신장 트리)

📖 정의

하나의 연결 성문으로 이루어진 무방향 가중치그래프에서 간선의 가중치의 합이 최소인 신장 트리

정답 d

Prim(프림) 알고리즘

📖 정의

임이의 시작점에서 가장 가까운 정점을 추가하여 간선이 하나의 트리를 만들고, 만들어진
트리에 인접한 가장 가까운 정점을 하나씩 추가하여 mst를 만든다.

• 시간 복잡도:
  • 이진 힙 사용하지 않을 때: $n \times (O(n) + O(n)) = O(n^2)$
  • 이진 힙 사용시 : $O(m\log n) = O(n\log )$