# 개요

최단 경로 문제 정리

단어가 좀 혼용될 수 있다

• Ex) 노드==정점 / 간선==엣지 

# 최단 경로 문제

가중치가 있는 방향/무방향 그래프에서 두 노드 사이의 가장 짧은 경로를 찾는 문제

# 최단 경로 문제의 유형

Single-Source / Single-Destination (One - to - All)

• 하나의 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 문제
• 모든 노드로부터 하나의 목적지 노드까지의 최단 경로를 찾는 문제
• 방향을 뒤집으면 서로 같아지기 때문에 사실상 같은 유형으로 본다.
• Dijkstra 알고리즘, Bellman Ford 알고리즘

All-Pairs (All - to - All)

• 모든 노드 쌍에 대하여 최단 경로를 찾는 문제
• Floyd-Warshall 알고리즘

# 최단경로와 음수 가중치

Dijkstra 알고리즘은 음수 가중치가 있을 경우 작동하지 않는다.

Bellman-Ford와 Floyd-Warshall 알고리즘은 음수 사이클이 없다는 가정하에 음수 가중치가 있어도 작동한다.

음수 사이클

음수 사이클이 있으면 최단 경로가 정의되지 않는다.

• 사이클의 합이 음수라면 계속 사이클을 돌게 되고 결국 합이 -∞되어 최단 경로를 찾을 수 없다.
• 단, 그래프 내에 음수 사이클이 있어도 그 사이클이 목적지까지 가는 경로에 없다면 상관없다.

# 최단 경로 문제의 기본 특성

1. 최단 경로의 어떤 부분 경로 역시 최단 경로이다. (Optimal SubStructure → DP)

• 위 경로가 u → v의 최단 경로라면, x → y의 경로 또한 최단 경로이다.

증명 (귀류법)

• 만약 더 짧은 경로(x → y)가 있다고 가정해보자
• 이 경로가 더 짧다면 u → v의 최단 경로는 u → v가 아니라 x → y를 거쳐가는 u → x → y → v가 될 것이다.
• 이것은 처음 가정(u →v 가 최단 경로라면)의 모순이 된다.
• 그러므로 최단 경로의 부분 경로도 최단 경로이다.

2.  최단 경로는 사이클을 포함하지 않는다.

# Single-Source 최단 경로 문제

음수 사이클이 없는 가중치 방향 그래프 G = (V, E)와 출발 노드 S에서 각 노드 v에 대하여 다음을 계산한다.

• d[v] (distance estimation): 출발 노드 S로부터 각 노드v에 대하여 현재까지 알고 있는 최단 경로의 길이 (→ 알고리즘이 진행됨에 따라 갱신 된다.)
  
  • 처음에는 d[S] = 0, 각 d[v]들은 ∞으로 초기화한다.
    • S는 출발 노드이고, 음수 사이클이 없으므로 가장 작은 값인 0
    • 그 외의 다른 노드들 v는 아직 탐색 시작을 안했으므로 ∞
  • 알고리즘이 수행됨에 따라 d[v]가 점점 감소하며 최종적으로 d[v]값이 S →  v의 최단 경로 길이가 된다.
• π[v] (predecessor): S에서 v까지의 최단 경로 상에서 v의 직전 노드
  • 처음에는 π[v]와 π[S]는 null로 초기화
    • 출발 노드S의 이전 노드는 없으므로 null
    • 다른 노드들 v는 아직 탐색 시작을 안했으므로 null
  • 최단경로의 길이 외에 그 경로 자체를 요구할 수 있으므로 이전 노드를 기록하며 역추적한다.

기본 연산: Relaxation

1. d[u] = 5, d[v] = 9, w(u,v) = 2(간선 u → v의 가중치 값)인 상황

• d[v]는 "현재까지 알고 있는" S → v의 최단 경로 길이 이므로 Relaxation 연산에  따라 갱신 될 수 있다.
• 기존에 알고 있는 S →  v의 최단 경로는 S →  v로 d[v] = 9 였는데 더 짧은 경로인 S → u → v경로를 발견했으므로 d[v] = d[u] + w(u,v)로 갱신한다 (9 > 5+2)

