방송대 방통대 자료구조 14강 - 그래프의 개념과 표현 방법 - 요약 노트 시험족보 예상문제 - 올에이클래스

자료구조 14강 - 그래프의 개념과 표현 방법

현실의 복잡한 관계를 정점과 간선으로 추상화하는 그래프의 기본 개념을 학습합니다. 방향·다중·가중 그래프, 인접과 차수, 경로와 사이클 등의 용어를 구분하고 그래프 추상 자료형과 인접 행렬·인접 리스트 표현을 정리합니다.

그래프의 개념

관계를 정점과 간선으로 추상화하기

그래프(graph)는 대상을 정점(vertex, node)으로, 대상 사이의 관계를 간선(edge)으로 나타내는 자료구조입니다. 지하철 노선에서 역을 정점으로, 역을 잇는 노선을 간선으로 표현하거나 도로망·통신망·프로젝트 일정·컴퓨터 네트워크의 연결을 나타낼 수 있습니다.

그래프 G는 하나 이상의 정점을 포함하는 집합 V와 두 정점의 관계를 나타내는 간선의 집합 E로 정의하며 G=(V,E)로 씁니다. 같은 그림이라도 정점과 간선의 집합을 명시하면 그래프의 논리 구조를 정확히 표현할 수 있습니다.

기호	의미
G	그래프 전체
V	정점들의 유한 집합
E	정점 사이의 관계를 나타내는 간선 집합
vᵢ, vⱼ	그래프를 구성하는 개별 정점

추상화의 장점 실제 거리나 지도 모양을 모두 보존하지 않아도 “어떤 대상들이 어떤 관계로 연결되어 있는가”에 집중할 수 있습니다.

방향 그래프와 무방향 그래프

간선에 방향이 있는가

무방향 그래프의 간선은 방향이 없으며 두 정점의 순서를 구별하지 않습니다. 정점 v₁과 v₂를 잇는 간선은 순서 없는 쌍 {v₁,v₂}로 나타냅니다. v₁에서 v₂로 이동할 수 있으면 같은 간선을 이용해 v₂에서 v₁로도 이동할 수 있습니다.

방향 그래프의 간선은 시작점과 끝점이 정해져 있으며 순서쌍 (v₁,v₂)로 나타냅니다. 이는 v₁에서 v₂로 향하는 간선이며, 반대 방향인 (v₂,v₁)과는 다른 간선입니다. 방향 간선은 화살표로 표시합니다.

구분	간선 표기	이동 관계
무방향 그래프	{vᵢ,vⱼ}	양쪽 방향을 구분하지 않음
방향 그래프	(vᵢ,vⱼ)	vᵢ에서 vⱼ로 향함
혼합 그래프	두 표기를 함께 사용	방향 간선과 무방향 간선이 공존

순서 구분 무방향 간선 {v₁,v₂}와 {v₂,v₁}는 같지만, 방향 간선 (v₁,v₂)와 (v₂,v₁)는 서로 다릅니다.

다중 그래프와 가중 그래프

두 정점 사이에 여러 간선이 있는 경우

다중 그래프(multigraph)는 같은 두 정점 사이에 여러 개의 간선을 허용하는 그래프입니다. 방향 다중 그래프는 같은 방향의 간선이 여러 개 존재할 수 있고, 무방향 다중 그래프는 같은 두 정점 쌍을 잇는 무방향 간선이 여러 개 존재할 수 있습니다.

간선에 비용이나 거리를 붙이는 경우

가중 그래프(weighted graph)는 각 간선에 거리, 시간, 비용, 용량 같은 가중치가 지정된 그래프입니다. 가중치는 정점의 연결 여부만이 아니라 연결을 이용하는 비용이나 중요도를 표현합니다. 같은 정점 쌍 사이에도 경로별 비용이 다를 수 있습니다.

구분 포인트 다중 그래프는 “간선의 개수”를 확장하고, 가중 그래프는 “간선에 추가된 값”을 표현합니다. 하나의 그래프가 두 성질을 동시에 가질 수도 있습니다.

완전 그래프와 간선의 최대 개수

완전 그래프(complete graph)는 서로 다른 모든 정점 쌍이 간선으로 연결된 그래프입니다. 루프를 제외하고 n개의 정점을 갖는 단순 무방향 완전 그래프에서는 두 정점을 순서 없이 선택하므로 간선의 수가 조합으로 계산됩니다.

