내용

• 그래프 개요
• 순회 (DFS, BFS)
• 방향그래프 (강연결, 이행적폐쇄, 플로이드 워셜, DP, DAG, 위상정렬)
• 최소신장트리
• 최단거리

그래프 개요

그게뭔데

정점(Vertex)의 집합 V, 간선(Edge)의 집합 E가 있을 때
(V, E)쌍을 그래프(Graph)라고 한다.

위키백과

유형

• 간선
  • 무방향(무향) 간선 : 정점들의 순서 없는 쌍 --> (u,v)와 (v,u)는 같음
  • 방향(유향) 간선 : 정점들의 시점/종점 순서쌍 --> (u,v)와 (v,u)는 다름
• 그래프
  • 무방향 그래프 : 무방향 간선으로 정점이 연결된 그래프
  • 방향 그래프 : 방향 간선으로만 정점이 연결된 그래프

용어

• 끝점 : 어떤 간선의 양쪽 정점
• 부착(incident) 간선 : 어떤 정점에 붙어있는 간선
• 인접(adjacent) 정점 : 어떤 정점의 부착 간선 건너에 있는 정점
• 차수(degree) : 어떤 정점의 부착 간선의 개수
• 병렬 간선 : 두 정점 사이에 여러 간선이 존재할 때, 그 간선들의 관계는 병렬 간선
• 루프 : 순서쌍 (v,u)에서 v=u인 간선

• 경로(path) : 정점에서 정점으로 가는 길. 정점과 간선의 교대열.
  (e.g.,) A x B y C --> A에서 C로 가는 길
  • 단순 경로 : 정점, 간선이 한 번씩 나타남
  • 비단순 경로 : 두 번 이상 나타남
• 싸이클(cycle) : 돌고 돌아서 시작정점으로 오는 경로
  (e.g.,) A j B k --> A정점에서 출발해 돌고돌아 A로 가는 길
  • 단순 싸이클 : 각 정점, 간선이 한 번씩만 나타나는 싸이클
  • 비단순 싸이클 : 두 번 이상 나타남

┌---(j)---┐
A --(x)-- B --(y)-- C --(z)--┐
└---(k)---┘         |        |
                    └--------┘

간선 x의 끝점 : A, B
정점 A의 부착간선 : j, x, k (얘들은 서로 병렬간선)
정점 A의 인접정점 : B
정점 A의 차수 : 3
정점 C는 루프가 있음 : 간선 z

경로 예시 : A x B y C
사이클 예시 : A j B x

그래프 속성

(약속)
정점 개수 n
간선 개수 m
정점v의 차수 deg(v)

• $\sum_{v}{deg(v)} = 2m$
• 루프, 병렬 간선이 없을 때
  • 무방향 그래프이면 $m \leq n(n-1)/2$
  • 방향 그래프이면 $m \leq n(n-1)$

그래프 메소드

• 일반
  • int numVertices() : 정점 개수
  • int numEdges() : 간선 개수
  • iterator vertices() : 정점 목록
  • iterator edges() : 간선 목록
  • iterator directedEdges() : 방향간선 목록
  • iterator unDirectedEdges() : 무방향간선 목록
  • bool isDirected(e) : 방향간선이냐?
  • vertex aVertex() : 임의 1개 정점 리턴
  • vertex insertVertex(o) : 그래프에 항목 o의 정점 삽입
  • void removeVertex(v) : 정점 삭제
  • void removeEdges(e) : 간선 삭제
• 무방향 그래프
  • int deg(v)
  • vertex opposite(v, e)
  • bool areAdjacent(v, w)
  • iterator endVertices(e)
  • iterator adjacentVertices(v)
  • iterator incidentEdges(v)
  • edge insertEdge(v, w, o) : 정점 v, w사이에 내용 o의 간선 넣기
• 방향 그래프
  • vertex origin(e) : 시점 정점
  • vertex destination(e) : 종점 정점
  • int inDeg(v)
  • int outDeg(v)
  • iterator inIncidentEdges(v)
  • iterator outIncidentEdges(v)
  • iterator inAdjacentVertices(v)
  • iterator outAdjacentVertices(v)
  • edge insertDirectedEdge(v, w, o)
  • makeUndirected(e) : 무방향간선으로
  • reverseDirection(e) : 방향 반대로

그래프의 세부 분류

밀집도를 기준으로

• 희소 그래프 : 간선이 비교적 적은 그래프
• 밀집 그래프 : 간선이 비교적 많은 그래프

연결성을 기준으로 $_{연결\ 안되고\ 따로떨어진\ 덩어리\ 각각을\ `연결요소`라\ 한다.}$

• 연결 그래프 : 모든 정점이 연결된 그래프 (연결 요소가 한 개)
• 비연결 그래프 : 여러 연결 요소로 구성된 그래프

싸이클이 있는 경우 연결성을 기준으로

• 자유트리(트리) : 싸이클이 없는 연결 무방향 그래프
• 숲 : 싸이클이 없는 무방향 그래프

그래프 G=(V,E)에 대해

• 부그래프 : V의 부분집합, E의 부분집합을 갖는 그래프
• 신장 부그래프 : V는 전부 갖고, E의 부분집합을 갖는 그래프
• 신장 트리 : 신장 부그래프 가운데 트리인 것
• 신장 숲 : 신장 부그래프 가운데 숲인 것