2. d[u] = 5, d[v] = 6, w(u,v) = 2인 상황

• Relaxation 연산을 했지만 기존 최단 경로인 S → v d[v]가 더 짧은 경로이므로 갱신하지 않는다.

Relaxtaion 의사 코드

Relax(u, v, w) {
	if(d[v] > d[u] + w(u,v))
    	then d[v] ← d[u] + w(u,v)
        	 π[v] ← u
}

대부분의 Single-Source 최단 경로 알고리즘의 기본 구조

1. 초기화: d[S] = 0, 노드 v에 대해 d[v] = ∞, π[v]=null
2. 간선들에 대해서 반복적인 Relaxtation 연산

의사 코드

Generic-Single-Source(G, w, S) {
	Init(G, S)
    Repeat
    	for each edge(u,v)
        	Relax(u,v,w)
    until there is no change
}

1. 의문: 이렇게 반복하면 최단 경로가 정말 찾아질까?
2. 의문: 찾아진다면 몇 번 반복해야 찾아질까?

증명

• 가정: N개의 정점에서, S → vn 경로가 최단 경로라면 이 경로에 포함된 간선의 개수는 최대 N-1개이다.
• 첫 번째 Round
  • 모든 간선들에 대해 Relax연산을 하고, d[S] = 0, d[v1]이  ∞에서 d[S] + w(S, v1)을 통해 갱신 된다.
  • S → vn까지의 최단 경로의 부분 경로 역시 최단 경로이므로 갱신 된 d[v1]이 곧 최단 경로가 된다.
• 두 번째 Round
  • 모든 간선들에 대해 Relax연산을 하고, d[v2]이  ∞에서 d[v1] + w(v1, v2)을 통해 갱신 된다.
  • 마찬가지로 갱신 된 d[v1]이 곧 최단 경로가 된다.
• 반복하면 d[vn]은 n-1번째 Round에 최단 경로가 된다.
• 즉 노드의 개수가 N개라면 N-1번의 반복으로 모든 노드의 최단 경로를 구할 수 있다.

직관적으로 봐도 vn까지 최단 경로의 간선 수는 최대 N-1라는 것을 생각할 수 있는데

• vx를 거쳐가는 더 짧은 경로가 있다면? → 그럼 그 경로가 최단 경로가 되며, N개의 정점에서 N+1개의 정점이 되었다. 그러므로 간선의 개수는 최대 N개가 될 것이다.

• v2 → v3 → v4 경로를 통해 가는 것보다 v3 → v2 갔다가 다시 v2 → v3으로 가는 것이 더 빠르다면? → 그 자체로 음수 사이클이 생긴다는 뜻이며 음수 사이클이 없다는 전제에 모순된다.

Worst Case

시간 복잡도: O(n^3) → 효율적인 알고리즘이라고 할 수 없다.

다음과 같은 상황을 보자

• 첫 번째 Round에서 간선들을 어떠한 순서로 Relax 연산을 하다보니 d[v] = 1000이 되었다.
• 두 번째 Round에서 간선들을 어떠한 순서로 Relax 연산을 하다보니 d[v] = 800이 되었다.
• 최악의 상황은 마지막 Round에서 d[v] = 200으로 갱신 되고 이것이 최단 경로라는 것을 알게 되었을 때이다. 그제서야 v 이후의 노드들에 대한 최단 경로를 알 수 있게 된다.
• 하지만 처음부터 가중치가 50인 경로로 Relax를 했다면 더 빠르게 최단 경로를 찾을 수 있지 않았을까?
  • Dijkstra 알고리즘으로 해결
• 최악의 경우 시간 복잡도가 O(n^3)인데도 사용하는 이유는 가중치가 음수일 때도 동작하고, 음수 사이클 여부를 알 수 있기 때문이다.

