[알고리즘](C언어) 그래프 알고리즘

1. 그래프 ADT

그래프 ADT

그래프(graph): G = (V,E) 혹은 G(V,E)로 표시

• V: 정점(vertex)이라 불리는 노드의 집합
• E: 간선(edge)이라 불리는 정점쌍들의 집합
• 정점과 간선은 원소, 즉 정보를 저장

• 예
  • 아래 예에서 정점은 공항을 표현하며 공항도시 이름을 저장
  • 간선은 두 공항 사이의 항로를 표현하며 항로의 거리(mile)를 저장

간선에 따른 그래프 유형

방향간선(directed edge)

• 정점들의 순서쌍 <u,v>
  • u: 시점(origin)
  • v: 종점(destination)
  • ex: 항공편(flight)
• 방향그래프(directed graph)
  • 모든 간선이 방향간선인 그래프
  • n개의 정점으로 구성된 방향 그래프에서 간선이 최대일 경우는 모든 정점이 연결되어 n(n-1)개가 될 때이다.
  • ex: 항공편망(flight network)

무방향간선(undirected edge)

• 정점들의 무순쌍 (u,v)
  • ex. 항로
• 무방향그래프(undirected graph)
  • 무방향간선으로 이루어진 그래프
  • n개의 정점으로 구성된 무방향 그래프에서 간선이 최대일 경우는 모든 정점이 연결되어 n(n-1)/2개가 될 때이다.
  • ex. 항로망(flight route network)

그래프 응용

• 전자회로
  • 인쇄회로기판(printed circuit board, PCB)
  • 집적회로(integrated circuit, IC)
• 교통망
  • 고속도로망
  • 항공노선망
• 컴퓨터 네트워크
  • LAN(local area network)
  • 인터넷
  • 웹
• 데이터베이스
  • 개체-관계 다이어그램(entity-relationship diagram)

2. 그래프 주요 개념

그래프 용어

• 간선의 끝점(end vertex, endpoint)
  • 정점 U와 V는 a의 양끝점
• 정점의 부착(incident) 간선
  • a, d, b는 V에 부착한다.
• 정점의 인접(adjacent) 정점
  • U와 V는 인접하다
• 정점의 차수(degree)
  • 정점에 부속되어 있는 간선의 수
  • 방향 그래프의 정점의 차수 = 진입 차수(in-degree) + 진출 차수(out-degree)
    • 진입 차수: 정점으로 들어오는 간선의 수
    • 진출 차수: 정점에서 나가는 간선의 수
  • X의 차수는 5다
• 병렬 간선(parallel edges)
  • h와 i는 병렬 간선
• 루프(loop, self-loop)
  • j는 루프다

• 경로(path)
  • 정점과 간선의 교대열
  • 그래프에서 간선을 따라 갈 수 있는 길을 순서대로 나열한 것
  • 정점으로 시작하여 정점으로 끝난다
  • 각 간선은 그 양끝점으로 시작하고 끝난다
• 단순경로(simple path)
  • 모든 정점과 간선이 유일한 경로
  • 모두 다른 정점으로 구성된 경로
• 예
  • P1 = (V,b,X,h,Z)은 단순경로
  • P2 = (U,c,W,e,X,g,Y,f,W,d,V)는 비단순경로

• 싸이클(cycle)
  • 정점과 간선이 교대하는 원형열
  • 각 간선은 그 양끝점으로 시작하고 끝난다(경로의 시작 정점과 마지막 정점이 같은 경로)
• 단순싸이클(simple cycle)
  • 모든 정점과 간선이 유일한 싸이클
• 예
  • C1 = (V,b,X,g,Y,f,W,c,U,a)는 단순싸이클
  • C2 = (U,c,W,e,X,g,Y,f,W,d,V,a)는 비단순싸이클
• DAG(directed acyclic graph)
  • 방향 그래프면서 사이클이 없는 그래프

그래프 속성

표기

• n: 정점 수
• m: 간선 수
• deg(v): 정점 v의 차수

속성 1

• 증명: 각 간선이 두 번 세어진다

속성2

루프와 병렬 간선이 없는 무방향그래프에서, m <= n(n-1)/2

• 증명: 각 정점의 최대 차수는 (n-1)

완전 그래프(complete graph)

• 각 정점에서 다른 모든 정점을 연결하여 최대로 많은 간선 수를 가진 그래프
• 정점이 n개인 방향/무방향 그래프에서 최대의 간선 수
  • 방향: n(n-1)개
  • 무방향: n(n-1)/2개

부(분)그래프 - 부: 부분집합(subgraph)

• 그래프 G = (V,E)의 부그래프(subgraph): 다음 정점과 간선으로 구성된 그래프
  • 정점: V의 부분집합
  • 간선: E의 부분집합
• 원래의 그래프에서 정점이나 간선을 일부만 제외해서 만든 그래프
• 아래의 그림에서 G1'들은 각각 G1의 부그래프

