그래프 자료구조 개념 정리

* 바킹독 선생님의 글(https://blog.encrypted.gg/1016), '파이썬 알고리즘 인터뷰', 영문 위키피디아 등에서 참고함. 

 

정의

정점과 간선으로 이루어진 자료구조

 

 

용어

• 정점(Vertex)
• 간선(Edge)
• 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph): 간선의 방향이 없는 / 있는 그래프
• 차수(Degree): 간선으로 연결된 이웃된 정점의 개수
  • outdegree와 indegree: 방향 그래프에서 자기에서 나가는 간선의 개수 / 자기한테 들어오는 간선의 개수

 

• 순환 그래프(Cyclic Graph)와 비순환 그래프(Acyclic Graph): cycle이 있는 그래프 / cycle이 없는 그래프
• 완전 그래프(Complete Graph): 모든 서로 다른 두 정점 쌍이 간선으로 연결된 그래프
• 연결 그래프(Connected Graph): 임의의 두 정점 사이에 경로가 존재하는 그래프
• 단순 그래프(Simple Graph): 두 정점 사이의 간선이 1개 이하이며 loop(자기 자신에서 나가서 자기 자신으로 들어오는 간선)이 없는 그래프

 

 

표현 방법

1. 인접 행렬

정점이 V개 있을 때, V*V int 행렬 graph을 선언한다.

• Undirected graph인 경우: 정점 i와 정점 j 사이에 간선이 있을 경우 graph[i][j], graph[j][i]에 1을 넣는다.
• Directed graph: 정점 i에서 정점 j로 가는 간선이 있을 경우 graph[i][j]에 1을 넣는다.

 

2. 인접 리스트

정점이 V개 있을 때, 리스트 V개를 선언한다. 각각의 리스트를 1, 2, 3, ... , V라 하여, i에서 정점 j로 가는 간선이 있을 경우 리스트 i에 j를 삽입한다. JAVA에서는 ArrayList<ArrayList<Integer>>() 로 구현한다. 일반적으로 정점은 1에서 시작하므로, 맨 처음 index에는 빈 List를 넣어주면 관리가 편리하다.

 

 

※ 두 표현의 효율 비교 (중요!)

	인접 행렬	인접 리스트
공간 복잡도	O(V^2)	O(V+E)
정점 U, V가 연결되어 있는지 확인	O(1)	O(min(deg(U), deg(V))
정점 V와 연결된 모든 정점을 확인	O(V)	O(deg(V))
언제 사용할까?	두 점의 연결 여부를 자주 확인할 때 E가 V^2랑 가까울 때	특정 정점에 연결된 모든 정점을 확인할 때 E가 V^2보다 훨씬 작을 때

BFS, DFS을 포함하여, 일반적인 경우 두 정점이 연결되어있는 지 확인하는 경우보단 특정 정점에서 연결된 모든 정점을 확인하는 일이 훨씬 많으며, V가 크면 인접 행렬을 사용하면 메모리 초과가 발생하기에 인접 리스트를 사용하는 것이 좋다.

 

 

그래프에서의 BFS, DFS

 

1) BFS 유사코드: 큐 사용

인접 리스트에서 시간 복잡도 O(V+E), 인접 리스트에서 O(V^2)

procedure BFS(G, root) is
	let Q be a queue
	label root as explored
	Q.enqueue(root)
	while Q is not empty do
		v := Q.dequeue()
		if v is the goal then
			return v
		for all edges from v to w in G.adjacentEdges(v) do
			if w is not labeled as explored then
				label w as explored
				Q.enqueue(w)

 

 

2) DFS 유사코드: 스택 사용(비재귀)

인접 리스트에서 시간 복잡도 O(V+E), 인접 리스트에서 O(V^2)

procedure DFS_iterative(G, v) is
    let S be a stack
    S.push(v)
    while S is not empty do
        v = S.pop()
        if v is not labeled as discovered then
            label v as discovered
            for all edges from v to w in G.adjacentEdges(v) do 
                S.push(w)

 

3) DFS 유사코드: 재귀 사용

procedure DFS(G, v) is
    label v as discovered
    for all directed edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)

 

※ 바킹독 선생님의 comment

1. 재귀 DFS가 코드도 간결하고 사용도 편리하나, 메모리 중 stack 영역에 함수 데이터가 쌓인다. 일반적인 저지 사이트(백준, 프로그래머스 등)에서는 스택 메모리 제한을 256 or 512MB 으로 하여 널널하나, SWEA처럼 1MB 정도로 스택 메모리를 작게 제한하는 경우에는 런타임 에러가 발생할 수 있다.
2. 비재귀 DFS는 엄밀하게 말해서 출력보다 스택에 쌓아두는 작업을 먼저하기에, 우리가 기대하는 대로의 DFS 움직임이 아니다. 따라서 DFS의 의미를 살려서 풀어야 하는 문제에서는 틀릴 수도 있으나, 코딩테스트 수준에서는 그럴 일이 거의 없을 것이다.

 

연습문제

https://www.acmicpc.net/workbook/view/306

문제집: Graph (jcdgods)

https://programmers.co.kr/learn/courses/30/parts/14393

프로그래머스