알고리즘 - 그래프 심화(2)

이상해씨·2022년 8월 27일
0

웹 풀스택(JAVA)

목록 보기
31/54

✔ 최단 경로 알고리즘

  • 최단 경로 : 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로.
    • 가중치가 없다면 BFS로 구현 가능.
  • 하나의 시작 정점에서 끝 정점까지의 최단 경로
    • 다익스트라(dijkstra) 알고리즘 : 음의 가중치를 허용하지 않음.
    • 벨만-포드(Bellman-Ford) 알고리즘 : 음의 가중치 허용
  • 모든 정점들에 대한 최단 경로
    • 플로이드-워샬(Floyd-Warshall) 알고리즘 : DP(Dynamic programming, 동적 계획법)

✔ 다익스트라(Dijkstra) 알고리즘

  • 시장 정점에서 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
    • 시작 정점에서 거리가 최소인 정점을 선택해 나가면서 최단 경로 계산.
    • 그리디 알고리즘 이용 : MST의 Prim과 유사.
    • 기본 시간 복잡도 : O(V2)
    • 우선순위 큐 시간 복잡도 : O((V+E)logV)
// s : 시작 정점, A : 인접 행렬, D : 시작 정점에서의 거리
// V : 정점 집합, U : 선택된 정점 집합.
// 기본 코드.
Dijkstra(s, A, D){
	U = {s};
    
    for (Vertex v : V){
    	D[v] = A[s][v];
    }
    
    while (U != V){
    	// 처리되지 않은 정점 중 [출발지 -> 정점] 비용이 최소인 정점 찾기.
    	D[w]가 최소인 정점 w (U에 포함되지 않은 정점).
        // 선택된 정점 집합에 추가.
        Union(U, {w});
        // 추가된 정점의 인접 정점 탐색.
        for (Vertex v : w 인접 미방문 정점){
        	D[v] = min(D[v], D[w] + A[w][v]);
        }
    }
}

✔ 위상 정렬(Topology Sort)

  • 유향 그래프의 정점들을 변의 방향을 거스르지 않도록 나열하는 것.
    • 순서가 정해져 있는 작업들을 차례로 수행해야 할 때, 순서 결정.
    • 유향 그래프의 구조에 따라 여러 개의 종류가 존재할 수 있음.
    • 그래프 순환(Cycle)가 존재하지 않아야 함. : 비순환 유향 그래프(Directed Acyclic Graph)
    • 예시) 선수과목(Prerequisite)

◾ 사용 예시

  • 위상 정렬이 가능한지 여부 : 사이클 발생 여부 확인 가능.
  • 위상 정렬한 결과

◾ 위상 정렬 구현

  • BFS 이용 : 이해하기 더 쉬운 방식.
  • DFS 이용

1. 위상 정렬 구현 : BFS

  1. 진입 차수가 0인 노드(시작점) 큐에 추가.
  2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 인접한 노드의 간선 제거.
    => 인접한 노드의 진입 차수 1 감소.
  3. 간선 제거 후 진입 차수가 0이 된 노드 큐에 추가.
  4. [2, 3] 과정 반복.
  • 모든 노드가 처리되었다면 위상 정렬 완성. 처리되지 않았다면 사이클 발생.
// V : 정점 집합.
// V_n : 정점의 수.
// inDegree : 진입 차수의 수.
// A : 인접 행렬.

void TopologySort(V, V_n, inDegree, A){
	Deque deque;
    // 진입 차수가 0인 정점 추가.
    for(Vertex v : V){
    	if(inDegree[v] == 0) deque.offerLast(v);
    }
	
    // 덱이 빌 때까지 반복.
    int count = 0;	// 선택된 정점의 수.
    while(!deque.isEmpty()){
    	// 진입 차수가 0인 정점 반환.
    	Vertex cur = deque.pollFirst();
        
        // 출력.
        count++;
        print(cur)
        
        // 인접 행렬 탐색.
        for(Vertex v : A[cur]){
        	// 간선 제거(진입 차수 감소)
        	inDegree[v]--;
            // 진입 차수가 0인 경우 덱에 추가.
            if(inDegree[v] == 0) deque.offerLast(v):
        }
    }
    
    // 정점이 모두 선택되었다면 위상 정렬.
    if(count == V_n){
    	print("위상 정렬");
    }
}
profile
후라이드 치킨

0개의 댓글