알고리즘 : 그래프 (Graph) (2)

그래프의 표현

그래프를 컴퓨터가 처리하게 만들기 위해서는 그래프를 적절한 자료구조로 변환해 주어야 한다.

표현 방식에는 인접행렬(adjaceny matrix)와 인접리스트(adjaceny list)가 있다.

 

인접 행렬 그래프 (adjaceny matrix)

모든 정보를 저장하는 방식이다.

직관적이며 쉽게 구현이 가능하지만 불필요한 정보 저장이 많다. 그래프의 크기가 커지면 메모리 초과가 발생할 수도 있다.

보통 2차원 배열을 사용하여 구현한다.

정점의 개수가 총 n개이면 인접행렬은 nxn의 크기를 갖는다. 무방향 그래픠 경우 대각선을 중심으로 대칭이며 가중치가 있을 경우 1이 아닌 가중치를 저장하게 된다.

 

 

인접 리스트 그래프 (adjaceny list)

갈 수 있는 곳만 저장하는 방식이다.

필요한 정보만 저장하므로 메모리를 절약할 수 있으나 인접행렬에 비해 다소 어렵다.

보통 리스트와 벡터 등의 자료구조를 이용하여 이동가능한 정점을 저장한다.

각 정점에 인접한 정접들을 n개의 연결리스트로 표현한 방식이다. 무방향 그래프의 경우 하나의 간선 당 2개의 노드가 생기게 된다. 예를 들어 위 그림에서 세번째 그래프를 보면 <b, c> 간선을 표현하는 건 노드 b에 표현되어 있을 뿐 c에는 표현되어 있지 않다. 하지만 무방향이었다면 b, c 모두에 <b, c> 간선이 표현되어 있을 것이다.

 

하나의 그래프를 나타내는 방식을 비교할 수 있는 그림이다.

 

vector<int> graph[9];
int main() {
	// 노드 1에 연결된 노드 정보 저장
	graph[1].push_back(2);
	graph[1].push_back(3);
	graph[1].push_back(8);

    // 노드 2에 연결된 노드 정보 저장 
    graph[2].push_back(1);
    graph[2].push_back(7);

    // 노드 3에 연결된 노드 정보 저장 
    graph[3].push_back(1);
    graph[3].push_back(4);
    graph[3].push_back(5);

    // 노드 4에 연결된 노드 정보 저장 
    graph[4].push_back(3);
    graph[4].push_back(5);

    // 노드 5에 연결된 노드 정보 저장 
    graph[5].push_back(3);
    graph[5].push_back(4);

    // 노드 6에 연결된 노드 정보 저장 
    graph[6].push_back(7);

    // 노드 7에 연결된 노드 정보 저장 
    graph[7].push_back(2);
    graph[7].push_back(6);
    graph[7].push_back(8);

    // 노드 8에 연결된 노드 정보 저장 
    graph[8].push_back(1);
    graph[8].push_back(7);
}

c++ vector을 이용해서 구현하면 이렇게 된다. (list 방식)

 

 

시간복잡도

1. 인접행렬

임의의 두 노드 (i, j)가 주어졌을 때 인접해있는지 확인 : O(1)

임의의 노드 i가 주어졌을 때 인접한 모든 노드 찾기 : O(n)

 

2. 인접리스트

임의의 두 노드 (i, j)가 주어졌을 때 인접해있는지 확인 : O(deg(i))

전체에서 i번째를 찾고 여기서 j가 있는지 확인해야 한다. 여기서 i번째 노드의 차수를 deg(i)라고 한다.

임의의 노드 i가 주어졌을 때 인접한 모든 노드 찾기 : O(deg(i))

i번째 노드에 속한 모든 값을 확인한다. 여기서 i번째 노드의 차수를 deg(i)라고 한다.

 

 

공간복잡도

1. 인접행렬

노드 수 x 노드 수만큼의 행렬이 필요하다. 즉 O(n^2)이 된다.

 

2. 인접리스트

노드 수를 V, 엣지 수를 E라고 했을 때 두 값을 합친 만큼 필요하다. 즉 O(V+E)가 된다.

 

 

 

자료구조의 선택

노드 수보다 엣지 수가 많은 dense graph는 인접행렬, 노드 수보다 엣지 수가 적은 sparse graph는 인접리스틀 쓰는 것이 좋다.

위에서 설명했듯이 인접행렬은 노드수가 많아지면 많아질수록 단점이 심해지기 때문이다. 

 

 

그래프 기본 알고리즘

다음은 BFS, DFS에 대해 알아볼 예정이다. BFS, DFS 관련 포스팅을 새로 만들 예정이지만 아주 간단하게 다뤄보도록 하겠다.

 

BFS는 너비우선탐색 알고리즘으로 시작 정점을 방문하고 인접한 모든 정점을 우선 방문하는 것이다.

DFS는 시작 정점을 방문하고 자식을 모두 탐색한 후 연결된 노드가 없으면 한 단계 이전으로 돌아가 반복한다.

 

위 그림은 트리 구조인데 BFS랑 DFS가 항상 트리구조의 그래프에만 적용되는 것은 아니다. 다만 이해를 위해 트리 구조 그림을 사용하였다.

트리는 두 개의 노드 사이 반드시 1개의 경로만을 가지고 사이클이 존재하지 않는 방향 그래프이다. 

 

 

 

 

 

 

참고 티스토리

 

https://ttl-blog.tistory.com/954#%F0%9F%A7%90%C2%A0Simple%20Graph%C2%A0-1

[알고리즘] 그래프 (1) - 그래프의 기본 용어

https://yjg-lab.tistory.com/147

[자료구조] 그래프(Graph) 표현 | 인접 행렬, 인접 리스트, 인접 배열

https://bigsong.tistory.com/33

[자료구조] 그래프와 트리(Graph, Tree)