JArchive 프로그래밍 일기

그래프의 정의와 표현

연결 관계를 표현하기 위한 자료구조

그래프의 정의

그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)의 집합 V와 정점들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조이다.

그래프는 정점과 간선으로 정의된다. G(V, E)

(cf. 정점의 위치나 간선의 순서 등은 그래프 정의에 포함되지 않는다.)

관련 용어

각 정점에 연결된 간선의 갯수를 차수(degree)라고 한다.

유향 그래프에서는 간선에 방향성이 존재하므로 차수가 두 개로 나뉜다.

정점으로 들어오는 간선의 갯수를 진입차수(in-degree), 정점에서 나가는 간선의 갯수를 진출차수(out-degree) 라고 한다.

그래프의 종류

그래프는 표현하려는 대상에 따라 속성이나 형태의 제약을 추가할 수 있다.

ex) 간선에 방향 속성 추가, 간선에 가중치 속성 추가, 정점을 2개의 그룹으로 나누기 etc.

• 방향 속성
  • 방향그래프(directed graph) 혹은 유향그래프두 정점 v와 u 가 있을 때, v->u 방향의 간선과 u->v 방향의 간선은 서로 다른 간선이다.
  • : 간선에 특정한 방향이 정해진 그래프
  • 무향그래프(undirected graph) : 간선에 방향이 없는 그래프
  • : 간선을 양방향으로 지날 수 있다.
• 가중치 속성
  • 가중치 그래프(weighted graph) : 간선에 가중치(weight) 라는 실수 속성을 부여
• 형태 속성
  • 다중 그래프(multigraph) : 두 정점 사이에 2개 이상의 간선이 존재할 수 있는 그래프
  • 단순 그래프(simple graph) : 두 정점 사이에 간선이 최대 1개만 있는 그래프
• 트리 혹은 루트 없는 트리(unrooted tree)
• : 부모 자식 관계는 없고, 두 정점간의 간선이 1개만 있는 그래프
• 이분 그래프 (bipartite graph)
• : 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눈다. 서로 다른 그룹에 속한 정점 간에만 간선이 존재하도록 만든 그래프
• DAG (사이클 없는 방향 그래프, directed acyclic graph): 상호 의존 관계 또는 순서가 정해진 작업들을 표현할 때 활용
• cf) 위상정렬 : 순서가 정해진 작업들에서 순서를 정렬하는 알고리즘 (그래프의 정점을 정렬)
• : 한 점에서 출발해 자기 자신으로 돌아오는 경로(사이클)이 없는 그래프

그래프의 경로

경로(path)란, 끝과 끝이 서로 연결된 간선들을 나열한 것이다.

• 단순 경로(simple path) : 한 정점을 최대 한 번만 지나는 경로 (1-5-4-2)
• 사이클 (cycle 혹은 회로) : 시작한 정점에서 끝나는 경로 (1-5-4-1)

특별한 명시가 없다면 ''경로''는 보통 ''단순 경로''를 의미한다.

• 연결그래프(connected graph) : 모든 정점쌍들에 대해 ''경로''가 존재하는 그래프
• 비연결그래프(disconnected graph) : 특정 정점쌍 사이에 ''경로''가 없는 그래프
• 완전그래프(complete graph) : 모든 정점들이 연결되어 있는 그래프

그래프의 표현 방법

대부분 그래프는 트리에 비해 정적인 용도로 사용된다.

정적이라는 뜻은 새로운 정점이나 간선을 추가/삭제 하는 일이 드물다는 의미다.

따라서 대부분 그래프는 구조의 수정이 어렵더라도 간단하고 메모리를 적게 차지하는 방법으로 구현하는 편이다.

인접 리스트 (adjacency list)

그래프의 각 정점마다 해당 정점에서 나가는 간선의 목록(인접 노드)을 저장해서 그래프를 표현한다.

즉, 각 정점마다 하나의 연결 리스트를 갖는 방식으로 구현한다.

정점 간에 인접한지 list를 모두 확인하는 데에 오래 걸린다.

• 무향 그래프에서 (a, b) 간선은 2 번 저장된다. (a->b) (b->a)는 다르기 때문이다.
• 유향 그래프에서는 (a, b)는 특정 방향이 존재하므로 한 번만 저장된다.

vector<list<int> > adjacent;

간선의 가중치 그래프를 표현하려면?

struct Edge{
    int vertex; // 간선의 반대쪽 끝 정점의 번호 
    int weight; // 간선의 가중치 
}

또는 단순하게 pair STL 이 자주 쓰인다.

pair<int, int>  // 도착 정점, 가중치

가중치 있는 무향 그래프에서 정점, 간선, 가중치 입력받기

(pair 객체 사용)

시작 정점, 도착 정점, 가중치 순으로 입력받는다. 도착정점과 가중치를 pair로 묶는다.

• 그래프 구조 : 정점 개수 5, 간선 개수 6
• 입력 : 시작 정점, 도착 정점, 가중치

- 아래와 같이 입력이 주어진다 -
 5 6 // 정점 개수, 간선 개수
 1 2 1 // 시작 정점, 도착 정점, 가중치 순서
 4 1 5
 2 3 3
 5 2 2
 3 5 4
 4 5 6

• 입력받는 코드

#include <vector>
#include <stdio.h>
using namespace std;

int ver, ed; // 정점, 간선
vector<pair<int,int> > vertex[200];

int main(void){
    scanf("%d %d", &ver, &ed); // 정점 수, 간선 수 입력받기

    for(int i = 0; i < ver; i++){
        int start, end, weight = 0;
        scanf("%d %d %d", &start, &end, &weight);

        vertex[start].push_back(make_pair(end, weight));
        vertex[end].push_back(make_pair(start, weight)); // 무방향 그래프니까 반대 경우도 저장 
    }

}

인접 행렬 (adjacency matrix)

V x V 크기의 2차원 배열로 간선 정보를 저장

• 무향 그래프의 경우: 행렬에 대각선을 그어보면 대칭 모양이 나온다. 대칭 행렬(Symmetric Matrix)
• : 정점 1에서 2, 정점 2에서 1 모두 연결되어 있으므로 1로 표시하고, 연결이 안 된 정점끼리 0으로 표시한다.

• 유향 그래프예를 들어, 정점 6은 가리키고 있는 정점이 5밖에 없다. 정점 6의 인접 정점은 5뿐이다.
• ㅍ
• 
• : 정점 자신이 가리키고 있는 정점에 대해서만 인접해 있다고 표현한다.

vector<vector<bool> > adjacent; // 유향 그래프
vector<vector<int> > adjacent_weight; // 가중치 유향 그래프

• 가중치 가진 유향 그래프
  
• : 간선의 정보를 bool 값 대신 정수나 실수 변수로 쓰면 된다.

인접 리스트와 인접 행렬 표현의 비교

두 방식은 정반대의 특성을 가져서 한 방식의 단점이 다른 방식의 장점이 된다. 구현하려는 알고리즘이나 그래프의 종류에 맞게 사용하자.

• 희소 그래프 : 간선의 수가 V^2 에 비해 적은 그래프
• 밀집 그래프 : 간선의 수가 V^2 에 비례하는 그래프.

그래프와 트리 비교

[참고]

그래프 인접행렬 인접리스트

알고리즘 문제해결전략(도서 종만북 요약)

도움이 되셨다면 '공감'을 눌러주세요 :)