무방향 완전 그래프 간선 수는 nC₂=n(n-1)/2입니다.

단순 방향 완전 그래프에서는 서로 다른 두 정점을 시작점과 끝점으로 순서 있게 선택합니다. 따라서 모든 방향 관계를 허용할 때 가능한 방향 간선 수는 순열로 계산됩니다.

방향 완전 그래프 간선 수는 nP₂=n(n-1)입니다.

예를 들어 정점이 4개라면 무방향 완전 그래프의 간선은 6개이고, 방향 완전 그래프에서 모든 순서쌍을 허용하면 12개입니다.

인접, 차수, 독립 정점

인접과 독립

무방향 그래프에서 두 정점 vₚ와 vᵩ를 잇는 간선이 존재하면 두 정점은 서로 인접한다고 합니다. 방향 그래프에서는 간선의 방향까지 확인해야 합니다. 어떤 간선과도 연결되지 않은 정점은 독립 정점 또는 고립 정점이며, 간선 없이 독립 정점만으로 이루어진 그래프는 널 그래프라고 합니다.

차수

무방향 그래프에서 정점의 차수는 그 정점에 접속한 간선의 수입니다. 방향 그래프에서는 정점으로 들어오는 간선의 수를 진입 차수, 정점에서 나가는 간선의 수를 진출 차수라고 하며 두 값을 합한 것이 해당 정점의 전체 차수입니다.

용어	의미
인접 정점	간선 하나로 직접 연결된 두 정점
독립 정점	어떤 간선과도 연결되지 않은 정점
진입 차수	방향 그래프에서 정점으로 들어오는 간선 수
진출 차수	방향 그래프에서 정점에서 나가는 간선 수
무방향 차수	정점에 접속한 간선 수

경로와 사이클

정점을 연결하는 간선의 연속

경로(path)는 한 정점에서 다른 정점까지 이어지는 간선의 연속입니다. 경로의 길이는 경로에 포함된 간선의 수입니다. 정점의 순서열 또는 간선의 순서열로 나타낼 수 있으며 방향 그래프에서는 모든 간선의 방향을 따라가야 합니다.

구분	조건
단순 경로	경로에 포함된 모든 정점이 서로 다릅니다.
기본 경로	경로에 포함된 모든 간선이 서로 다릅니다.
사이클	시작점과 끝점이 같은 단순 경로입니다.
사이클 그래프	사이클이 존재하는 그래프입니다.

루프(loop)는 한 정점에서 출발하여 자기 자신으로 연결되는 길이 1인 간선입니다. 방향 그래프에 사이클이 하나도 없으면 무사이클 그래프이며, 특히 방향 무사이클 그래프를 DAG(Directed Acyclic Graph)라고 합니다.

그래프와 트리 그래프는 루프·다중 간선·사이클을 허용할 수 있지만, 트리는 계층 구조이며 일반적으로 사이클이 없는 연결 그래프라는 점에서 구별됩니다.

그래프 추상 자료형

그래프 추상 자료형은 표현 방식과 무관하게 그래프가 제공해야 할 연산을 정의합니다. 생성·소멸·복사 같은 기본 연산, 정점과 간선의 삽입·삭제, 탐색과 인접성 확인, 경로 길이 계산, 너비 우선 탐색과 깊이 우선 탐색이 포함됩니다.

연산 범주	대표 연산
생명 주기	Create, Destroy, Copy
구조 변경	InsertVertex, InsertEdge, DeleteVertex, DeleteEdge
질의	Search, IsAdjacent, ExistsPath, PathLength
탐색	BFS, DFS

인접 행렬에 의한 그래프 표현

n×n 행렬로 연결 여부 저장하기

정점이 n개인 그래프는 n×n 인접 행렬로 표현할 수 있습니다. 행 i와 열 j의 원소 aᵢⱼ는 정점 vᵢ에서 vⱼ로 가는 간선이 존재하면 1, 존재하지 않으면 0으로 둡니다. 가중 그래프에서는 간선이 있으면 그 가중치 wᵢⱼ를 저장하고, 없으면 강의록의 기준에 따라 0을 저장합니다.

그래프 종류	인접 행렬의 특징
방향 그래프	aᵢⱼ와 aⱼᵢ가 서로 다를 수 있습니다.
무방향 그래프	aᵢⱼ=aⱼᵢ이므로 주대각선을 기준으로 대칭입니다.
가중 그래프	1 대신 간선의 가중치를 저장합니다.
루프	정점 자기 자신과의 간선이므로 주대각 원소에 나타납니다.