ㅇ

• 그래프 G = (V,E)의 신장 부그래프(spanning subgraph): 다음 정점과 간선으로 구성된 그래프
  • 정점: V - 모든 정점을 취함
  • 간선: E의 부분집합

연결성

 

• 모든 정점쌍에 대해 경로가 존재하면 "그래프가 연결(connected)되었다"고 하며 연결 그래프(connected graph)이다.
  • 떨어져있는 정점이 없는 그래프
• 강한 연결 그래프(strongly connected graph)
  • 연결 그래프 G의 임의의 서로 다른 두 정점 V, W에 대해서 직접 경로(direct path)인 (V,W)와 (W,V)가 함께 존재
• 그래프 G의 연결요소(connected component): G의 최대 연결 부그래프

밀집도(<-> 희소)

• 그래프 알고리즘의 선택은 종종 간선의 밀집도에 따라 좌우된다
• 예
  • 주어진 알고리즘 G에 대해, 알고리즘 A와 B가 동일한 문제를 각각 O(nm) 시간과 O(n^2) 시간에 해결할 경우,
    • G가 희소하다면, 알고리즘 A가 B보다 빠르다
    • G가 밀집하다면, 알고리즘 B가 A보다 빠르다

싸이클

• 자유트리(free tree), 또는 트리: 다음 조건을 만족하는 무방향그래프 T
  • T는 연결됨
  • T에 싸이클이 존재하지 않음
    • 위 트리에 대한 정의는 루트가 있는 트리에 대한 정의와는 다르다)
    • root가 없다는 의미에서 free라고 한다.
• 숲(forest): 싸이클이 없는 무방향그래프
  • 숲의 연결요소는 트리들이다
  • 자유트리가 두 개 모이면 숲이 된다.

신장

• 연결그래프의 신장트리(spanning tree): 신장 부그래프 가운데 트리인 것
  • 신장: 모든 정점을 커버할 수 있음
  • 트리: 싸이클이 없는 것
• 신장트리는 그래프가 트리가 아닌 한, 유일하지 않다.
• 신장트리는 통신망 설계에 응용된다
• 그래프의 신장숲(spanning forest): 신장 부그래프 가운데 숲인 것 

3. 그래프 ADT 메쏘드

3-1. 방향/무방향 그래프에서 공통으로 사용하는 메쏘드 

• 정점과 간선들은 원소를 저장

1) 일반 메쏘드

integer numVertices()

• 그래프 내 모든 정점의 개수를 return

integer numEdges()

• 총 간선 수 return

iterator vertices()

• 모든 정점을 return

iterator edges()

• 모든 간선을 return

2) 접근 메쏘드

vertex aVertex()

• any: 아무
• 아무 정점을 return
• 그냥 맨 앞에 있는 정점 반환하면 됨

3) 질의 메쏘드

boolean isDirected(e)

• 이 간선이 방향 간선이냐 아니냐

4) 반복 메쏘드

iterator directedEdges()

• 모든 방향 간선 return

iterator unDirectedEdges()

• 모든 무방향 간선 return

5) 갱신 메쏘드

vertex insertVertex(o)

• 새로운 정점을 추가
• o: object
• 정점을 추가됐으므로 간선도 같이 추가되어야 함

removeVertex(v)

• 정점을 제거

removeEdge(e)

• 간선을 제거

3-2. 무방향그래프에서만 가능한 ADT 메쏘드

1) 접근 메쏘드

integer deg(v)

• 그래프의 차수 반환

vertex opposite(v, e)

• v의 반대쪽 정점 return

2) 질의 메쏘드

boolean areAdjacent(v, w)

• v와 w가 인접한지 아닌지

3) 반복 메쏘드

iterator endVertices(e)

• e의 양 끝 점을 return

iterator adjacentVertices(v)

• v에 인접한 정점들 return

iterator incidentEdges(v)

• v에 부착되어 있는 간선들 return

4) 갱신 메쏘드

edge insertEdge(v, w, o)

• 정점 v에서 w로 항목 o를 저장한 무방향간선을 삽입하고 반환

3-3. 방향그래프에서만 가능한 ADT 메쏘드

1) 접근 메쏘드

vertex origin(e)

• e의 출발점을 return 

vertex destination(e)

• e의 목적지(도착점) return

integer inDegree(v)

• v로 들어오는 간선 개수 return

integer outDegree(v)

• v에서 나가는 간선 개수 return

2) 반복 메쏘드

iterator inIncidentEges(v)

• v로 들어오는 진입 부착 간선 return

iterator outIncidentEdges(v)

• v에서 나가는 진출 부착 간선 return

iterator inAdjacentVertices(v)

• v로 들어오는 진입 부착 정점 return

iterator outAdjacentVertices(v)

• v에서 나가는 진출 부착 정점 return

3) 갱신 메쏘드

edge insertDirectedEdge(v, w, o)