그래프 구현

그래프의 대표적인 구현 방법으로 아래 세 가지가 있다.

• 간선리스트 구조 : 정점 리스트와 간선 리스트 유지.
• 간선리스트 구조의 확장
  • 인접리스트 구조 : 정점별로 부착된 간선 리스트 유지
  • 인접행렬 구조 : n개 정점에 대해 인접 여부를 표시한 nXn 배열 유지

각 구현방법별 성능

항목	간선리스트	인접리스트	인접행렬
공간	O(n+m)	O(n+m)	O(n^2)
incidentEdges	O(m)	O(deg(v))	O(n)
adjacentVertices	O(m)	O(deg(v))	O(n)
areAdjacent	O(m)	O(min(deg(v), deg(w))	O(1)
insertVertex	O(1)	O(1)	O(n)
insertEdge	O(1)	O(1)	O(1)
removeVertex	O(m)	O(deg(v))	O(n)
removeEdge	O(1)	O(1)	O(1)

연결리스트를 사용한 표현

인접리스트 구조의 정점,간선 리스트는 아래와 같이 표현할 수 있다.

typedef struct _Edge {
  struct _Vertex* a;
  struct _Vertex* b;
  int w; // weight
  struct _Edge* next;
} Edge;

typedef struct _IncidentEdge {
  struct _Edge* edge; // Edge node
  struct _IncidentEdge* next;
} IncidentEdge;

typedef struct _Vertex {
  struct _IncidentEdge* incidentEdges;
  int n; // node number 
  struct _Vertex* next;
} Vertex;

Vertex* VERTICES = getVertexNode(); // header node
Edge* EDGES = getEdgeNode(); // header node

인접행렬 구조의 정점, 간선 리스트와 인접행렬은 아래와 같이 표현할 수 있다.

typedef struct _Edge {
  struct _Vertex* a;
  struct _Vertex* b;
  int w; // weight
  struct _Edge* next;
} Edge;

typedef struct _Vertex {
  int adjID; // 인접행렬 매트릭스에서 사용할 해당 정점의 ID
  int n; // node number 
  struct _Vertex* next;
} Vertex;

Vertex* VERTICES = getVertexNode(); // 정점 리스트
Edge* EDGES = getEdgeNode(); // 간선 리스트
Edge* ADJS[VERTICES_NUM][VERTICES_NUM] = { NULL }; // 부착간선 매트릭스 

배열을 사용한 표현

그냥 연결리스트로 만들었던 것들을 다 배열에다가 박아넣으면 된다.
Vertex* 노드는 Vertex형 구조체 배열의 원소가 되고...
Vertex** 노드는 Vertex*형 구조체 배열의 원소가 되고...

(딱히 특별한게 없음)

문제점으로 가변 그래프에 대응하기가 귀찮다는 점을 들 수 있다.

그래프 순회

모든 정점, 간선을 검사하는 절차
인접리스트로 구현하면 O(n+m)
인접행렬로 구현하면 O(n^2)이다.

DFS와 BFS모두 신장숲, 연결요소, 경로, 싸이클여부를 구할 수 있다.
최단경로는 BFS로, 이중 연결요소는 DFS로 구할 수 있다.

깊이우선탐색(DFS)

이진트리의 Pre-order순회와 유사.

순회 하다가 출발 정점으로 되돌하가기 위해 재귀 스택을 사용한다. 이는 재귀 호출로 자연히 구현된다.

각 정점과 간선은 상태를 갖는다.

• 정점
  • Fresh : 초기상태 (방문 이전)
  • Visited : 이미 방문한 상태
• 간선
  • Fresh : 초기상태 (방문 이전)
  • Tree (트리간선) : 방문된 간선. 트리를 만드는 방향.
  • Back (후향간선) : 방문된 간선. 직계조상 방향.

DFS의 속성은 다음과 같다.

• DFS(G, v)는 어떤 정점 v가 포함된 연결요소의 모든 정점, 간선을 방문
• 트리 간선(Tree로 라벨링 된 간선)들은 v가 포함된 연결요소의 신장트리를 이룬다.
  • 트리 간선을 따라가면 신장트리를 만들 수 있다.

의사코드로 표현한 알고리즘은 다음과 같다.

Alg driver(G)
1. for each v ∈ G.vertices()
     v.label ← Fresh
   for each e ∈ G.edges()
     e.label ← Fresh
2. for each v ∈ G.vertices()
     if(v.label = Fresh)
       DFS(G, v)
       
Alg DFS(G, v)
1. v.label ← Visited
2. for each e ∈ G.incidentEdges(v)
     if(e.label = Fresh)
       w ← G.opposite(v, e)
       if(w.label = Fresh)
         e.label ← Tree
         DFS(G, w)
       else
         e.label ← Back

아래와 같이 C로 구현할 수 있다. (그래프는 인접리스트로 구현함)

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

// 간선, 부착간선, 정점 노드 정의.
typedef struct _Edge {
  struct _Vertex* a;
  struct _Vertex* b;
  int label; // 0:Fresh, 2:Tree, 3:Back
  struct _Edge* next;
} Edge;

typedef struct _IncidentEdge {
  struct _Edge* edge; // Edge node
  struct _IncidentEdge* next;
} IncidentEdge;

typedef struct _Vertex {
  struct _IncidentEdge* incidentEdges;
  int n; // node number
  int label; // 0:Fresh, 1:Visited
  struct _Vertex* next;
} Vertex;

// 함수 원형 정의
Edge* getEdgeNode();
IncidentEdge* getIncidentEdgeNode();
Vertex* getVertexNode();

Vertex* findVertexNodeByNodenumber(int n);
Edge* insertEdge(Vertex* va, Vertex* vb);
IncidentEdge* insertIncidentEdge(Vertex* v, Edge* edge);
Vertex* insertVertex(int a);
Vertex* oppositeVertex(Vertex* v, Edge* e);

void DFS();
void rDFS(Vertex* v);

// -----------------

Vertex* VERTICES = NULL; // header node
Edge* EDGES = NULL; // header node

int main(){
  VERTICES = getVertexNode(); // header node
  EDGES = getEdgeNode(); // header node

  int n, m, s;
  scanf("%d%d%d", &n, &m, &s); getchar();

  int a, b;
  Vertex *va, *vb;
  for(int i=0; i<m; i++){
    va = NULL; vb = NULL;
    scanf("%d%d", &a, &b); getchar();

    // 입력받은 정점 번호에 대한 정점이 있으면 생성
    va = findVertexNodeByNodenumber(a);
    vb = findVertexNodeByNodenumber(b);
    if(va == NULL) va = insertVertex(a);
    if(vb == NULL) vb = insertVertex(b);

    insertEdge(va, vb);
    }
  
  DFS(s);
  
  return 0;
}

// --------------------------
//   새로운 노드를 할당하는 함수

Edge* getEdgeNode() {
  Edge* p = (Edge*)malloc(sizeof(Edge));
  p -> a = NULL;
  p -> b = NULL;
  p -> next = NULL;
  return p;
}

IncidentEdge* getIncidentEdgeNode() {
  IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge));
  p -> edge = NULL;
  p -> next = NULL;
  return p;
}