# Reference

권오흠 교수님 유튜브 및 강의자료

그래프 순회

• 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업
• 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를 하여 중복방문을 피한다.
• 대표적으로 DFS, BFS가 있다.

BFS (Breath-First-Search): 너비 우선 탐색

• 출발노드에서 인접한 노드(형제노드)를 먼저 탐색하는 방식
• 가중치가 없는 그래프에서 최단경로를 찾을 때 사용한다.
• 일반적으로 Queue를 이용하여 구현한다.

동작방식

1. 시작정점을 방문하여 큐에 삽입한다.
2. 큐에서 정점을 꺼내 정점에서 인접한 정점중, 방문하지 않은 정점들을 방문하여 큐에 삽입한다.
3. 모든 정점을 반복할 때까지 반복한다.

Visualize

E노드에서 더이상 간선이 없으므로 그냥 큐에서 꺼내는것으로 끝이다

G노드에서 더이상 간선이 없으므로 그냥 큐에서 꺼내는것으로 끝이다. H노드와 I노드도 마찬가지이다.

코드

의사코드

BFS(graph, start_node) {
  Queue q;
  boolean[] visit;
  
  q.add(start_node);
  visit[start_node] = true;
  
  while(!q.isEmpty()) {
    current_node = q.pop();
    for(adjacent_node to current_node) {
      if(!visit[adjacent_node]) {
        visit[adjacent_node] = true;
        q.add(adjacent_node);
      }
    }
  }
}

코드 - Queue (Java)

class BFS_Queue {
  private int[][] graph;
  private boolean[] visit;
  
