그래프 (Graph)

그래프 (Graph)

그래프는 아이템(사물 또는 추상적 개념)들과 이들 사이의 연결 관계로 표현한다

정점(Vertex) : 그래프의 구성요소로 하나의 연결점

간선(Edge) : 두 정점을 연결하는 선

차수(Degree) : 정점에 연결된 간선의 수

그래프는 정점(Vertex)들의 집합과 이들을 연결하는 간선(Edge)들의 집합으로 구성된 자료 구조

V : 정점의 개수, E : 그래프에 포함된 간선의 개수

V 개의 정점을 가지는 그래프는 최대 V * (V-1) / 2 개의 간선이 가능(무향 그래프, 양방향)

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

트리는 계층형 관계와 1:N 관계를 나타내는 특수한 그래프 형태

그래프 유형

무향 그래프(Undirected Graph), 양방향

유향 그래프(Directed Graph), 단방향

가중치 그래프(Weighted Graph)

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

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

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

트리도 그래프이다.

• 각 노드는 최대 하나의 부모 노드가 존재할 수 있다.
• 각 노드는 자식 노드가 없거나 하나 이상이 존재할 수 있다.
• 두 노드 사이에는 유일한 경로가 존재한다.

인점(Adjacency)

두개의 정점에 간선이 존재(연결됨)하면 서로 인접해 있다고 한다.

완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.

그래프 표현

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

인접행렬(Adjacent matrix)

V * V 크기의 2차원 배열을 이용해서 간선 정보 저장

배열의 배열

V * V 정방 행렬

행 번호와 열 번호는 그래프의 정점에 대응

두 정점이 인접되어 있으면 1, 그렇지 않으면 0 (가중치가 없는 그래프)

가중치가 있을 경우, 인접여부 + 가중치를 표현

무향 그래프

i 번째 행의 합 = i 번째 열의 합 = Vi의 차수

유향 그래프

행 i의 합 = Vi의 진출 차수

열 i의 합 = Vi의 진입 차수

인접 리스트(Adjaccent List)

각 정점마다 다른 정점으로 나가는 간선의 정보를 저장

간선 리스트(Edge List)

간선(시작 정점, 끝 정점)의 정보를 객체로 표혀하여 리스트에 저장

그래프 탐색(순회)

그래프 순회는 비선형구조인 그래프로 표현된 모든 자료(정점)을 빠짐없이 탐색하는 것을 의미한다.

두 가지 방법

너비 우선 탐색(Breadth First Search, BFS)

깊이 우선 탐색(Depth First Search, DFS)

너비 우선 탐색(Breadth First Search, BFS)

너비우선탐색은 탐색의 시작점(임의 설정)의 인접한 정점들을 먼저 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인점한 정점들을 차례로 방문하는 방식

인점한 정점들에 대해 탐색을 한 후, 차례로 다시 너비우선탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 큐를 활용함

너비로 방문순서를 관리

BFS(G, V) // 그래프 G, 탐색 시작 정점 v
    큐 생성
    시작 정점 v를 큐에 삽입
    정점 v를 방문한 것으로 표시
    while(큐가 비어 있지 않은 경우) {
        t -> 큐의 첫 번째 원소 반환
        for(t와 연결된 모든 간선에 대해) {
            u <- t의 인접 정점
            u가 방문되지 않은 곳이면,
            u를 큐에 넣고, 방문한 것으로 표시
        }
    }
end BFS()

깊이 우선 탐색(Depth First Search, DFS)

시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색

더 이상 갈 곳이 없게 되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 방문

모든 정점을 방문하는 순회 방법

가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복

재귀적으로 구현 혹은 후입선출 구조의 스택 사용

// 재귀적 방법
G : 그래프
DFS(v) // v: 탐색 정점

    visited[v] = true // v 방문 처리

    for each all w in adjacency(G, v)
        if visited[w] != true
            DFS(w)

end DFS()