Vertex* getVertexNode() {
  Vertex* p = (Vertex*)malloc(sizeof(Vertex));
  p -> incidentEdges = getIncidentEdgeNode();
  p -> next = NULL;
  return p;
}

// --------------------------
//    기타 함수

void DFS(int s) { // s : 순회 시작 정점 번호
  // 초기화
  Vertex* u = VERTICES -> next;
  while(u != NULL){
    u -> label = 0; // Fresh
    u = u -> next;
  }
  
  Edge* e = EDGES -> next;
  while(e != NULL) {
    e -> label = 0; // Fresh
    e = e -> next;
  }

  // 정점번호가 s인 노드 - 첫 번째 노드 스왑. 
  Vertex* vs = findVertexNodeByNodenumber(s); // s번 정점
  Vertex* vsPrev = VERTICES -> next;
  while(vsPrev -> next != vs)
    vsPrev = vsPrev -> next;

  vsPrev -> next = vs -> next;
  vs -> next = VERTICES -> next;
  VERTICES -> next = vs;
  
  // 순회 시작
  u = VERTICES -> next;
  while(u != NULL) {
    if(u -> label == 0) // 정점 u가 Fresh이면
      rDFS(u);
    // TEST_printIncidentEdges(u);
    u = u -> next;
  }
}

void rDFS(Vertex* v) {
  v -> label = 1; // Visited
  printf("%d\n", v->n);
  
  IncidentEdge* ie = (v -> incidentEdges)->next;
  Edge* e = NULL;
  Vertex* w = NULL;
  
  while(ie != NULL) {
    e = ie -> edge;
    if(e -> label == 0) { // Fresh
      w = oppositeVertex(v, e);
      if(w -> label == 0) { // Fresh
        e -> label = 2; // Tree
        rDFS(w);
      }
      else {
        e -> label = 3; // Back
      }
    }

    ie = ie -> next;
  }
}

Vertex* insertVertex(int a){
  // 입력 : 노드 번호 a
  
  Vertex* newVtx = getVertexNode();
  newVtx -> n = a;

  newVtx -> next = VERTICES -> next;
  VERTICES -> next = newVtx;
  
  return newVtx;
}

IncidentEdge* insertIncidentEdge(Vertex* v, Edge* edge) {
  // 어떤 정점의 indidentEdge 연결리스트에 새로운 간선 추가. (반대편 노드 오름차순 순서에 맞게 추가)
  // 입력 : 추가대상 정점 v, 추가할 간선 edge
  
  IncidentEdge* newie = getIncidentEdgeNode();
  newie -> edge = edge;

  // 새로운 incedentEdge(newie)를 삽입할 위치를 찾는다.
  // while문이 끝난 뒤 q 노드, p 노드 사이에 삽입한다.
  IncidentEdge* p = (v -> incidentEdges) -> next;
  IncidentEdge* q = NULL; // p의 직전 노드
  Vertex* newieOppositeVtx = oppositeVertex(v, edge);
  int newieOppositeVtxNum = newieOppositeVtx -> n;
  Vertex* existOppositeVtx = NULL;
  int existOppositeVtxNum = 0;
  
  while(p != NULL){
    existOppositeVtx = oppositeVertex(v, p->edge);
    existOppositeVtxNum = existOppositeVtx -> n;
    if (existOppositeVtxNum > newieOppositeVtxNum)
      break;
    
    q = p;
    p = p -> next;
  }
  
  if(q == NULL) // 만약 v -> incidentEdges가 비었으면(헤더밖에 없으면)
    q = v -> incidentEdges;

  // 삽입
  newie -> next = q -> next;
  q -> next = newie;

  return newie;
}

