그래프

개념
정점(Vertex)의 집합 V와 두 정점을 잇는 선분인 간선(Edge)의 집합 E로 이루어지는 도형

I. 그래프 (Graph)의 개요

가.  그래프의 정의

    - 정점(Vertex)의 집합 V와 두 정점을 잇는 선분인 간선(Edge)의 집합 E로 이루어지는 도형

 G1 = (V, E)

 V(G1) = {0, 1, 2, 3}

 E(G1) = {(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)}

 

 

    나.  그래프의 제한 사항

         - 자기 자신을 향하는 간선을 없다. (no self loop)

         - 중복된 간선을 허용하지 않는다. (no multigraph)

 

      다. 그래프에 관련된 용어

용어

설명

한글

영어

완전 그래프

complete graph

그래프에서 간선의 수가 최대인 그래프

인접

adjacent

무방향 그래프에서 정점 a,b에 대하여 간선(a,b)가 있으면 정점a는 정점b에 인접(adjacent)하다고 한다.

부속

incident

무방향 그래프에서 정점 a,b에 대하여 간선(a,b)가 있으면 간선(a,b)는 정점a와 b에 부속(incident)하다고 한다.

경로

path

정점 a에서 정점 b로 가는 간선의 집합

경로의 길이

length of path

경로 상에 있는 간선의 수

단순 경로

simple path

경로 상의 정점이 중복되지 않는 경로

사이클

cycle

단순 경로 중 경로가 다시 원점으로 돌아오는 경우

 

Ⅱ. 그래프의 표현

가.  인접 행렬 (adjacency matrix)

- 그래프를 이차원 행렬에 저장하는 방법으로서

  1. if (vi, vj)가 인접할 때        => “1”
  2. if (vi, vj)가 인접하지 않을 때 => “0”

- 무방향 그래프에서는 행렬이 대각선을 중심으로 대칭이다.

 

나.  인접 리스트 (adjacency list)

  1. 각각의 vertex에 대한 인접한 vertex들을 나열
  2. 각 vertex를 시작으로 인접 vertex를 list로 연결
  3. 연결된 vertex들만 리스트로 관리하여 기억장소 낭비 최소
  4. 상대적으로 edge수가 많을 경우, 기억장소 낭비 증가

#define MAX_VERTICES 50

struct list_node {

 int vertex;

 struct list_node * link;

};

typedef struct list_node node;

typedef node * node_ptr;

node_ptr graph[MAX_VERTEX];

 

Ⅲ. 그래프의 탐색

가.  깊이 우선 탐색 (DFS : Depth First Search)

- 트리의 전위탐색 방법을 그래프에 적용한 것

- 자동차로 여행할 경우, 방문지가 있으면 무조건 방문하는 방법

(1) 하나의 노드를 택한다.

(2) 노드를 방문하여 필요한 작업을 한 다음, 연결된 다음 노드를 찾는다.

    현재 방문 노드는 스택에 저장하고, 2단계를 반복하면서 막히면 3단계로 간다.

(3) 더 이상 방문할 노드가 없으면 스택에서 노드를 빼내 다음 노드를 찾아 2단계를 반복함.

/* 정점 v에서 시작하여 그래프의 깊이 우선 방문 */

void dfs(int v) {

 node_ptr w;

 visited[v] = TRUE; /* 1 방문지 표시 */

 printf(“%5d”, v);

 for(w = graph[v]; w; w = w->link) /* 2 연결리스트 탐색 */

  if(!visited[w->vertex])

   dfs(w->vertex);

}

 

나.  너비 우선 탐색 (BFS : Breath First Search)

- 트리의 레벨우선 탐색을 그래프에 적용한 것

- 자동차로 여행할 경우, 가까운 곳부터 방문하는 방법

(1) 하나의 노드를 택한다.

(2) 노드를 방문하여 필요한 작업을 한 다음, 연결된 다음 노드를 찾는다.

    노드들을 큐에 저장한다. 더 이상 방문할 곳이 없으면 3단계로 간다.

(3) 큐의 맨 앞의 노드를 빼내 2단계를 반복한다.

/* 정점 v에서 시작하여 그래프의 너비 우선 방문 */

void bfs(int v) {

 node_ptr w; queue_ptr front, rear;

 front = rear = NULL;/* initialize queue */

 printf(“%5d”, v);

 visited[v] = TRUE; /* 1 방문지 기록 */

 insert(&front, &rear, v);

 while(front) /* 2 방문지 있는 동안 반복 */

 { v = delete(&front);

   for(w = graph[v]; w; w = w->link;

   if(!visited[w->vertex]) {

     printf(“%5d”, w->vertex);

     insert(&front, &rear, w->vertex);

     visited[w->vertex] = TRUE;

}}}

댓글