Graph

Graph란?

그래프는 비선형적 자료구조입니다. 그래프는 데이터를 담는 정점과 정점들을 연결하는 간선으로 구성되며 객체(정점) 간의 관계를 표현할 수 있습니다.

용어

• 연결(Incident): 정점과 간선 사이의 관계를 나타내는 용어로 간선이 정점에 연결되어 있다고 말합니다.
• 인접(Adjacent): 정점 사이의 관계를 나타내는 용어로 두 정점이 동일한 간선에 연결되어 있다면 두 정점이 인접해 있다고 말합니다.
• 유향 그래프(Directed Graph): 방향성이 있는 간선들로 이루어진 그래프를 말합니다.
• 무향 그래프(Undirected Graph): 방향성이 없는 간선들로 이루어진 그래프를 말합니다.
• 가중치 그래프(Weighted Graph): 그래프를 구성하는 간선에 가중치가 존재하는 그래프를 말합니다.
• 정점의 차수(Degree): 무향 그래프에서 정점 V 와 인접한 정점의 수를 정점 V 의 차수라고 합니다.
• 진입 차수(In-Degree): 유향 그래프에서 다른 정점에서 정점 V 로 향하는 방향을 가진 간선의 수를 정점 V 의 진입 차수라고 합니다.
• 진출 차수(Out-Degree): 유향 그래프에서 정점 V 에서 다른 정점으로 향하는 방향을 가진 간선의 수를 정점 V 의 진출 차수라고 합니다.
• 경로(Path): 한 정점에서 다른 한 정점으로 향하는 연속된 간선들의 Sequence를 말합니다. Path 중에서 한 번 방문한 정점은 다시 방문하지 않는 경로를 Simple Path라고 합니다.
• 도달 가능(Reachable): 정점 V 에서 정점 W 로의 경로가 존재하는 경우 정점 W 는 정점 V 에서 도달 가능하다라고 합니다.
• Connected Graph: 모든 정점 사이의 경로가 존재하는 그래프를 말합니다. 유향 그래프에서 모든 정점 사이의 경로가 존재하는 그래프는 특별히 Strongly Connected Graph라고 합니다.
• Cycle: 출발 정점과 도착 정점이 같은 경로를 Cycle이라고 합니다. Cycle이 없는 그래프는 Acyclic Graph라고 합니다.

그래프의 구현

인접 리스트

인접 리스트는 각 정점에 인접한 정점들을 리스트에 저장하여 그래프를 구현하는 방식입니다.

인접 행렬

인접 행렬은 2차원 배열로 그래프를 구현하는 방식입니다. 2차원 배열의 각 원소는 두 정점이 인접한지 여부 혹은 두 정점을 연결하는 간선의 가중치를 나타냅니다.

비교

	인접 리스트	인접 행렬
메모리	O(E)	O(V^2)
areAdjacent(x, y)	O(min(degree(x), degree(y))	O(1)
incidentEdges(x)	O(degree(x))	O(V)

그래프 순회

그래프의 순회란 어떤 한 정점에서 시작하여 그래프의 모든 정점을 한 번씩 방문하는 것을 말합니다.

DFS (Depht First Search)

• A -> B -> D -> G -> E -> H -> C -> F

1. 모든 정점과 간선의 방문 여부 초기화
2. 그래프 속 한 정점 V에 대해 DFS 호출
3. DFS의 대상이 된 정점 방문
4. V와 연결된 간선을 찾고 각 간선의 flag가 unexplored인지 확인
5. unexplored라면 건너편 정점 W의 flag 확인
6. W를 방문하지 않았다면 정점 W에 대해 DFS 호출
7. W를 이미 방문했다면 해당 간선의 flag를 back으로 변경
8. 그래프의 모든 정점이 처리될 때까지 3번부터 위 과정 반복

BFS (Breath First Search)

• A -> B -> C -> D -> E -> F -> G -> H

1. 모든 정점과 간선의 방문 여부 초기화
2. 그래프 속 한 정점을 queue에 삽입하면서 방문 처리
3. queue의 front에 있는 정점 V를 꺼내 V와 연결된 간선을 찾음
4. 각 간선의 flag가 unexplored인지 확인 후 건너편 정점 W의 방문 여부 확인
5. 방문하지 않았다면 queue에 삽입하면서 방문 처리
6. 이미 방문했다면 해당 간선의 flag를 back으로 변경
7. 그래프의 모든 정점이 처리될 때까지 3번부터 위 과정 반복

시간복잡도

DFS와 BFS 모두 인접 리스트로 구현한 경우엔 O(V + E) 시간복잡도를 갖고 인접 행렬로 구현한 경우엔 O(V^2) 시간복잡도를 갖습니다.