[Advanced] 6. 그래프의 기본과 탐색 - 이론편

그래프 기본

• 객체들과 객체들 간의 연결 관계 표현
• 정점(vertex)들의 집합과 정점을 연결하는 간선(edge)들의 집합
• 선형 자료구조나 트리 자료구조로 표현하기 힘든 N : N 관계를 가지는 원소들을 표현하기에 용이

 

그래프의 종류

무향 그래프 (Undirected Graph)

유향 그래프 (Directed Graph)

가중치 그래프 (Weighted Graph)

 

그래프의 표현

인접행렬 : 두 정점을 연결하는 간선의 유무를 행렬로 표현

단점 - 정점의 개수가 커지면 인접 행렬에 필요한 메모리 크기는 n^2에 비례해서 커짐

 

인접 리스트 : 각 정점마다 인접 정점으로 나가는 간선의 정보 저장

• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결 리스트로 저장

 

 

친구관계 소식전달 문제

• A로부터 시작해서 한 명의 친구에게만 소식을 전달할 수 있다. 최대 몇 명의 친구가 소식을 전달 받을 수 있을까?
• A로부터 시작해서 친구들에게 동시에 소식을 전달할 수 있다. 가장 늦게 소식을 전달받는 친구는 누구일까?

---

그래프 순회

- 비선형구조인 그래프로 표현된 모든 정점을 빠짐없이 탐색

- 깊이 우선 탐색(DFS) vs 너비 우선 탐색(BFS)

 

DFS

• 스택 이용

# G : 그래프, S : 스택, v : 시작정점
# visited : 정점의 방문 정보 표시, False로 초기화
# G[v] : 그래프에 G에서 v의 인접 정점 집합

def DFS(S, v):
    S =[v]
    while S:
	v = S.pop()
    	if v not in visited:
            visited.append(v)
            visit(v)
            S.extend(G[v] - set(visited))
       return visited

• 재귀호출 이용

# G : 그래프, v : 시작정점
# visited : 정점의 방문 정보 표시, False로 초기화
# G[v] : 그래프에 G에서 v의 인접 정점 리스트

def DFS(G, v):
	visited[v] = True
    visit(v)
    for w in G[v]:
    	if not visited[w]:
        	DFS(G, w)

 

BFS

• 큐 이용
   

# G :그래프, Q : 큐, v : 시작 정점
# visited : 정점의 방문 정보 표시, False로 초기화
# G[v] : 그래프에 G에서 v의 인접 정점 리스트

def BFS(Q, v):
    D = [0 for i in range(1000001)]
    D[v] = 0 # v노드까지 가는데 걸리는 거리
    Q.append(v)
    visited[v] = True
    visit(v)
    while Q:
        v = Q.pop(0)
        for w in G[v]:
            if not visited[w]:
                Q.append(w)
                D[w] = D[v] + 1 # w거리 = v까지의 거리 + 1
                visited[w] = True
                visit(w)

 

---

상호배타 집합들 (서로소)

• 서로 중복 포함된 원소가 없는 집합들로 교집합이 없음
• 집합에 속한 하나의 원소를 대표자로 두어 각 집합들을 구분
• 연결 리스트,  트리 이용

 

상호 배타 집합의 연산

Make_Set(x)	원소 x만으로 구성된 집합을 생성
Find_Set(x)	임의의 원소 x가 속한 집합의 대표자를 알기 위한 연산
Union(x)	x원소가 속한 집합과 y원소가 속한 집합을 하나의 집합으로 합치는 연산

 

상호 배타 집합의 트리 표현

 

Make_Set(x)

def Make_Set(x):
    p[x] = x    # 정점 x(인덱스)의 부모노드는 x(p[x])

Find_Set(x)

def Find_Set(x):
    if x == p[x]:
        return x
    else:
        return Finde_Set(p[x])

Union(x)

def Union(x, y):
    p[Find_Set(y)] = Finde_Set(x)

 

위 코드의 문제점

해결 방법

 

Make_Set(x)

# p[x] : 노드 x의 부모노드 저장
# rank[x] : 루트 노드가 x인 트리의 랭크 값 저장

def Make_Set(x):
    p[x] = x    # 정점 x(인덱스)의 부모노드는 x(p[x])
    rank[x] = 0

Find_Set(x)

def Find_Set(x):
    if x != p[x]:
        p[x] = Find_Set(p[x])
    return p[x]

Union(x)

def Union(x, y):
    Link(Find_Set(x), Find_Set(y))
    
def Link(x, y):
    if rank[x] > rank[y]:
        p[y] = x
    else:
        p[x] = y
    if rank[x] == rank[y]:
        rank[y] += 1