Edge* insertEdge(Vertex* va, Vertex* vb) {
  // 입력 : 정점노드 a, b
  Edge* newEdge = getEdgeNode();
  newEdge -> a = va;
  newEdge -> b = vb;
  newEdge -> next = EDGES -> next;
  EDGES -> next = newEdge;

  insertIncidentEdge(va, newEdge);
  if(va != vb)
    insertIncidentEdge(vb, newEdge);
  
  return newEdge;
}

Vertex* findVertexNodeByNodenumber(int n) {
  // 노드번호 n에 해당하는 정점 찾기
  // 정점이 있으면 해당 노드 반환, 없으면 NULL 반환
  Vertex* v = VERTICES -> next;
  while(v != NULL){
    if(v -> n == n)
      break;
    v = v -> next;
  }

  return v;
}

Vertex* oppositeVertex(Vertex* v, Edge* e){
  // 정점 v의 간선 e 건너편에 있는 정점을 리턴
  if(e -> a == v)
    return e -> b;
  else
    return e -> a;
}

너비우선탐색(BFS)

이진트리의 레벨순회와 유사하다.

DFS와의 차이는 아래와 같이 정리할 수 있다.

• 수행 결과는 동일하지만 무엇을 먼저 탐색하는지가 다르다.
• DFS는 재귀스택 부담이 있었지만, BFS는 그 대신 레벨 리스트 유지 부담이 있다.

정점과 간선은 아래 상태를 가진다.

• 정점
  • Fresh
  • Visited
• 간선
  • Fresh
  • Tree (트리 간선)
  • Cross (교차 간선) : 같거나 하나 큰 레벨 방향의 간선

BFS를 돌고 나면 그래프는 레벨별로 리스트를 갖게 된다.

• 레벨0, 즉 시작정점은 $L_0$에 들어간다.
• 레벨0에서 출발해 도달한 정점들, 즉 레벨1에 해당하는 정점들은 $L_1$에 들어간다.
• 그 다음은 마찬가지로 레벨2에 대한 $L_2$, 레벨3에 대한 $L_3$으로 나아간다.

BFS의 속성은 다음과 같다.

• 알고리즘 BFS(G,v)는 v를 포함한 연결요소의 모든 정점, 간선을 방문
• 트리 간선(Tree로 라벨된 간선)은 신장트리(BFS Tree)를 형성
• $L_i$ 내의 각 정점 w에 대해
  • BFS 신장트리의 v에서 w로 가는 경로는 i개 간선을 가진다.
  • v의 연결요소의 v에서 w로 가는 모든 경로는 최소 i개 간선을 가진다.
    (대충 $L_i$리스트는 시작정점에서 i개 간선을 거쳐 갈 수 있다는 말)

의사코드로 표현된 알고리즘은 아래와 같다. (그래프는 인접행렬로 구현함)

Alg driver(G)
1. for each v ∈ G.vertices()
     v.label ← Fresh
   for each e ∈ G.edges()
     e.label ← Fresh
2. for each v ∈ G.vertices()
     if(v.label = Fresh)
       BFS(G, v)

Alg BFS(G, v)
1. L_0 ← 빈 리스트
   L_0.addLast(v)
   v.label ← Visited
2. i ← 0
3. while(!L_i.isEmpty())
     L_(i+1) ← 빈 리스트
     for each v ∈ L_i.elements()
       for each e ∈ G.incidentEdges(v)
         if(e.label = Fresh)
           w ← G.opposite(v, e)
           if(w.label = Fresh)
             e.label ← Tree
             w.label ← Visited
             L_(i+1).addLast(w)
           else
             e.label ← Cross

C로 구현된 BFS는 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

// 간선, 정점 노드 정의.
typedef struct _Edge {
  struct _Vertex* a;
  struct _Vertex* b;
  int label; // 0:Fresh, 2:Tree, 3:Cross
  struct _Edge* next;
} Edge;

typedef struct _Vertex {
  int adjID; // 인접행렬 매트릭스에서 사용할 해당 정점의 ID
  int n; // node number 
  int label; // 0:Fresh, 1:Visited
  struct _Vertex* next;
} Vertex;

// 함수 원형 정의
Edge* getEdgeNode();
Vertex* getVertexNode();

Vertex* findVertexNodeByNodenumber(int n);
Edge* insertEdge(Vertex* va, Vertex* vb);
void insertIncidentEdge(int aAdjID, int bAdjID, Edge* e);
Vertex* insertVertex(int a);
Vertex* oppositeVertex(int nodenum, Edge* e);

void BFS();
void BFSI(Vertex* v);
void insertVertexIntoLevelContainer(int i, Vertex* v);

// -----------------

Vertex* VERTICES = NULL; // 정점 리스트
Edge* EDGES = NULL; // 간선 리스트

Edge* ADJS[101][101] = { NULL };
Vertex** LEVEL_CONTAINERS = NULL; // 레벨 컨테이너의 리스트

int VTX_NUM = 0;

