그래프

● 그래프의 정의

앞에서 배운 트리와 같은 경우는 레벨에 따라 또는 운행방법에 따라 정보를 저장하고 처리하지만, 실세계에는 어떤 공정의 반복이나 상하관계가 명확하지 않은 보다 자유로운 정보 표현 방식이 필요하다.

그래프는 정보 단위와 연결정보만으로 정보를 표현하는 일반적인 구조로서 트리의 루트와 같은 시각정보가 가변적이다. 그러므로 프로그래머에게 더욱 유연성이 부여되며, 그 만큼 책임이 따르게 된다.
( 트리도 그래프에 속한다 )

V(G)는 정점들의 집합.
E(G)는 연결선들의 집합.
그래프에서 정점의 쌍은 <V1, V2>로 표시하는데 여기서 V1은 연결선의 꼬리라 하고 V2는 연결선의 머리이다.

① 인접 : 정점의 순서쌍(V1, V2)이 E(G)에 있는 연결선이면 V1, V2를 인접한다고 한다.
② 부속 : 정점의 순서쌍(V1, V2)이 E(G)에 있는 연결선이면 연결선 (V1, V2)는 정점 V1, V2에 부속되어 있다.
③ 경로 : V1에서 Vn에 이르는 정점들의 순서를 경로라 하며, 경로상의 연결선의 수를 경로의 길이라 한다.
④ 단순 경로 : 첫 번째와 마지막 정점을 제외하고 모든 정점이 서로 다를 때를 말한다.
⑤ 사이클 : 첫번째 경로와 마지막 정점이 같은 단순 경로를 말한다.
⑥ 차수 : 한 정점에 교차된 연결선들의 수를 만한다.
⑦ 연결 그래프 : 그래프에 속하는 모든 정점들이 연결되어 있어 특정 두 정점에 대하여 경로가 존재하는 그래프
⑧ 다중 그래프 : 그래프의 임의의 두 정점 사이에 두 개 이상의 연결선이 존재하는 그래프이다.
⑨ 완전 그래프 : n개의 정점으로 구성된 무방향 그래프에서 최대 연결선의 수가 n(n-1)/2이고, 
                        방향 그래프에서 최대 연결선의 수가 n(n-1)인 그래프를 완전 그래프라고 한다.
                        각 정점이 다른 모든 정점과의 연결선이 있는 경우

● 그래프의 표현

① 인접행렬     

각 정점들 간의 연결 상태를 행렬과 같은 형태로 나타내는 방법. 정점의 개수가 n개일 때 인접행렬 M은 n×n의 정사각 행렬 형태를 띤다. i행, j열의 값이 1이면 i와 j에 해당하는 정점이 인접해 있는 것이고, 그 값이 0이면 인접하지 않은 것이다.

 

② 인접 리스트

인접 리스트는 정점들의 포인터를 1차원으로 표현한 것을 말한다. 1차원 배열의 각 데이터는 그 정점에 인접한 노드들을 연결 리스트 형태로 표현한 것이다. ※ 인접한것!!

 

#define MAX_VERTICES 50  /* 정점의 최대수 */
typedef struct vertex *vertex_pointer;
struct vertex {
    int vertex_num;
    vertex_pointer link;
vertex_pointer graph[MAX_VERTICES];
vertex_pointer graph[MAX_VERTICES];

● 그래프의 연산

① 깊이 우선 탐색
int already_visited[MAX_VERTICES]; 처럼 방문 여부를 표시할 전역 변수 배열을 사용한다.
방문 한 곳의 값을 1로 저장, 시작점에서 인접한 정점을 선택하여 그것을 시작점으로하여 탐색을 다시 시작
트리의 전위 운행에 의한 트리탐색 방법과 비슷하다.

 void dfs(int s)

{
    vertex_pointer v;
    already_visited[s] = 1;
    printf("%d :: ", s);
    for ( v = graph[s]; v != NULL; v = v -> link )
        if (already_visited[v->vertex_num] == 0)
}

 

② 너비 우선 탐색
정점 s에서 시작하여 미리 준비한 배열 already_visited 방문여부를 표시하면서 s의 인접리스트에 있는 모든 정점들을 바로 방문한다. 이때 방문된 순서로 자료구조 큐에 삽입되면 s의 인접 리스트상의 첫 번째 정점이 큐로부터 서비스될 정점이 된다. 이 정점은 다시 인접한 방문이 안 된 정점들을 모두 방문한다. 이렇게 계속해서 큐에 쌓아가면서 계속 탐색을 진행한다. ※큐를 사용해서 구현한 것이 핵심!

void bfs(int s)
{
    int v;
    vertex_pointer now;
    int stop = 0;
    already_visited[s] = 1;
    printf("%d :: ", s);
    addq(s);
    while (!stop) {
        v = deleteq();
        for ( now = graph[v]; now != NULL ; now = now -> link) {
            if (already_visited[now->vertex_num] == 0) {
                already_visited[now->vertex_num] = 1;
                printf("%d ::", vertex_num);
                addq(vertex_num);
            }
        }
        stop = check_continue();
    }
}

● 연결 요소 찾기

위의 탐색 함수는 여러 연결 요소를 가지고 있는 그래프에서 호출할시 특정 연결 요소만을 방문하고 종료되는 문제점이 있다. 따라서 아래의 connected() 함수를 생성하여 그래프의 모든 정점에 방문을 할 수 있게한다.

 int conneceted()
{
    int v, cnum = 0;
    if (already_visited[v] == 0 ) {
        dfs(v);
        cnum++;
        printf("\n");
        }
    return cnum;
}

● 신장트리

신장트리는 간단히 말해서 모든 정점을 포함하고, 이것들이 모두 연결된 상태의 트리이다. 
또 신장트리는 특정 그래프의 최소 부분 그래프로서 n개의 정점이 있다면 n-1개의 간선을 가지고 있는 구조다.
만일 신장트리에 간선을 추가한다면 사이클을 이루게 된다.

깊이우선 탐색함수를 이용해 만들어진 신장 트리는 깊이 우선 신장 트리이고,
너비우선 탐색함수를 이용해 만들어진 신장 트리는 너비 우선 신장 트리이다.

● 최소 비용 신장트리

실제 응용분야에서는 그래프의 구조인 간선에 가중치를 부여하는 경우가 더 많다. 가중치가 비용이라면 최소화되도록 연결요소가 만들어져야 한다. 최소 비용 신장트리는 최소비용이나 최대 이익을 나타낼 수 있도록 구성된 신장 트리이다.

가중치가 나타나 있는 그래프

● Kruscal의 알고리즘

① 간선들 중 가장 가중치가 적은 간선을 선택한다.
② 만약 선택된 간선으로 인해 사이클이 발생하면 제외한다.
③ 위 과정들을 반복한 후 모든 정점이 연결되면 알고리즘을 끝낸다.

● Prim의 알고리즘

① 시작할 정점을 임의로 선택한다.
② 선택된 정점들에 부속된 간선들 중 가중치가 적은 간선을 선택한다.
③ 선택된 간선에 인접한 두 정점에 대하여 ②의 단계를 반복한다.
④ 만약 Cycle이 발생하면 그 전에 방문된 정점에서 아직 방문이 안된 간선 중 가중치가 제일 작은 것을 선택한다.
⑤ 모든 정점이 연결되면 알고리즘이 끝난다.