인접 행렬은 두 정점 사이의 간선 존재 여부를 인덱스 한 번으로 확인하기 쉽습니다. 하지만 간선이 적은 희소 그래프에서도 항상 n²개의 공간이 필요합니다.

인접 리스트에 의한 그래프 표현

인접 리스트는 정점마다 헤드 포인터를 두고, 그 정점과 인접한 정점들을 연결 리스트로 저장합니다. 방향 그래프에서는 보통 각 정점에서 나가는 간선의 도착 정점을 해당 리스트에 기록합니다. 무방향 그래프에서는 간선 {u,v}를 u의 리스트와 v의 리스트 양쪽에 기록합니다.

공간 특성 인접 리스트는 정점과 실제 간선에 비례하는 공간을 사용하므로 간선이 적은 희소 그래프에 효율적입니다.

어떤 정점의 모든 이웃을 순회할 때는 해당 정점의 리스트만 따라가면 됩니다. 반면 특정 두 정점이 직접 연결되어 있는지 확인하려면 한 정점의 인접 리스트에서 다른 정점을 찾아야 하므로 정점의 차수에 따라 시간이 달라질 수 있습니다.

비교	인접 행렬	인접 리스트
기본 구조	n×n 배열	정점별 연결 리스트
간선 확인	행·열 위치로 즉시 확인	인접 리스트에서 탐색
이웃 열거	행 전체를 검사	해당 리스트만 순회
적합한 그래프	간선이 많은 밀집 그래프	간선이 적은 희소 그래프

핵심 개념 정리

• 그래프 G=(V,E)는 정점 집합 V와 간선 집합 E로 구성됩니다.
• 무방향 간선은 순서 없는 쌍, 방향 간선은 시작점과 끝점이 있는 순서쌍입니다.
• 완전 그래프의 최대 간선 수는 무방향 n(n-1)/2, 방향 n(n-1)입니다.
• 경로 길이는 간선 수이며, 사이클은 시작점과 끝점이 같은 단순 경로입니다.
• 인접 행렬은 n² 공간으로 연결 확인이 쉽고, 인접 리스트는 희소 그래프에 효율적입니다.

최종 암기 문장 그래프는 “정점과 관계를 간선으로 표현”하며, 행렬은 “빠른 연결 확인”, 리스트는 “실제 이웃 중심 저장”에 강합니다.

예상문제 20선

그래프의 종류와 핵심 용어, 추상 자료형, 인접 행렬·인접 리스트 표현을 확인하는 문제입니다. 답을 선택한 뒤 해설로 판단 근거를 점검하세요.

1. 그래프 G를 구성하는 두 집합은?

① 스택 S와 큐 Q ② 정점 집합 V와 간선 집합 E ③ 부모 집합과 자식 집합 ④ 키 집합과 해시 집합

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
그래프는 G=(V,E)로 정의하며 V는 정점, E는 간선의 집합입니다.

2. 그래프에서 대상 사이의 관계를 나타내는 요소는?

① 정점만 ② 배열 인덱스만 ③ 루트만 ④ 간선

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
정점은 대상을, 간선은 정점 사이의 관계를 나타냅니다.

3. 무방향 간선 {v₁,v₂}에 대한 설명으로 옳은 것은?

① {v₁,v₂}와 {v₂,v₁}는 같은 간선이다. ② v₁에서 v₂ 방향만 허용한다. ③ 두 정점은 인접할 수 없다. ④ 반드시 가중치가 필요하다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
무방향 간선은 정점의 순서를 구별하지 않습니다.

4. 방향 간선 (v₁,v₂)가 나타내는 것은?

① v₂에서 v₁로만 향하는 간선 ② 방향이 없는 간선 ③ v₁에서 v₂로 향하는 간선 ④ 두 정점의 데이터 합

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
순서쌍의 첫 정점이 시작점, 둘째 정점이 끝점입니다.

5. 혼합 그래프의 특징은?

① 간선이 하나도 없다. ② 모든 정점이 고립되어 있다. ③ 방향 간선과 무방향 간선이 함께 존재한다. ④ 가중치가 항상 0이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
혼합 그래프는 두 종류의 간선을 동시에 포함합니다.

6. 다중 그래프에 대한 설명으로 옳은 것은?