int main(){
  // n, m, s 입력
  int n, m, s;
  scanf("%d%d%d", &n, &m, &s); getchar();
  VTX_NUM = n;

  // 정점, 간선 리스트 초기화.
  VERTICES = getVertexNode(); // header node
  EDGES = getEdgeNode(); // header node

  // BFS 순회시 각 레벨별 노드를 보관할 컨테이너 초기화
  LEVEL_CONTAINERS = (Vertex**)malloc(sizeof(Vertex*)*VTX_NUM);
  for(int i=0; i<VTX_NUM; i++)
    LEVEL_CONTAINERS[i] = getVertexNode();

  // 정점, 간선 입력.
  int a, b;
  Vertex *va, *vb;
  for(int i=0; i<m; i++){
    va = NULL; vb = NULL;
    scanf("%d%d", &a, &b); getchar();

    // 입력받은 정점 번호에 대한 정점이 없으면 생성
    va = findVertexNodeByNodenumber(a);
    vb = findVertexNodeByNodenumber(b);
    if(va == NULL) va = insertVertex(a);
    if(vb == NULL) vb = insertVertex(b);

    insertEdge(va, vb);
  }

  // 순회
  BFS(s);
  
  return 0;
}

// --------------------------
//   새로운 노드를 할당하는 함수

Edge* getEdgeNode() {
  Edge* p = (Edge*)malloc(sizeof(Edge));
  p -> a = NULL;
  p -> b = NULL;
  p -> next = NULL;
  return p;
}

Vertex* getVertexNode() {
  Vertex* p = (Vertex*)malloc(sizeof(Vertex));
  p -> next = NULL;

  return p;
}

// --------------------------
//    기타 함수

void BFS(int s) { // s : 순회 시작 정점 번호
  // 초기화
  Vertex* u = VERTICES -> next;
  while(u != NULL){
    u -> label = 0; // Fresh
    u = u -> next;
  }
  
  Edge* e = EDGES -> next;
  while(e != NULL) {
    e -> label = 0; // Fresh
    e = e -> next;
  }
  
  // s번 정점노드와 첫 번째 정점노드 스왑
  // ---- VERTICES리스트에 대해서
  Vertex* vs = findVertexNodeByNodenumber(s); // s번 정점
  Vertex* vsPrev = VERTICES -> next;
  while(vsPrev -> next != vs)
    vsPrev = vsPrev -> next;

  vsPrev -> next = vs -> next;
  vs -> next = VERTICES -> next;
  VERTICES -> next = vs;
  
  // 순회
  u = VERTICES -> next;
  while(u != NULL) {
    if(u -> label == 0) // 정점 u가 Fresh이면
      BFSI(u);
    u = u -> next;
  }
}

void BFSI(Vertex* u) {
  int i = 0;
  u -> label = 1; // visited
  printf("%d\n", u->n);
  
  insertVertexIntoLevelContainer(i, u);

  Vertex* element = NULL;
  Edge* edge = NULL;
  while(LEVEL_CONTAINERS[i]->next != NULL) { // if L_i is not empty
    element = LEVEL_CONTAINERS[i] -> next; // L_i의 원소(정점) 조회
    while(element != NULL) {
      for(int k=0; k<=100; k++){
        edge = ADJS[element->adjID][k]; // 부착간선 조회
        if(edge == NULL) continue;
        
        if(edge -> label == 0){ // l(e) = Fresh
          Vertex* w = oppositeVertex(element->n, edge);
          if(w -> label == 0) { // l(w) = Fresh
            edge -> label = 2; // Tree
            w -> label = 1; // Visited
            printf("%d\n", w->n);
            insertVertexIntoLevelContainer(i+1, w);
          }
          else {
            edge -> label = 3; // Cross
          }
        }
      }
      element = element -> next;
    }
    
    i++;
  }

  
}

void insertVertexIntoLevelContainer(int i, Vertex* v) {
  // i 레벨 컨테이너의 가장 뒤에 정점 복사본 삽입
  // 원본(v)와 복사본(copiedVtx)는 next필드값만 다름.
  Vertex* copiedVtx = getVertexNode();

  copiedVtx -> adjID = v -> adjID;
  copiedVtx -> n = v -> n;
  copiedVtx -> label = v -> label;

  Vertex* p = LEVEL_CONTAINERS[i] -> next;
  Vertex* q = LEVEL_CONTAINERS[i];
  while(p != NULL){
    q = p;
    p = p -> next;
  }
  
  copiedVtx -> next = NULL;
  q -> next = copiedVtx;
}

Vertex* insertVertex(int a){
  // 입력 : 노드 번호 a
  Vertex* p = getVertexNode();
  
  p -> adjID = a-1;
  p -> n = a;
  
  p -> next = VERTICES -> next;
  VERTICES -> next = p;
  
  return p;
}

void insertIncidentEdge(int aAdjID, int bAdjID, Edge* e){
  ADJS[aAdjID][bAdjID] = e;
  ADJS[bAdjID][aAdjID] = e;
}

Edge* insertEdge(Vertex* va, Vertex* vb) {
  // 입력 : 정점 노드 va, vb
  Edge* newEdge = getEdgeNode();
  newEdge -> a = va;
  newEdge -> b = vb;
  newEdge -> next = EDGES -> next;
  EDGES -> next = newEdge;

  insertIncidentEdge(va->adjID, vb->adjID, newEdge);
  
  return newEdge;
}

