그래프

1. 그래프

그래프는 아이템들과 이들 사이의 연결관계를 표현하며, 정점(v)들의 집합과 이들을 연결하는 간선(e)의 집합으로 구성된다.

그래프는 선형자료구조나 트리 자료구조로 표현하기 어려운 N:N 관계를 가지는 원소들을 표현하기에 용이하다.

무향그래프, 유향그래프, 가중치 그래프, 사이클이 없는 방향 그래프(DAG), 정점에 대한 모든 간선을 가진 그래프인 완전그래프 등이 있다. 일반적으로 사이클이 있는 그래프 문제의 경우, 방문을 체크해야 하므로 더 까다롭다.

2. 그래프의 표현

그래프를 표현하는 방식은 크게 3가지가 있다.

2-1. 인접 행렬

v * v크기의 2차원 배열을 이용해 간선 정보를 저장한다.
행 번호와 열 번호는 그래프의 정점에 대응된다.
두 정점이 인접(연결)해 있다면 1, 그렇지 않으면 0으로 표기
진입차수와 진출차수를 간단하게 알 수 있다.

그러나 정점이 많고 노드 수가 적은 그래프의 경우, 메모리의 낭비가 심해진다.

2-2. 인접 리스트

각 정점마다 해당 정점으로 나가는 간선의 정보를 저장한다.

입접리스트로 표현했을때의 문제점 : 진출차수는 해당 배열에 연결된 리스트의 갯수만 알아내면 되지만, 진입차수의 경우 전체 노드를 다 뒤져봐야 하므로 처리가 곤란한 경우가 생긴다. 그러므로 진입차수가 필요한 문제의 경우, 노드를 생성하는 시점에서 카운트 배열을 따로 생성하는 방식으로 추가적인 구현이 필요하다.

2-3. 간선의 배열

간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장

3. 그래프 순회(탐색)

그래프의 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)를 빠짐없이 탐색하는 것을 말한다. 그래프의 탐색 기법에는 BFS, DFS가 있다.

3-1. 깊이 우선 탐색(DFS)

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색해가다가 더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법이다.

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복하므로 후입선출 구조의 스택을 사용한다.

[방법1] 스택을 이용한 깊이 우선 탐색 과정

(1) [이웃 처리] 스택에 push하면서 연결된 이웃 노드를 push한다.

(2) [자가/방문 처리] 이웃된 노드가 없는 경우(이웃이 모두 방문이 완료된 경우) 자기 자신을 pop하고 방문(visited)처리한다.

(3) 앞선 (1), (2)를 반복하여, 더이상 스택에 배열이 남아있지 않은 경우 종료한다.

def DFS(v) :
    stack = []
    stack.append(v)
    while stack :
        v = stack.pop()
        if not visitied[v] :
            visitied[v] = 1
            print(v, end=' ')
            for w in range(1, len(G[v])) :
                if G[v][w] and not visitied[w] :
                    stack.append(w)

'''
- 정점이 7개인 그래프G
- G의 모습은 아래와 같다.
[0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 1, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 1, 1, 0, 0]
[0, 1, 0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 1, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 1, 1, 0, 1]
[0, 0, 0, 1, 0, 0, 1, 0]
'''
visitied = [0]*8
edges = [1, 2, 1, 3, 2, 4, 2, 5, 4, 6, 5, 6, 6, 7, 3, 7]
# 0번 정점은 존재하지 않음, G[0]의 값은 모두 0이다.
G = [[0]*8 for _ in range(8)]
for i in range(0,len(edges),2) :
    G[edges[i]][edges[i+1]] = 1
    G[edges[i+1]][edges[i]] = 1

DFS(1) # 결과: 1 3 7 6 5 2 4

[방법2] 재귀를 이용한 깊이 우선 탐색

def DFS(v) :
    # 현시점에 방문한 노드 출력
    print(v, end=' ')
    visitied[v] = 1
    # i:1~7
    for i in range(1,8) :
        if G[v][i] and not visitied[i] :
            DFS(i)
# 결과 : 1 2 4 6 5 7 3

그래프 순회(DFS, BFS)

그래프