• 정점 v에서 w로 항목 o를 저장한 방향간선을 삽입하고 반환

makeUndirected(e)

• 간선 e를 무방향으로 전환

reverseDirection(e)

• 방향간선 e를 역행

4. 그래프 표현

그래프는 세 가지 구조를 사용해서 구현할 수 있다.

1. 간선리스트(edge list) 구조
2. 인접리스트(adjacency list) 구조
3. 인접행렬(adjacency matrix) 구조

위의 세 가지 방식으로 구현이 가능하다.

 

간선리스트 구조는 간단하지만 너무 간단해서 한계가 있다. 따라서 여기서 좀 더 발전한 인접리스트를 사용하거나 좀 더 발전시킨 인접행렬을 사용한다. 주로 사용하는 것은 인접리스트 구조와 인접행렬 구조이다.

 

4-1. 간선리스트 구조

• 정점리스트
  • 정점 노드들에 대한 포인터의 리스트
• 간선리스트
  • 간선 노드들에 대한 포인터의 리스트
• 정점 노드
  • 원소
• 간선 노드
  • 원소
  • 시점 노드
  • 종점 노드

 

아래의 인접리스트 구조와 인접행렬 구조는 동일하게 부착된 간선들에 대한 정보들을 제공하며 리스트로 제공하냐 행렬로 제공하냐의 차이다.

 

4-2. 인접리스트 구조

• 간선리스트 구조 + 부착리스트
• 각 정점에 대한 부착리스트 
  
  • 각 정점의 부착간선들을 간선 노드에 대한  참조들의 리스트로 표시
• 간선리스트보다 직접적으로 표현되어 있으므로 더욱 편리함 

4-3. 인접행렬 구조

• 간접리스트 구조 + 인접행렬
• 정점 개체에 대한 확장
  • 정점에 해당하는 정수 키(첨자)

• 인접행렬(adjacency matrix)
  • n개의 정점에 대해 n x n 배열
    • 무방향 그래프의 경우 대칭행렬임
  • 인접정점 쌍에 대응하는 간선 노드들에 대한 참조
  • 비인접정점 쌍에 대한 NULL 정보
• "구식 버전"은 간선의 존재여부만을 1(간선 존재)과 0(간선 부존재)으로 표시함

• 방향 그래프의 인접행렬
  • 행 i의 합 = 정점 i의 진출 차수
  • 열 i의 합 = 정점 i의 진입 차수
• 무방향 그래프의 인접행렬
  • 행 i의 합 = 열 i의 합 = 정점 i의 차수

연결리스트를 이용한 구현

배열을 이용한 구현

그래프 구현 비교

점근 성능 비교

 

5. 구현

다음의 문제 1과 문제 2는 주어진 그래프를 인접 리스트 및 인접 행렬로 각각 표현하여 해결해야

한다. 다음은 두 문제 모두에 공통된 사항이다.

1) 그림 1의 그래프에 관해 해결해야 한다.

2) 가중치의 값은 양수와 음수 모두 가능하나, 0은 허용하지 않는다.

3) 그림 1 그래프의 정점 개수는 변경되지 않는다. 단, 간선 개수는 변화할 수 있다. 참고로 정점 6개인 그래프에서 가능한 간선 개수는, 자기 자신으로 가는 간선(즉, 루프)을 포함하여 최대 21(= 6 + 5 + 4 + 3 + 2 + 1)개다.

4) 간선의 이름을 생략하기로 한다. 따라서 간선 구조체의 이름 필드는 정의하지 않아도 된다.

5) 그래프를 배열 또는 연결 리스트 가운데 어느 것을 이용하여 구현 할지는 각자의 판단에 맡긴다.

문제 1: 무방향 가중그래프에 대한 인접리스트 구현

그림 1의 무방향 가중그래프를 인접리스트로 표현하고, 다음 명령어에 따라 그래프 정보를 출력하거나 그래플르 수정하는 프로그램을 작성하시오.

 

대화식 프로그램에 주어지는 명령어는 a, m, q 세 가지며 각 명령에 대해 다음과 같이 수행해야 한다.

a <node number>

<node number>를 가지는 node와 인접한 node와 그 노드까지의 간선 가중치를 모두 인쇄. 단, node number의 오름차순으로 인쇄하되, space 외의 구분자 없이 노드번호 가중치 노드번호 가중치 ... 형식으로 인쇄한다. 그래프에 정점 a가 존재하지 않으면 아무 것도 하지 않고 –1을 출력한다.

m a b w

간선 (a, b)의 가중치를 w로 변경한다. 그러한 간선이 존재하지 않을 때는 가중치 w인 새로운 간선 (a, b)를 생성한다. w = 0이면 간선 (a, b)를 삭제한다. 그래프에 정점 a 혹은 b가 존재하지 않으면 아무 것도 하지 않고 –1을 출력한다.

q

프로그램 종료