Vertex* findVertexNodeByNodenumber(int n) {
  // 노드번호 n에 해당하는 정점 찾기
  // 정점이 있으면 해당 노드 반환, 없으면 NULL 반환
  Vertex* v = VERTICES -> next;
  while(v != NULL){
    if(v -> n == n)
      break;
    v = v -> next;
  }

  return v;
}

Vertex* oppositeVertex(int nodenum, Edge* e){
  // 정점 v의 간선 e 건너편에 있는 정점을 리턴
  if((e -> a) -> n == nodenum)
    return e -> b;
  else
    return e -> a;
}

방향그래프

모든 간선이 방향간선인 그래프

속성

• 모든 간선이 한 방향인 그래프에서, 간선 (a,b)는 a에서 b로만 간다.
  --> b에서 a로 가지는 않는다.
• 루프와 중복간선이 없다면(=단순하다면), $m \leq n(n-1)$이다.

방향 DFS 알고리즘

DFS/BFS를 방향그래프에 특화한 것으로, 주어진 간선 방향으로만 순회한다.
간선은 아래 네 가지 상태를 가진다.

• Tree(트리 간선) : 트리를 만드는 방향 (밑으로 간다)
• Back(후향 간선) : Tree간선의 반대방향 (위로 간다)
• Forward(전향 간선) : 트리를 만드는 방향이기는 한데.. 어떤 간선의 도착 정점이 이미 다른 Tree간선에 의해 트리에 들어와있다면, 그 간선은 Forward간선이다. (내가 이름을 짓는다면 'Too much talking 간선'으로 짓겠다.)
• Cross(교차 간선) : sibling으로 가는 방향

  Back
  ┌───→   A  ────→ C
  |    ↙  \ 
  |   B    |   
  \ ↙ ↘ ↙ Forward
   D  ← E
    Cross
    
표시 안된 간선 : Tree
D->E : Cross
D->A : Back
A->E : Forward

강연결성

강연결은 그래프 전체에 도달 가능성이 있는 것으로 생각할 수 있다.

• 도달 가능성 : 방향그래프의 정점 u에서 정점 v로 가는 방향경로가 존재하면 아래와 같이 표현한다.
  • u는 v에 도달한다.
  • v는 u로부터 도달 가능하다.
• 강연결 : 방향그래프에서 한 정점에서 모든 정점으로(전부 다) 도달하면 강연결(strongly connected)이라고 한다. 그 성질을 '강연결성'이라고 한다.
• 강연결 요소 : 강연결인 최대의 부그래프

강연결을 검사하기 위해 DFS를 사용할 수 있다.
이 때, 모든 정점의 강연결을 검사하지 않고도 전체 그래프가 강연결인지 여부를 판단할 수 있다.

시간 복잡도 O(2n+2m) = O(n+m)에 해결할 수 있다.

Alg isStronglyConnected(G)
1. v ← G.aVertex()  # 임의의 정점 하나 선택

# v에서 어디로 갈 수 있냐?
2. DFS(G, v)
3. for each u ∈ G.vertices()
     if(u.label = Fresh)
       return False # 삑! 강연결이 아닙니다.

# 어디에서 v로 갈 수 있냐?
4. for each e ∈ G.edges()  # 그래프의 모든 간선방향 반대로 역행
     G.reverseDirection(e)
   DFS(G, v)
   
5. for each u ∈ G.vertices()
     if(u.label = Fresh)
       return False # 삑! 강연결이 아닙니다.
 
# 강연결로 판단됨
6. return True

강연결 요소를 구하는데에도 DFS를 사용할 수 있다. 강연결 검사와 마찬가지로 O(n+m)시간에 해결 가능하다.

이행적 폐쇄

이행적 폐쇄는 방향그래프 G에 대해 다음을 만족하는 방향그래프로, 도달가능성 정보를 제공한다.

• 동일한 정점으로 구성
• G에서 u가 v에 도달하면 방향간선 (u,v)가 존재
  (대충 모든 경로를 직행 간선으로 다시 표현한다는 소리)

그래프 G
+-+         +-+         +-+
|A| ------> |B| ------> |C|
+-+         +-+         +-+
             |      +-+
             +----> |D|
                    +-+
  
그래프 G' (이행적 폐쇄)
 +-----------------------+
 |                       ↓
+-+         +-+         +-+
|A| ------> |B| ------> |C|
+-+         +-+         +-+
 |           |      +-+
 |           +----> |D|
 |                  +-+
 |                   ↑
 +-------------------+

이행적 폐쇄를 구하기 위해(계산하기 위해) 두 가지 방법을 사용할 수 있다

• DFS : O(n(n+m))
• DP - Floyd-Warshall 알고리즘 : 인접행렬로 구현한 경우 O(n^3)

플로이드 워셜 알고리즘을 의사코드로 표현하면 아래와 같다.

Alg Floyd-Warshall(G)
1. G_0 ← G
2. for k ← 1 to n
     G_k ← G_(k-1)
     for i ← 1 to n, i ≠ k
       for j ← 1 to n, j ≠ i, k 
         if(G_(k-1).areAdjacent(v_i, v_k) & G_(k-1).areAdjacent(v_k, v_j))
           if(!G_k.areAdjacent(v_i, v_j))
             G_k.insertDirectedEdge(v_i, v_j, k)
3. return G_n

위상 정렬

