그래프(Graph) 자료구조

---

멘토링

 

그래프의 개념과 구성 요소에 대한 개별적인 이해도 중요하지만, 
최단 경로 및 최소 신장 트리 알고리즘과 연계하여 
그래프와 트리를 학습하시길 권고드립니다.

 

최단 경로 알고리즘

다익스트라(Dijkstra), 벨만-포드(Bellman-Ford),
플로이드 와샬(Floyd Warshall), A* 알고리즘

 

최소 신장 트리 알고리즘

크루스컬(Kruskal), 프림(Prim) 알고리즘

 

그래프(Graph)의 개념

 

객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합으로,
연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조

[두음] 그정간다

그래프, 정점, 간선, 다:다 관계 표현

 

그래프의 종류

 

무방향 그래프, 방향 그래프, 완전 그래프, 가중 그래프, 
유향 비순환 그래프(DAG, Directed Acyclic Graph)

 

DAG 경우 정보관리기술사 시험에 위상정렬과 연계되어 출제된바 있으니 관심있게 보시길 바랍니다.

 

출처 : 탑싯 에센스

 

그래프의 구현 방법

 

출처 : 탑싯 에센스

 

인접 행렬 :

 

두 노드간의 엣지 상태를 행렬 형태로 표현

순차 자료구조를 이용한 그래프 구현 방식으로,
그래프의 두 정점을 연결한 간선의 유무를 2차원 배열을 사용한 행렬로 저장하는 방식

[ 그래프 구현 방식 ] 우측 그림에서 두 정점 A와 B, A와 C 간 무방향 간선이 존재하는데,
A행 B열의 1 값이 의미하는 바는 A 정점과 B 정점간에 간선이 존재함을 나타내는 것임

무방향 그래프 경우 하나의 간선이 존재할 때 두 정점간 2개의 관계가 존재하므로
3개의 정점 A,B,C간 3개의 간선이 있는 경우 총 6개의 관계가 존재하며
행렬의 우하향 대각선(AA,BB,CC) 기준으로 대칭 구조를 가짐

인접 리스트 : 

 

각 노드 별로 연결되어 있는 노드들만 표현

연결 자료구조를 이용한 그래프 구현방식으로,
각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트로
각 정점의 차수만큼 노드를 연결하는 방식

정점 기준 간선으로 연결된 정점 정보를 저장하는 방식으로 이해하시면 될 듯 합니다. 

A 정점은 B 정점과 C 정점을 간선으로 연결하고 있고,
B 정점은 A 정점과 C 정점을 간선으로 연결하고 있고,
C 정점은 A 정점과 B 정점을 간선으로 연결하고 있습니다.

 

간선 리스트 : 

 

엣지만을 리스트 형태 또는 배열 형태로 저장하여 표현
정점간의 간선의 정보를 저장

  
예시는 무방향 그래프이므로 총 6개의 간선이 존재합니다. 

(A B), (B A)
(A C), (C A)
(B C), (C B)

 

그래프의 탐색

DFS(Depth First Search) : 깊이 우선 탐색

BFS(Breadth First Search) : 너비 우선 탐색

프로그래밍 경험이 없으신 경우에는 좀 어려울 수 있는데,
스택을 이용한 DFS, 큐를 이용한 BFS 구현 방식에 대한 Pseudo Code 까지는 알고 있으면 좋습니다.

 

기출 문제

 

(관리 125-4-4)
방향성 비순환 그래프(Directed Acyclic Graph)에 대하여 다음 물음에 답하시오.

가. 방향성 비순환 그래프의 개념과 특징
나. 아래 방향성 비순환 그래프에 대하여 위상정렬(Topology Sort)을 실시하고 결과값 제시

 

(관리 123-4-6)
다음에 대하여 설명하시오.

가. 최단 경로 알고리즘의 유형 4가지
나. 다음 그래프에서 4가지 알고리즘 계산방법
- A, B, C, D, E 5개 노드로 구성된 그래프(A가 출발지, E가 목적지임)
다. "나"의 4가지 알고리즘 계산결과 비교

 

(관리 96-1-1)
그래프를 이용하여 최적 경로를 찾는 데 이용되는 최소 신장 트리(Minimal spanning tree) 알고리즘에 대하여 설명하시오.

 

(관리 84-3-5)
다음 그래프에 Dijkstra가 제안한 최소 비용(least-cost) 경로 설정 알고리즘이 적용되는 과정을 제시하시오.
(그래프의 에지옆 숫자는 비용을 의미함)

 

(관리 116-4-2)
아래 그래프에서 최소 신장 트리(MST: Minimum Spanning Tree)를 구하는 과정을 2개의 알고리즘을 이용하여 설명하시오.
가. 크루스컬(Kruskal) 알고리즘
나. 프림(Prim) 알고리즘

 

참고 자료

탑싯 에센스 - 소프트웨어 개발

https://godgod732.tistory.com/15

[알고리즘] - 그래프의 표현 방법 #8

https://leejinseop.tistory.com/43

[자료구조] 그래프(Graph)의 개념 설명

https://sarah950716.tistory.com/12

[그래프] 인접 행렬과 인접 리스트

인접행렬과 재귀를 통한 DFS 구현
https://code-lab1.tistory.com/15

[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

스택이용 DFS, 큐 이용 BFS 구현
https://sweetday-alice.tistory.com/176

[C++] DFS와 BFS 구현하기

행복한 일상 되세요.