그래프

1. 그래프

가. 개요

• 그래프는 자료들간에 다대다 관계를 표현할 수 있다.
• 그래프는 사물들과 이들 사이의 연결관계를 표현한다.

나. 요소

• 정점 : Vertex 그래프 구성요소로 하나의 연결점
• 간선 : Edge 두 정점을 연결하는 선
• 차수 : Degree 정점에 열결된 간선의 수
• 그래프는 정점들과 집합과 이들을 연결하는 간선들의 집합으로 구성된 자료구조이다.

다. 특징

• V개의 정점을 가지는 그래프는 최대 V * V(-1) / 2개의 간선이 가능하다.

  ex 5개 정점이 있는 그래프의 최대 간선 수는 10 => 5*4 /2 개이다.

라. 그래프 유형

• 무향 그래프 : 방향이 없는 그래프
• 유향 그래프 : 방향이 있는 그래프
• 가중치 그래프
• 사이클이 없는 방향 그래프(DAG)
• 완전 그래프 : 정점들에 대해 모든 간선을 가진 그래프
• 부분 그래프 : 원래그래프에서 일부를 제외한 그래프
• 트리 : 상위, 하위를 구분하여 계층적 구조를 가지는 그래프

마. 인접

• 두 개의 정점사이에 간선이 존재하면 서로 인접해 있다고 한다.
• 즉, 관계가 있다는 뜻이다.
• 완전 그래프에 속한 임의의 두 정점들은 서로 인접해 있다.

2.그래프 경로

가. 경로?

• 어떤 정점 A에서 시작하여 다른 정점 B로 끝나는 순회
• 두 정점사이를 잇는 간선들을 순서대로 나열한 것.

나. 단순 경로

• 시작정점과 끝 정점을 제외하고 중복된 정점이 없는 경로

그래프를 표현하기위해서는, 다음과 같은 세가지가 있다.
문제에 따라 무엇을 쓸지 잘 생각해보고 쓰자.

다. 인접행렬

• 두 정점을 연결하는 간선의 유무를 행렬로 표현하는 방법이다.
• 행 번호와 열 번호는 그래프의 정점에 대응한다.
• V*V 정방행렬
• 인접하면 1 그렇지 않으면 0으로 표현한다.
• 무향그래프, 유향그래프에 다 쓸 수 있다.
• 유향그래프에서 : 행 i의 합은 Vi의 진출 차수 // 열i의 합은 Vi의 진입차수이다.

• 단점 : 희소 그래프 밀집그래프

라. 인접 리스트

• 각 정점에 대한 인접 정점을 순차적으로 표현한 그래프이다.
• 하나의 정점에 대한 인접 정점들을 각각 노드로 하는 연결리스트로 저장한다.
• 무향그래프, 유향그래프에 다 쓸 수 있다.

• 구성 : 각정점의 연결리스트 HEAD 배열은 node의 리스트로 만들면된다.

마. 간선리스트

• 두 정점에 대한 간선 그 자체를 객체로 저장하여 리스트로 저장한다.
• 간선을 표현하는 두 정점의 정보를 나타낸다.(시작 정점 / 끝 정점)

3. 그래프 순회

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

가. BFS - 너비 우선 탐색

• 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식.
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로 선입 선출 형태의 자료구조인 큐를 활용함

알고리즘

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

구성

• Visited 배열 생성 / false로 초기화
• Q 생성
• 시작 정점 방문 / 방문터리 및 큐

나. DFS - 너비 우선 탐색

• 탐색 시작점의 인접한 정점들을 모두 차례로 방문한 후에, 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식.
• 인접한 정점들에 대해 탐색을 한 후, 차례로 다시 너비 우선 탐색을 진행해야 하므로 선입 선출 형태의 자료구조인 큐를 활용함

알고리즘

DFS (V) 탐색정점
    visited[v] <- True
    FOR each all w in adjancey(G,v)
        IF visited[w] != true
            DFS(W)

구성

• Visited 배열 생성 / false로 초기화
• Q 생성
• 시작 정점 방문 / 방문터리 및 큐

다. 서로소 집합

• 서로 중복된 원소가 없는 집합.
• 상호 배타적인 집합이다.
• 즉, 교집합이 없다.
• 합치는 방법은 대표끼리 합치면된다.

연산

• 처음 : 원소1개를 갖는 서로소 집합 (자기 자신이 곧 대표자이)
• Make-Set : 유일한 멤버 x를 포함하는 새로운 집합을 생성
• Find-Set : 대표자를 찾는 연산 / x를 포함하는 집합을찾는 연산이다.
• Union : x와 y를 통합하는 연산

연산의 효율을 높이기

매번 대표를 찾는데 오래 걸린다.

• Rank를 이용한 Union

• 각 노드는 자신을 루트로 하는 sub트리의 높이을 랭크라는 이름으로 저장한다.

• 두 집합을 합칠 때 랭크가 낮은 집합을 높은 집합에 붙인다. 그러면 랭크는 그대로이다.

• Path Compression : Find set을 행하는 과정에서 만나는 모든 노드 들이 직접 root를 가리키도록 포인터를 바꾸어준다.

표현

• 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
• 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 갖는다.
• 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.0

4. 최소 신장트리 MST

가. 그래프에서 최소 비용 문제 유형

1. 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리
2. 두 정점사이의 최소비용 경로 찾기

나. 신장 트리

n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

다. 최소 신장트리

무향 가중치 그래프에서 신장트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리

라. 크루스칼 알고리즘 (KRUSKAL)

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 최초, 모든 간선을 가중치에 따라 오름 차순으로 정렬
2. 가중치가 가장 낮은 간선 부터 선택하면서 트리를 증가 시킨다.
   단, 사이클이 존재하면 안된다.
3. n-1개의 간선이 선택될때까지 2를 반복
   그리디 알고리즘이다.

마. 프림 알고리즘 (PriM)

• 하나의 정점에서 연결된 간선 중에서 하니씩 선택하면서 MST를 만들어가는 방식

1. 임의의 정점에서 하나 선택해서 시작한다.
2. 선택한 정점과 인접하는 정점들 중에 최소 비용의 간선이 존재하는 정점을 선택
   단, 사이클이 존재하면 안된다.
3. n-1개의 간선이 선택될때까지 2를 반복

• 서로소인 2개의 집하 정보를 유지한다.