그래프의 개념과 종류, 구현

그래프

-> 연결되어 있는 객체 간의 관계를 표현하는 자료구조. 가장 일반적인 자료구조의 형태로 트리, 이진트리도 그래프의 특수한 경우. 선수과목 관계, 도로망, 영역간 인접 관계 등을 표현할 수 있음.

 

 

▷ 개념

· 그래프 G는 ( V,E )로 표시. 특별한 언급이 없으면 그래프는 자가 루프와 중복 에지가 없는 단순 그래프를 의미.

 

 

· 정점(vertex)

     V(G) : 그래프 G의 정점들의 집합. 여러 가지 특성을 가질 수 있는 객체를 의미하며 노드라고도 불림.

 

· 에지(edge)

    E(G) : 그래프 G의 에지들의 집합. 정점들 간의 관계를 의미하며 간선 또는 링크라고도 불림.

 

· 인접 정점(adjacent vertex)

    어떤 정점에서 에지에 의해 직접 연결된 정점

 

· 경로(path)

    정점 s로부터 정점 t까지의 (방향) 경로가 존재하려면, 반드시 나열된 정점들 간에 (방향) 에지가 존재해야 함.

    경로의 길이 = 경로를 구성하는 에지의 수.

    단순 경로 : 경로 중에서 반복되는 정점, 에지가 없는 경로

    사이클(cycle) : 단순 경로의 시작 정점과 끝 정점이 동일한 경로

 

위 그림의 G1에서 0의 인접정점은 1,2,3이고 0,1,2,3은 단순 경로지만 0,1,3,2 경로가 아님. 0,1,2,0은 사이클.

 

 

 

 

▷ 종류

 

· 무향 그래프(undirected graph)

   무방향/ 양방향 그래프. 도로의 왕복통행 길. (A,B) = (B,A). 무향 그래프의 차수는 하나의 정점에 연결된 다른 정점의 수. 정점들의 모든 차수의 합은 에지 개수의 2배임. 하나의 에지에 대해 양끝에 연결되어 있는 정점이 각각 따로 차수를 계산하기 때문.

 

 

· 방향 그래프(directed graph, digraph)

 

    방향/유향 그래프. 에지를 통해서 한쪽 방향으로만 갈 수 있음. 도로 일방통행 길. <A,B> != <B,A>. 방향 그래프의 차수는 진입 차수(in-degree)와 진출 차수(out-degree)로 나뉨. 진입 차수는 외부에서 들어오는 에지의 수이고, 진출 차수는 외부로 향하는 에지의 수임. 모든 진입(또는 진출) 차수의 합은 에지 수와 같음.

 

무향 그래프 G2와 유향 그래프 G3

 

 

· 가중치 그래프(weighted graph)

 

    에지에 비용과 같은 가중치가 할당된 그래프. 무향, 방향 그래프 모두에 해당될 수 있음. 

 

 

·부분 그래프(subgraph)

 

    정점 집합 V(G)와 에지 집합 E(G)의 부분 집합으로 이루어진 그래프. 정점 집합이 원그래프와 동일하면 Spanning subgraph라고 하고, 그 중에서도 cycle이 없는 것을 Spanning tree라고 함.

 

 

·연결 그래프(connected graph)

 

    무향 그래프 G에 있는 모든 정점 쌍에 대하여 경로가 존재하는 그래프. 즉, 경로가 없는 정점이 존재하지 않는 것. 최대로 연결된 부분 그래프를 연결 성분이라고 하며, 연결 그래프는 연결 성분이 오직 1개임. 연결 성분이 2개 이상이면 연결 그래프가 아닌 것.

연결 그래프 G1과 비연결 그래프 G2

 

 

·트리(unrooted tree)

 

    그래프의 특수한 형태로서 사이클을 갖지 않는 연결 그래프(connected acyclic graph). minimally connected graph라고도 할 수 있음. 루트 노드가 별도로 존재한다면 rooted tree. 보통 우리가 트리라고 부르는 것은 rooted tree이다.

 

 

·완전 그래프(complete graph)

 

    모든 정점이 서로 연결되어 있는 그래프. 즉, 최대로 연결되어 있는 그래프(maximally connected graph). n개의 정점을 가지는 완전 그래프의 에지 개수는 무향 그래프인 경우에 n(n-1)/2 개, 방향 그래프인 경우에 n(n-1) 개.

 

 

 

 

▷ ADT

create_graph() :: = 그래프를 생성

init(g) :: = 그래프 g를 초기화

insert_vertex(g,v) :: = 그래프 g에 정점 v 삽입

insert_edge(g,u,v) :: = 그래프 g에 에지 (u,v) 삽입

delete_vertex(g,v) :: = 그래프 g의 정점 v 삭제

delete_edge(g,u,v) :: = 그래프 g의 에지 (u,v) 삭제

is_empty(g) :: = 그래프 g가 공백 그래프인지 확인

adjacent(v) :: = 정점 v의 인접 정점 리스트 반환

destroy_graph(g) :: = 그래프 g 제거

 

 

 

 

▷ 구현

 

○ 인접 행렬(adjacent matrix)

그래프에 에지 (i,j)가 존재한다면 A[i][j]를 1으로 표현하고 에지가 없다면 0으로 표현. 일반적으로 boolean 행렬.

인접 행렬의 대각선 성분은 모두 0 (자가 루프가 없는 단순 그래프)이며 무향 그래프의 인접 행렬은 대각선 대칭(symmetric)이어서 삼각 행렬만으로도 표현 가능.

가중치 그래프인 경우 대각선 성분들만 0으로 표현하고, 존재하지 않는 에지는 무한대로 표현. 공간 복잡도 O(n2). 희소 그래프(행렬 원소 대부분이 무한대이거나 0)인 경우 매우 비효율적.

 

무향 그래프인 경우와 방향 그래프인 경우의 인접 행렬 표현

 

 

○ 인접 리스트(adjacent list)

각 정점에 인접한 정점들을 연결 리스트로 표현. 각 정점마다 하나의 연결리스트가 존재하므로 총 n개의 연결 리스트로 구성. 각 연결 리스트마다 포인터 변수가 리스트의 첫 노드를 가리키게 하고, 차수가 0이어서 연결리스트가 없는 경우에는 포인터 변수값을 null로 지정함.

정점 n개, 에지 m개인 그래프는 무향 그래프인 경우에는 에지 하나에 대해 노드가 두 개 필요하므로 n개의 포인터 변수와 2m개의 일반 노드가 존재하고, 방향 그래프의 경우에는 n개의 포인터 변수와 m개의 일반 노드가 존재함. 알고리즘의 효율성이 n과 m에 의존함.

 

typedef struct GraphNode {
    int vertex;
    struct GraphNode *link;
} GraphNode;

typdef struct GraphType {
    int n;
    GraphNode *adj_list[MAX_VERTICES];
} GraphType;