  public BFS_Queue() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    this.visit = new boolean[graph.length];
  }
  
  public void bfs(startNode) {
    Queue<Integer> queue = new LinkedList();
    
    queue.add(startNode);
    visit[startNode] = true;
    
    while(!queue.isEmpty()) {
      int currentNode = queue.poll();
      
      for(int i = 0; i < graph[currentNode].length; i++) {
        if(isAdjacentNode(currentNode, i) && !visit[i]) {
          visit[i] = true;
          queue.add(i);
        }
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }
}

시간 복잡도

• 인접 리스트: $O(N+E)$ ($N$: 정점 개수, $E$: 간선 개수)
• 인접 행렬: $O(N^2)$

참고

2021.04.14 - [Algorithm] - [Algorithm] 그래프 (Graph)

2022.01.08 - [Algorithm] - [Algorithm] DFS (Depth-First-Search, 깊이 우선 탐색)

그래프 순회

• 그래프에서 임의의 한 정점에서 출발하여 모든 정점을 한번씩 방문하는 작업
• 탐색하는 동안 이미 방문한 정점이 있을 수 있으므로 방문했다는 표시를하여 중복방문을 피한다.
• 대표적으로 DFS와 BFS가 있다.

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

• 출발노드에서 하위노드(자식노드)를 먼저 탐색하는 방식
• 일반적으로 Stack이나 Recursive를 이용하여 구현한다.

동작방식

1. 시작노드에서 간선을 따라 다음노드로 방문한다.
2. 더이상 탐색할 간선이 없다면 역추적(Backtracking)을 통해 이전노드로 이동하여 아직 탐색하지 않은 간선을 참색한다.
3. 모든 노드를 탐색할 때까지 반복한다.

Visualize

E노드에서 더이상 이동 할 간선이 없으므로 역추적으로 통해 B노드로 이동, B노드에서도 마찬가지로 더이상 이동할 간선이 없으므로 A노드로 이동 후 다음 간선인 (A,C)을 통해 C노드로 이동

F노드에서 더이상 이동할 간선이 없으므로 역추적을 통해 C노드로 이동, C노드에서 다음 간선인 (C,G)을 통해 G노드로 이동

I노드에서 더이상 이동할 간선이 없으므로 역추적을 통해 G노드로 이동, G노드에서도 마찬가지로 C노드로 이동, C노드에서도 마찬가지로 A노드로 이동, A노드에서 다음 간선인 (A,D)를 통해 D노드로 이동

코드

의사코드

DFS(graph, current_node, visit) {
  visit[current_node] = true
  
  for( adjacent_node to current_node) {
    if(!visit[adjacent_node]) {
      DFS(graph, adjacent_node, visit)
    }
  }
}

코드 - Recursive (Java)

class DFS_Recursive {

  private int[][] graph;
  
  private boolean[] visit;
  
  public DFS_Recursive() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    visit = new boolean[graph.length];
  }
  
  public void dfs(currentNode) {
    visit[currentNode] = true;
    
    for(int i = 0; i < graph[currentNode].length; i++) {
      if(isAdjacentNode(currentNode, i) && !visit[i]) {
        dfs(i);
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }

}

코드 - Stack

class DFS_Stack {

  private int[][] graph;
  
  private boolean[] visit;
  
  public DFS_Stack() {
    this.graph = {
      {0, 1, 1, 1, 0, 0, 0, 0, 0},
      {1, 0, 0, 0, 1, 0, 0, 0, 0},
      {1, 0, 0, 0, 0, 1, 1, 0, 0},
      {1, 0, 0, 0, 0, 0, 0, 1, 0},
      {0, 1, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 1, 0, 0, 0, 0, 0, 1},
      {0, 0, 1, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 1, 0, 0, 0},
    };
    visit = new boolean[graph.length];
  }
  
  public void dfs(startNode) {
    Stack<Integer> stack = new Stack();
    
    stack.push(startNode);
    visit[startNode] = true;
    
    while(!stack.isEmpty()) {
      int currentNode = stack.pop();
      
      for(int i = 0; i < graph[currentNode].length; i++) {
        if(isAdjacentNode(i) && !visit[i]) {
          stack.push(i);
          visit[i] = true;
        }
      }
    }
  }
  
  public boolean isAdjacentNode(int currentNode, int targetNode) {
    return graph[currentNode][targetNode] == 1;
  }

}

시간복잡도

• 인접 리스트: $O(N+E)$ ($N$: 정점 개수, $E$: 간선 개수)
• 인접 행렬: $O(N^2)$

참고

2021.04.14 - [Algorithm] - [Algorithm] 그래프 (Graph)

2022.01.08 - [Algorithm] - [Algorithm] BFS (Breath-First-Search, 너비 우선 탐색)

Heap Sort

• Heap 자료구조를 이용하여 정렬하는 방식
• Best case, Worst case 모두 시간 복잡도가 $O(nlogn)$
  • 그러나 대체로 Quick Sort보다 느림
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort) : 비교하는 원소의 값이 같을 때, input 순서대로 정렬

• 

Heap (약식)

• 최댓/최솟값을 찾는 연산을 빠르게 하기위해 고안된 자료구조
• 완전 이진트리(Complete Binary Tree)
• 부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높음
• index i에 대해서
  • 왼쪽 자식 노드의 index: $i\ast 2+1$
  • 오른쪽 자식 노드의 index: $i\ast 2+2$
  • 부모 노드의 index: $i/2$
• 구조적으로 Tree이지만 배열로 표현가능
  •  

    

동작

Step 1. 배열을 Heap으로 만든다.

부모노드의 Key값은 항상 자식노드의 Key값보다 우선순위가 높다

Step 1-1. 

Step 1-2.

Step 1-3.

Step 2. 첫번째 index와 마지막 index를 swap 후 heap size를 1 줄인다.

Step 2-1.

Step 2-2.

Step 2-3.

Step 2-4.

Step 2-5.

Step 2-6.

코드

public class Sort {
	
    public void heapSort(int[] arr) {
    	int lastIndex = arr.length - 1;
        buildHeap(arr, lastIndex);
        
        for(int i = lastIndex; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i-1);
        }
    }
    
    public void buildHeap(int[] arr, int lastIndex) {
    	int parent = (lastIndex - 1) / 2;
        
        for(int i = parent; i >= 0; i--) {
            heapify(arr, i, lastIndex);
        }
    }
    
    public void heapify(int[] arr, int parentIndex, int lastIndex) {
    	int leftChildIndex = parentIndex * 2 + 1;
        int rightChildIndex = parentIndex * 2 + 2;
        int largestIndex = parentIndex;
        
        if(leftChildIndex > lastIndex) {
        	return;
        }
        
        if(arr[leftChildIndex] > arr[largestIndex]) {
        	largestIndex = leftChildIndex;
        }
        
        if(rightChildIndex < lastIndex && arr[rightChildIndex] > arr[largestIndex]) {
        	largestIndex = rightChildIndex;
        }
        
        if(largestIndex != parentIndex) {
        	swap(arr, largestIndex, parentIndex);
            heapify(arr, largestIndex, lastIndex);
        }
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

왜 $O(nlogn)$일까?

Heap Sort의 의사코드를 보면 다음과 같다.

HeapSort(arr) {

    buildHeap(arr) // O(n)
    
    // O(nlogn)
    for( i = heapLastIndex ~ 0 ) {
        swap(arr, i, heapLastIndex)
        heapify(arr, 0, i - 1)
    }
}

Build Heap이 $O(n)$인 이유

for 구문이 $O(nlogn)$인 이유

Quick Sort

• 특정 원소(pivot)를 기준으로 왼쪽은 lower, 오른쪽은 upper 원소들을 두는 방식
• Merge Sort와 마찬가지로 Divide and Conquer 알고리즘
• 불안정 정렬(unstable sort)
  • 안정 정렬(stable sort): 비교하는 원소의 값이 같을 때 input 순서대로 정렬
• 평균적으로 $O(nlogn)$의 시간복잡도를 가지며, 매 Step마다 적어도 한 개의 원소는 반드시 자기 자리를 찾아가므로 매우 빠름
  • 하지만 최악의 경우에 $O(n^2)$의 시간복잡도를 가짐

  • 

동작

Step 1

Step 2

Step 3

Step 4

코드

public class Sort {
	
    public void quickSort(int[] arr, int first, int last) {
        if(first < last) {
            int pivot = partition(arr, first, last);
            quickSort(arr, first, pivot - 1);
            quickSort(arr, pivot + 1, last);
        }
    }
    
    public int partition(int[] arr, int first, int last) {
    	int pivot = arr[last];
        int i = first - 1;
        
        for(int j = first; j < last; j++) {
            if(arr[j] < pivot) {
            	swap(arr, ++i, j);
            }
        }
        swap(arr, i + 1, pivot);
        
        return i + 1;
    }
    
    public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

왜 최악의 경우에는 $O(n^2$일까?

• 최선의 경우: 매 Step마다 원소가 중앙에 위치되어서 반으로 나누어지는 경우

• 최악의 경우: 매 Step마다 원소가 끝에 위치되어서 1 : 9 로 나누어지는 경우 (이미 정렬된 배열)

그래서 pivot을 선택하는 여러 variation 기법이 존재한다. (Randomized Quick Sort 등..)

Merge Sort

• 원소 개수가 1개 또는 0개가 될 때까지 반으로 나눈뒤 반으로 나눈 원소들을 합쳐가는 과정에서 정렬하는 방식
• 정렬하려는 배열 크기만큼의 추가 배열이 필요함
• $O(nlogn)$으로 $O(n^2)$인 Selection, Insertion, Bubble Sort보다 훨씬 빠름
• Divide And Conquer 알고리즘

• 

동작

Merge가 동작하는 시점?을 하나의 Step으로 본다.

Step 1

Step 2

Step 3

Step 4

Step 5

Step 6

코드

public class Sort {
	
    public void mergeSort(int[] arr, int first, int last) {
    	if(first < last) {
        	int mid = (first + last) / 2;
            mergeSort(arr, first, mid);
            mergeSort(arr, mid + 1, last);
            merge(arr, first, mid, last);
        }
    }
    
    public void merge(int[] arr, int first, int mid, int last) {
    	int i = first;
        int j = mid + 1;
        int k = first;
        int[] copy = new int[arr.length];
        
        while(i <= mid && j <= last) {
        	if(arr[i] > arr[j]) {
            	copy[k++] = arr[j++];
            } else {
            	copy[k++] = arr[i++];
            }
        }
        
        if(i > mid) {
        	for(int l = j; j <= last; j++) {
            	copy[k++] = arr[l];
            }
        } else {
        	for(int l = i; i <= mid; i++) {
            	copy[k++] = arr[l];
            }
        }
        
        for(int l = first; l <= last; l++) {
        	arr[l] = copy[l];
        }
    }
    
}

왜 $O(nlogn)$일까?

Insertion Sort

• k번째 원소를 k-1번째 원소부터 첫번째 원소까지 비교하며 위치를 찾아 끼워넣는 방식
• O(n^2)인 정렬중에 빠른편에 속한다.

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void insertionSort(int[] arr) {
    	for(int i = 1; i < arr.length; i++) {
            int target = arr[i];
            for(int j = i - 1; j >= 0 && arr[j] > target; j--) {
            	arr[j+1] = arr[j];
            }
            arr[j+1] = target;
        }
    }
}

Bubble Sort

• 첫번째와 두번째 원소를 비교하여 정렬, 두번째와 세번째 , ... , n-1번째와 n번째를 정렬한 뒤 다시 처음으로 돌아가 첫번째와 두번째, ... , n-2번째와 n-1번째 ... 이를 반복하는 방식이다.
• Selection Sort와 마찬가지로 O(n^2)이다.

• 

동작

Step1

Step2 부터 j가 이동하면서 swap하지않고 그냥 지나가는 것은 생략한다.

Step2 

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = arr[index1];
    }
    
    public void bubbleSort(int[] arr) {
    	for(int i = arr.length - 1; i >= 0; i--) {
        	for(int j = 0; j < i; j++) {
            	if(arr[j] > arr[j+1]) {
                	swap(arr, j, j+1);
                }
            }
        }
    }
}

Selection Sort

• 처음 index부터 마지막 index까지의 이동하며 최대값을 찾은 후 저장하는 방식
• k-index에 들어갈 원소를 찾기위해서 k-1번 최대값을 찾는 비교를 해야하므로 O(n^2)이다.

• 

동작

Step1

Step2

Step3

Step4

Step5

Step6

코드 (Java)

public class Sort {

	public void swap(int[] arr, int index1, int index2) {
    	int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
	
	public void selectionSort(int[] arr) {
    	for(int i = arr.length-1; i >= 0; i--) {
        	int maxIndex = i;
            int j;
            for(j = 0; j < i; j++) {
            	if(arr[j] > arr[maxIndex]) {
                	maxIndex = j;
                }
            }
            swap(arr, i, maxIndex);
        }
    }
    
    
}

참고1 : 유튜브 (권오흠 교수, 2015 봄학기 알고리즘)

참고2 : (다양한 예제로 학습하는) 데이터 구조와 알고리즘 for java

1. 그래프 : G = (V, E)

1. 정의

• V : 정점(Vertex) 또는 노드(Node)들의 집합
• E : 간선,에지(Edge) 또는 링크(Link)라고 불리는 정점들의 쌍의 집합
• G = (V, E)

2. 종류

• 무방향(undirected) 그래프 vs 방향(directed) 그래프
  • 방향이 없는 그래프 vs 방향이 있는 그래프
  • (u, v) == (v, u) vs (u, v) != (v,u)
  • vs
• 가중치 그래프(Weight Graph)
• 방향, 무방향 그래프에 관계없이 각 간선에 가중치(weight) 혹은 비용(cost)이 할당된 그래프
  • 

3. 용어

• 인접 정점 or 인접 노드 : 간선에 의해 연결된 정점
• 차수(degree) : 정점에 연결된 다른 정점의 개수
  • 진입 차수(in-degree) : 방향 그래프에서 외부 노드에서 들어오는 간선의 수
  • 진출 차수(out-degree) : 방향 그래프에서 외부 노드로 나가는 간선의 수
• 연결 그래프(connected Graph)
  • 무방향 그래프에서 두 노드 사이를 연결하는 경로(path)가 존재할 때 두 정점은 서로 연결되어 있다고 한다.
  • 그래프 안의 모든 정점이 연결되어 있을때 연결된 그래프라고 한다
  • 연결 요소

  • 

2. 그래프의 표현

1. 인접 행렬

• 

  • 두 정점 사이에 간선이 있을경우 1, 없을 경우 0으로 표현한다.
    • 가중치 그래프의 경우 0,1 대신 가중치로 표현한다.
  • 무방향 그래프의 경우 자기 자신을 기준으로 대칭이다. (A, B) == (B, A)
    • 방향 그래프의 경우 비대칭이다.
  • 저장공간 : O(n^2)
  • 어떤 노드 v에 인접한 모든 노드를 찾을 때 걸리는 시간 : O(n)
  • 어떤 간선 (u,v)가 존재하는지 검사할때 걸리는 시간 : O(1)
• 간단한 구현 코드 (무방향 그래프)

public class Graph {
    int[][] adjMatrix;
    int vertexCount;

    public Graph(int count) {
        vertexCount = count;
        adjMatrix = new int[vertexCount][vertexCount];
    }

    public void addEdge(int u, int v) {
        adjMatrix[u][v] = 1;
        adjMatrix[v][u] = 1;
    }

    public void removeEdge(int u, int v) {
        adjMatrix[u][v] = 0;
        adjMatrix[v][u] = 0;
    }

    public List<Integer> findAdjVertex(int u) {
        ArrayList<Integer> adjVertexList = new ArrayList<>();
        for(int i = 0; i<adjMatrix.length; i++) {
            if(adjMatrix[u][i] == 1) {
                adjVertexList.add(i);
            }
        }
        return adjVertexList;
    }

    public boolean isEdge(int u, int v) {
        return adjMatrix[u][v] == 1;
    }
}

2. 인접 리스트

• 

  • 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 리스트
  • 두 정점 사이에 간선이 있을 경우 리스트에 추가한다 (순서는 상관없다)
  • 저장 공간 : O(n+m)
    • n은 정점개수, m은 간선 개수이다.
    • 무방향 그래프의 경우 2m, 방향 그래프의 경우 m이지만, Big - O 표기법에서는 O(n+m)이다.
  • 어떤 노드 v에 인접한 모든 노드를 찾을 때 걸리는 시간 : O(degree(v))
    • v에 해당하는 리스트의 길이이다.
  • 어떤 간선 (u,v)가 존재하는지 검사할 때 걸리는 시간 : O(degree(u))
    • u에 대한 연결 리스트를 돌면서 v가 있는지 확인한다.
• 간단한 구현코드 (무방향 그래프)

public class Graph {
	List<Integer>[] adjList;
    int vertexCount;
    
    public Graph(int count) {
    	vertexCount = count;
        adjList = new List[vertexCount];
        for(int i = 0; i<vertexCount; i++) {
        	adjList[i] = new ArrayList<>();
        }
    }
    
    public addEdge(int u, int v) {
    	adjList[u].add(v);
        adjList[v].add(u);
    }
    
    public removeEdge(int u, int v) {
    	adjList[u].remove(adjList[u].indexOf(v));
        adjList[v].remove(adjList[v].indexOf(u));
    }
    
    public List<Integer> findAdjVertex(int u) {
    	return adjList[u];
    }
    
    public boolean isEdge(int u, int v) {
    	for(int i = 0; i < adjList[u].size(); i++) {
        	if(adjList[u].get(i) == v) {
            	return true;
            }
        }
        return false;
    }

}