방향그래프가 DAG이면 위상순서를 가진다. 역도 성립한다.
위상정렬 수행 과정에서 사이클이 발견되면 위상순서가 없음을 알 수 있다.

• DAG(방향 비싸이클 그래프) : 방향 사이클이 없는 방향그래프
• 위상 순서 : 위상 정렬 과정에서 방향성을 고려하여 부여되는 순서
• 위상 정렬 : DAG로부터 위상 순서를 얻는 절차

위상 정렬은 두 가지로 구현할 수 있다.

• 정점의 진입차수 이용 : 맨앞에 있는게 누구냐?
• DFS 이용 : 맨뒤에 있는게 누구냐?

정점의 진입차수를 이용한 위상정렬 알고리즘은 아래와 같다.

Alg topologicalSort_InDegree(G)
1. Q ← 빈 큐
2. for each u ∈ G.vertices()
     u.inCount ← G.inDegree(u)
     if(u.inCount = 0)
       Q.enqueue(u)
3. i ← 1
4. while(!Q.isEmpty())
     u ← Q.dequeue()
     u.topologicalNum ← i
     i ← i+1
     
     for each e ∈ G.outIncidentEdges(u)
       w ← G.opposite(u, e)
       w.inCount ← w.inCount - 1
       if(w.inCount = 0)
         Q.enqueue()
5. if(i≤n)
     return False # G는 DAG가 아니다. (사이클이 있다.)
   else
     return True  # G는 DAG이므로 정상적으로 위상정렬 완료되었다.

DFS를 이용한 위상정렬 알고리즘은 아래와 같다.

Alg driver(G)
1. n ← G.numVertices()
2. for each u ∈ G.vertices()
     u.label ← Fresh
     u.topologicalNum ← NULL
3. for each v ∈ G.vertices()
     if(v.label = Fresh)
       topologicalSort_DFS(G, v)

Alg topologicalSort_DFS(G, v)
1. v ← Visited
2. for each e ∈ G.outIncidentEdges(v)
     w ← opposite(v, e)
     if(w.label = Fresh)
       topologicalSort_DFS(G, w)
     elseif(w.topologicalNum = NULL) # 방문했는데 위상순서 번호가 없다
       return False  # G는 DAG가 아니다.
3. v.topologicalNum ← n
   n ← n-1

최소신장트리(MST)

최소신장트리는 가중 그래프의 총 간선 무게가 최소인 신장트리이다.
(대충 그래프의 정점은 다 취하고 간선은 일부만 취했는데, 간선 무게 더한게 최소가 된다는 소리)

속성

• 싸이클 속성
  1. 그래프 G와 최소신장트리 T가 있다.
  2. G에 있지만 T에 없는 한 간선 e가 있다고 하자.
  3. e를 T에 추가하면 사이클 C가 생긴다고 가정하자.
  4. 이 때, 사이클 C에 대해 $weight(모든\ 간선\ 중\ 하나) \leq weight(e)$이다.
• 분할 속성
  1. 그래프 G의 정점들을 두 개의 부분 집합 U, V로 나눈다.
  2. U, V를 연결하는 최소 무게의 간선 e가 있다.
  3. 간선 e를 포함하는 최소신장트리가 존재한다.

탐욕법

MST 계산을 위해 세 가지 알고리즘을 사용할 수 있다.
아래에 설명해둔 알고리즘은 모두 단순 연결 무방향 가중그래프에 탐욕법을 적용한다. 성능은 모두 $O(m\ logn)$이다.

탐욕법은 탐욕적 선택 속성을 가진 문제에 적용할 수 있다.
전체적인 이득을 생각하지 않고 지역적인(그때그때 상황의) 이득을 택하는 것이다.

Prim-Jarnik 알고리즘

시작할 때 모든 정점의 거리는 무한대로 초기화하고, 임의의 시작정점에 대해서만 0으로 설정한다.

각 정점은 아래 두 속성을 갖는다.

• distance : 거리자
• parent : 부모방향 간선

Prim-Jarnik은 (배낭 밖의)모든 정점을 우선순위큐에 넣고 시작한다. 우선순위큐는 최소힙으로 구현할 수 있다. 힙의 키는 정점의 거리자, 원소는 정점이다.

while문에서 실질적인 알고리즘이 동작한다. 힙에서 거리자가 가장 작은 정점을 하나 빼온뒤, 인접정점을 하나씩 꺼내 거리자와 부모간선 값을 변경한다.

Alg PrimJarnik(G)
1. for each v ∈ G.vertices()
     v.distance ← ∞
     v.parent ← NULL
2. s ← G.aVertex()
   s.distance ← 0
3. Q ← 빈 우선순위 큐 (힙)
   for each v ∈ G.vertices()
     Q.insertItem(v.distance, v)

4. while(!Q.isEmpty())
     u ← Q.removeMin()
     for each e ∈ G.incidentEdges(u)
       z ← G.opposite(e, u)
       if( (z∈Q) & (e.weight < z.distance) )
         z.distance ← e.weight
         z.parent ← e
         Q.replaceKey(z, e.weight)

Kruskal 알고리즘

Prim-Jarnik에서는 while문을 돌 때마다 정점과 간선을 하나씩 포함시키며 배낭을 확장한다. 배낭 밖의 정점은 우선순위큐에 넣고 시작했다.

