[자료구조] 그래프 2 (신장 트리, Kruskal, Prim, Sollin 알고리즘, 그래프 최단경로, AOV 네트워크)

예시 그래프 (a) / 연결리스트 (b)

 

신장 트리(spanning tree)

G의 간선들로만 구성되고 G의 모든 정점들이 포함된 트리

• 신장트리는 G의 최소 부분 그래프(간선의 수가 가장 적은 부분 그래프)
• G'로서 V(G') = V(G)이고 G'는 연결되어 있음
• 신장트리는 n-1개의 간선 가짐

 

최소 비용 신장 트리

• 최저의 비용을 갖는 신장트리
• Kruskal, Prim, Sollin 알고리즘 사용

 

신장 트리의 제한 조건

• 그래프 내에 있는 간선들만을 사용
• 정확하게 n-1개의 간선만을 사용
• 사이클을 생성하는 간선을 사용 금지

 

 

Kruskal 알고리즘

• 한 번에 하니씩 T에 간선을 추가해 가면서 최소비용 신장트리 T를 구축
• T에 포함될 간선을 비용의 크기 순으로 선택
• 이미 T에 포함된 간선들과 함께 사이클을 형성하지 않는 간선만을 T에 추가
• G는 연결되어있고  n>0개의 정점을 가지므로 정확하게 n-1개의 간선만이 T에 포함됨

T = ∅;
while ((T가 n-1개 미만의 간선을 포함) && (E는 공백 아님))
{
    E에서 최소 비용 간선(v, w) 선택;
    E에서 (v, w);
    if ((v, w)가 T에서 사이클을 만들지 않으면)
        T에 (v, w)추가;
    else
        discard(v, w);
}
if (T가 n-1개 미만의 간선을 포함)
    cout << "신장 트리 없음" << endl;

 

Prim 알고리즘

• 한 번에 한 간선씩 최소 비용 신장 트리를 구축
• 각 단계에서 선택된 간선의 집합은 트리
• 하나의 정점으로 된 트리 T에서 시작
• 최소 비용 간선 (u, v)를 구해 T ∪ {(u, v)}이 트리가 되면 T에 추가
• T에 n-1개의 간선이 포함될 때까지 간선의 추가 단계를 반복
• 추가된 간선이 사이클을 형성하지 않도록 각 단계에서 간선 (u, v)를 선택할 때 u 또는 v 중 오직 하나만 T에 속한 것 선택

 

Sollin 알고리즘

• 각 단계에서 여러 개의 간선을 선택
• 간 단계에서는 포트리스에 있는 각 트리에 대해 하나의 간선을 선택
• 이 간선은 오직 하나의 정점만 그 트리에 속한 최소 비용 간선
• 선택된 간선은 구축중인 신장트리에 추가
• 오직 하나의 트리만이 존재 or 더 이상 선택할 간선이 없을 때 종료

 

 

최단경로

그래프와 정점 0에서 모든 종점까지의 최단경로

void MatrixWDigraph::ShortestPath(const int n, const int v)
{ // dist[j], 0<=j<n은 n개의 정점을 가진 방향 그래프 G에서 정점 v로부터 정점 j까지의
  // 최단 경로 길이로 설정됨, 간선의 길이는 length[i][j]로 주어짐
    for (int i = 0; i < n; i++)
    {
        s[i] = false;
        dist[i] = length[v][i];
    } // 초기화
    s[v] = true;
    dist[v] = 0;

    for (i = 0; i < n - 2; i++)
    {                      // 정점 v로부터 n-1개 경로를 결정
        int u = Choose(n); // choose는 s[w]=false 이고
                           // dist[u] = minimum dist[w]가 되는 u를 반환
        s[u] = true;
        for (int w = 0; w < n; w++)
            if (!s[w] && dist[u] + length[u][w] < dist[w])
                dist[w] = dist[u] + length[u][w];
    } // for(i=0;...)의 끝
}

 

시간복잡도 - O(\(n^{2}\))

 

예시

예시

방향 그래프에 대한 ShortestPath의 작동

반복 횟수	선택된 정점의 개수	거리
		LA	SF	DEN	CHI	BOST	NY	MIA	NO
		[0]	[1]	[2]	[3]	[4]	[5]	[6]	[7]
초기	-	∞	∞	∞	1250	0	250	∞	∞
1	5	∞	∞	∞	1250	0	250	1150	1650
2	6	∞	∞	∞	1250	0	250	1150	1650
3	3	∞	∞	2450	2150	0	250	1150	1650
4	7	3350	∞	2450	1250	0	250	1150	1650
5	2	3350	3250	2450	1250	0	250	1150	1650
6	1	3350	3250	2450	1250	0	250	1150	1650

 

 

작업 네트워크(Activity On Vertex)

정점이 작업을, 간선이 작업 간의 선행 관계를 나타내는 방향그래프 G

 

예시

 

정의

• 정점 i로부터 정점 j로의 방향 경로 존재 -> 정점 i는 정점 j의 선행자(predecessor)
• 간선 <i, j>가 존재 -> 정점 i는 정점 j의 직속 선행자(immediate predecessor)
• i가 j의 선행자 -> j는 i의 후속자(successor)
• i가 j의 직속 선행자 -> j는 i의 직속 후속자(immediate successor)
• 위상순서(topologocal): 임의의 두 정점 i, j에 대해 네트워크에서 i가 j의 선행자이면 선형순서에서도 i가 j앞에 있는 그래프 정점의 선형순서

 

위상순서 구현

void LinkedDigraph::TopologicalOrder()
{ // 네트워크의 n개 정점을 위상순서로 나열
    int top = -1;
    for (int i = 0; i < n; i++) // 선행자가 없는 정점들을 연결 스택으로 생성
        if (count[i] == 0)
        {
            count[i] = top;
            top = i;
        } // no predecessors

    for (i = 0; i < n; i++)
        if (top == -1)
            throw " Network has a cycle.";
    int j = top;
    top = count[top]; // 정점 하나를 스택에서 꺼냄
    cout << j << endl;
    Chain<int>::ChainIterator ji = adjLists[j].begin();
    while (ji)
    { // j의 후속자 정점의 계수 감소시킴
        count[*ji]--;
        if (count[*ji] == 0)
        {
            count[*ji] = top;
            top = *ji;
        } // *ji를 스택에 삽입
        ji++;
    }
}

 

예시

위상순서: 0, 3, 2, 5, 1, 4

위상 정렬 알고리즘에 의해 사용되는 내부 표현