Graph (그래프)

그래프

• 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결관계를 표현
• 정점(Vertex)의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조
  • v : 정점의 개수, e : 간선의 개수
  • v 개의 정점을 가지는 그래프는 최대 v(v-1)/2 간선이 가능
• 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이

 

그래프 유형

• 무향 그래프 (Undirected Graph)

• 유향 그래프 (Directed Graph)

• 가중치 그래프 (Weighted Graph)

• 사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph)

 

• 완전 그래프
  • 정점들에 대해 가능한 모든 간선들을 가진 그래프

• 부분 그래프
  • 원래 그래프에서 일부의 정점이나 간선을 제외한 그래프

• 인접(Adjacency)
  • 두 개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다라고 한다.
  • 완전 그래프에 속한 임의의 두 정점들은 모두 인접해 있다.

 

그래프 경로

• 경로란 간선들을 순서대로 나열한 것
  • 간선들 : (0, 2) (2, 4) (4, 6)
  • 정점들 : 0 - 2 - 4 - 6
• 경로 중 한 정점을 최대 한 번만 지나는 경로 : 단순 경로
  • 0 - 2 - 4 - 6 / 0 - 1 - 6
• 시작한 정점에서 끝나는 경로 : 사이클(Cycle)
  • 1 - 3 - 5 - 1

 

그래프 표현

간선의 정보를 저장하는 방식, 메모리나 성능을 고려해서 결정

• 인접 행렬 (Adjacent matrix)
  • V x V 크기의 2차원 배열을 이용해서 간선 정보를 저장
  • 배열의 배열 (포인터 배열)
• 인접 리스트 (Adjacent List)
  • 각 정점마다 해당 정점으로 나가는 간선의 정보를 저장
• 간선의 배열
  • 간선(시작 정점, 끝 정점)을 배열에 연속적으로 저장

 

인접 행렬

• 두 정점을 연결하는 간선의 유무를 행렬로 표현
• V x V 정방 행렬
• 행 번호와 열 번호는 그래프의 정점에 대응
• 두 정점이 인접되어 있으면 1, 그렇지 않으면 0으로 표현

 

• 무향 그래프
  • i번째 행의 합 = i번째 열의 합 = v의 차수

• 유향 그래프
  • 행 i의 합 = v의 진출 차수
  • 열 i의 합 = v의 진입 차수

 

• 장단점
  • 구현이 매우 간단함
  • 노드 끼리의 연결여부를 확인할 때, 인접 행렬의 adj[i][j]의 값이 1인지 0인지만 확인하면 되기 때문에 O(N) 시간 복잡도에 확인 가능하다는 장점

    ---

  • 정점의 개수는 많지만, 간선의 수는 얼마 없는 경우 인접 행렬에 데이터 낭비가 이뤄지고, 불필요한 탐색이 오래 이뤄지는 단점

 

인접 리스트

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

• 무향 그래프

• 유향 그래프

그래프 탐색 (순회)

• 비선형구조인 그래프로 표현된 모든 자료를 빠짐없이 탐색하는 것을 의미
  • 깊이 우선 탐색 (DFS, Depth First Search)
  • 너비 우선 탐색 (BFS, Breadth First Search)

 

DFS (깊이 우선 탐색)

추가 설명 게시물 : DFS (Depth First Search, 깊이 우선 탐색)

1. 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색
2. 탐색 중 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 갈림길 정점으로 되돌아옴
3. 그 후 다른 방향의 정점으로 탐색을 이어 진행
4. 위의 과정을 반복하여 모든 정점을 방문하는 순회방법

 

• 2번 과정을 위해서 후입선출 구조의 스택을 사용
• 추가 설명 게시물 : Stack (스택)

 

알고리즘

• DFS 알고리즘 - 재귀

# 재귀함수 구조의 dfs
def dfs1(v):
    visited[v] = 1
    print(v, end = ' ')

    for w in range(N+1):
        if adj[v][w] == 1 and visited[w] == 0:
            dfs1(w)

 

• DFS 알고리즘 - 반복

# 반복구조의 dfs
def dfs2(v):
    res = []    # 방문순서를 저장할 리스트
    s = []      # 스택 생성
    s.append(v) # push(v) 시작점 저장

    while len(s) != 0:  # 스택이 비어있지 않는 경우
        n = s.pop()     # pop(), 갈 수 있는 노드 중 하나를 꺼내 이동

        if visited[n] == 0:
            visited[n] = 1  # 방문했음을 표시
            res.append(n)
            for i in range(N+1):
                if adj[n][i] == 1:  # i와 인접해있다면
                    s.append(i)     # 스택 목록 추가
    return res

 

 

BFS (너비 우선 탐색)

추가 설명 게시물 : BFS (Breadth First Search, 너비 우선 탐색)

1. 탐색 시작점의 인접한 정점들을 먼저 차례로 방문
2. 방문했던 정점을 다시 시작점으로 하여 인접한 정점들을 차례로 방문

 

• 1, 2번 과정을 반복하기 위해, 선입선출 형태의 자료구조인 큐를 활용
• 추가 설명 게시물 : Linear Queue (선형 큐)

 

알고리즘

• BFS 알고리즘 - 반복

def BFS(G, v):
    visited = [0] * n
    queue = []
    queue.append(v)
    visited[v] = True # 시작점을 방문했다고 먼저 선언

    while queue:
        size = len(queue)       # 이렇게 사이즈로 선언하면
        for i in range(size):   # 같은 거리인 정점들끼리 묶어서
            tmp = queue.pop(0)  # 필요 행동을 취할 수 있다.
            visit(t)            # 여기서 필요 행동만 취하고 방문 여부 확인 밑의 반복문에서 진행
            for i in G[t]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True   # 방문 대상인 정점에 대해서 True로 미리 바꿔줌