Kruskal은 Prim-Jarnik과 다르게 각 정점을 개별 배낭에 넣고 시작한다. 여기서 개별 배낭은 분리집합으로 구현할 수 있다. 우선순위 큐에는 배낭 밖의 간선이 들어간다.

항목	Prim-Jarnik	Kruskal
초기 배낭 개수	1	정점 개수
초기 배낭이 담는 것	시작 정점	배낭 1개당 정점 1개
우선순위큐가 담는 것	배낭 밖 정점	배낭 밖 간선

알고리즘이 동작함에 따라 두 배낭과 그 사이의 간선을 하나의 배낭으로 합친다.

의사코드로 표현된 알고리즘은 다음과 같다.

Alg Kruskal(G)
1. for each v ∈ G.vertices()
     Bag(v) ← {v}  
   Q ← 빈 우선순위 큐
   for each e ∈ G.edges()
     Q.insertItem(e.weight, e)
   T ← NULL # MST를 구성하는 하나의 배낭
2. while(T의 간선 개수 < n-1)
     e ← Q.removeMin()
     if( Bag(e.u) ≠ Bag(e.v) )
       T.add(e)
       Merge(Bag(e.u), Bag(e.v))
3. return T

Baruvka 알고리즘

우선순위큐를 사용하지 않는다.

Alg Baruvka(G)
1. T ← V
2. while( T의 간선 개수 < n-1 )
     for each (T안의 연결요소 C_i)
       e ← C_i에서 T안의 다른 연결요소로 연결되는, 무게가 가장 작은 간선
       if( e ∉ T )
         T.add(e)
3. return T

최단경로

최단경로는 두 개의 정점 사이 무게 합이 최소인 경로이다.
최단경로 계산 알고리즘별로 적용 가능한 그래프와 성능이 다르다.

속성

• 최단경로의 부분경로는 최단경로이다.
• 단일점 최단경로 : 출발정점에서 다른 모든 정점에 도달하는 최단경로들의 트리가 존재한다. 이 최단경로트리는 루트 트리이다.

최단경로를 구할 수 없는 경우

• 가중 방향그래프에 음의 무게를 가진 싸이클이 존재
• 가중 무방향그래프에 음의 무게를 가진 간선이 존재

알고리즘 개요

알고리즘	적용 가능한 그래프	성능
다익스트라	{e∈E | e.w≥0} 인 그래프	O(m logn) or O(n^2)
벨만포드	방향그래프	O(nm)
BFS	비가중그래프	O(n+m)
위상 순서	DAG	O(n+m)

다익스트라

s는 임의로 지정한 출발정점이다.
다익스트라를 돌리면 s로부터 모든 정점으로의 최단경로를 구한다.

우선순위큐는 힙으로 구현할 수 있다. replaceKey는 해당 정점에 대한 upHeap이나 다름없다.

Alg Dijkstra(G)
1. for each v ∈ G.vertices()
     v.distance ← INFINITE
   s.distance ← 0
2. Q ← 빈 우선순위 큐
   for each v ∈ G.vertices()
     Q.insertItem(v.distance, v)
3. while(!Q.isEmpty())
     u ← Q.removeMin()
     for each e ∈ G.incidentEdges(u)
       z ← G.opposite(u, e)
       if(z ∈ Q.elements())
         if(u.distance + e.weight < z.distance)
           z.distance ← u.distance + e.weight
           Q.replaceKey(z, z.distance)

벨만포드

Alg Bellman-Ford(G, s)
1. for each v ∈ G.vertices()
     v.distance ← INFINITE
   s.distance ← 0
2. for i ← 1 to n-1
     for each e ∈ G.edges()
       u ← G.origin(e)
       z ← G.opposite(u, e)
       z.distance ← min(z.distance, u.distance+e.weight)

위상순서를 이용한 DAG의 최단경로 계산

그래프 G는 위상정렬이 완료되어 각 정점이 순서를 갖고 있다고 가정한다.
v_i는 i번째 위상순서의 정점이다.

Alg TopologicalOrder_ShortestPath(G, s)
1. for each v ∈ G.vertices()
     v.distance ← INFINITE
   s.distance ← 0
2. for i ← 1 to n-1
     for each e ∈ G.outIncidentEdges(v_i)
       z ← G.opposite(v_i, e)
       z.distance ← min(z.distance, v_i.distance + e.weight)

모든 쌍 최단경로

가중 방향그래프의 모든 정점사이의 최단경로 거리를 찾을 수 있다.
다익스트라, 벨만포드를 모든 정점에 대해(=n번) 호출할 수 있다.

또는 플로이드-워셜과 유사한 알고리즘을 사용해 O(n^3)시간에 찾을 수 있다. 이 방법을 의사코드로 나타내면 아래와 같다.

알고리즘을 돌리기 전 모든 정점에 대해 임의의 번호 1~n을 붙여두어야 한다.

Alg allPairsShortestDistance(G)
1. for i ← 1 to n
     for j ← 1 to n
       if(i=j)
         D[i][j] ← 0
       elseif( (v_i, v_j) ∈ G.edges() )
         D[i][j] ← w(v_i, v_j)
       else
         D[i][j] ← INFINITE
2. for k ← 1 to n
     for i ← 1 to n
       for j ← 1 to n
         D[i][j] ← min(D[i][j], D[i][k]+D[k][j])