① 같은 두 정점 사이에 여러 간선을 허용한다. ② 정점이 하나만 존재한다. ③ 사이클을 절대 허용하지 않는다. ④ 모든 간선이 같은 가중치를 가진다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
다중 그래프는 동일한 정점 쌍을 잇는 복수 간선을 허용합니다.

7. 가중 그래프에서 간선에 저장하는 것은?

① 정점의 부모 주소만 ② 항상 논리값 하나만 ③ 트리의 레벨만 ④ 거리·비용·시간과 같은 가중치

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
가중치는 관계를 이용하는 비용이나 중요도를 수치로 표현합니다.

8. n개 정점을 가진 단순 무방향 완전 그래프의 간선 수는?

① n(n-1) ② n(n-1)/2 ③ n² ④ n-1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
서로 다른 두 정점을 순서 없이 선택하므로 nC₂입니다.

9. n개 정점을 가진 단순 방향 완전 그래프에서 가능한 방향 간선 수는?

① n(n-1) ② n(n-1)/2 ③ n ④ 2n-1

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
시작점과 끝점을 순서 있게 선택하므로 nP₂입니다.

10. 독립 정점의 정의는?

① 모든 정점과 연결된 정점 ② 진출 차수가 항상 1인 정점 ③ 루프만 두 개 가진 정점 ④ 어떤 간선과도 연결되지 않은 정점

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
독립 또는 고립 정점은 다른 간선에 접속하지 않습니다.

11. 방향 그래프에서 정점으로 들어오는 간선 수를 무엇이라 하는가?

① 진출 차수 ② 진입 차수 ③ 경로 길이 ④ 그래프 차원

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
진입 차수는 해당 정점을 끝점으로 하는 간선 수입니다.

12. 방향 그래프에서 정점에서 나가는 간선 수를 무엇이라 하는가?

① 진입 차수 ② 사이클 수 ③ 진출 차수 ④ 정점 높이

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
진출 차수는 해당 정점을 시작점으로 하는 간선 수입니다.

13. 경로의 길이는 무엇으로 계산하는가?

① 정점 데이터의 합 ② 그래프 전체 정점 수 ③ 인접 행렬의 행 수만 ④ 경로에 포함된 간선의 수

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
강의록에서 경로 길이는 이어진 간선 개수입니다.

14. 단순 경로의 조건은?

① 경로상의 모든 정점이 서로 다르다. ② 모든 간선의 가중치가 같다. ③ 시작점과 끝점이 항상 같다. ④ 간선이 하나도 없다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
단순 경로는 정점을 반복하여 방문하지 않습니다.

15. 사이클의 정의로 옳은 것은?

① 항상 길이가 0인 경로 ② 모든 정점이 다른 열린 경로 ③ 시작점과 끝점이 같은 단순 경로 ④ 간선이 없는 그래프

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
사이클은 출발점으로 되돌아오는 닫힌 단순 경로입니다.

16. 루프에 대한 설명으로 옳은 것은?

① 서로 다른 세 정점을 연결하는 경로 ② 한 정점에서 출발해 자기 자신으로 연결되는 길이 1의 간선 ③ 항상 길이 2인 사이클 ④ 방향 그래프에는 존재할 수 없는 간선

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
루프는 시작점과 끝점이 동일한 하나의 간선입니다.

17. DAG의 의미는?

① 모든 정점이 연결된 무방향 그래프 ② 사이클이 없는 방향 그래프 ③ 가중치가 없는 다중 그래프 ④ 루프만 있는 그래프

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②
DAG는 Directed Acyclic Graph의 약자로 방향 무사이클 그래프입니다.

18. 정점이 n개인 그래프의 인접 행렬 크기는?

① n×1 ② 간선 수×1 ③ 항상 2×2 ④ n×n

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④
행과 열이 각각 정점에 대응하므로 n×n 행렬입니다.

19. 무방향 그래프의 인접 행렬이 갖는 특징은?

① 항상 상삼각 원소만 1이다. ② 모든 행이 서로 다르다. ③ 주대각선을 기준으로 대칭이다. ④ 대각 원소만 간선을 나타낸다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③
무방향 연결은 양쪽 관계가 같아 aᵢⱼ=aⱼᵢ입니다.

20. 간선이 적은 희소 그래프에 일반적으로 더 효율적인 표현은?

① 인접 리스트 ② 항상 인접 행렬만 ③ 완전 이진 트리 배열 ④ 스택 하나

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①
인접 리스트는 실제 존재하는 이웃 관계 중심으로 저장하여 희소 그래프의 공간을 절약합니다.