방송대 자료구조 14강 : 그래프의 개념과 인접 표현

방송대 자료구조 14강: 그래프의 개념과 인접 표현

도로망, 선수 과목, 컴퓨터 네트워크는 겉모습이 달라도 “대상과 관계”로 바꾸면 같은 그래프 언어로 다룰 수 있습니다. 이 글은 관계에서 정점과 간선을 골라내는 단계부터 방향·가중치·경로를 판별하는 기준, 그래프 추상 자료형의 연산, 인접 행렬과 인접 리스트로 저장하는 방법까지 하나의 변환 흐름으로 연결합니다.

관계 데이터를 그래프로 바꾸려면 네 가지를 먼저 결정한다

그래프는 복잡한 대상을 그림처럼 그리는 기법에 그치지 않습니다. 분석하려는 대상을 정점으로, 대상 사이의 관계를 간선으로 추상화한 자료구조입니다. 같은 현실도 무엇을 정점과 간선으로 보느냐에 따라 서로 다른 그래프가 됩니다. 지하철 노선을 예로 들면 역을 정점, 역 사이의 직접 연결을 간선으로 볼 수 있습니다. 반면 환승 관계만 분석한다면 노선 자체를 정점으로 보고 두 노선의 환승 가능성을 간선으로 삼을 수도 있습니다.

그래프를 만들 때는 그림부터 그리지 말고 다음 네 질문에 답해야 합니다. 첫째, 구별해야 할 대상은 무엇인가? 둘째, 어떤 관계만 간선으로 인정할 것인가? 셋째, 관계의 순서나 흐름이 중요한가? 넷째, 거리·시간·비용처럼 간선마다 보존해야 할 수치가 있는가? 이 답이 각각 정점 집합, 간선 집합, 방향성, 가중치를 정합니다.

추상화 순서: 대상 선택 → 관계의 기준 확정 → 방향 유무 판정 → 가중치 의미 확정의 순서로 모델을 만듭니다. “가깝다”처럼 관계 기준이 모호하면 간선 집합 자체가 달라지므로, 표현 방법을 고르기 전에 관계의 조건부터 분명히 해야 합니다.

G=(V, E)는 대상과 관계를 분리해 기록한다

그래프 G는 정점의 유한 집합 V와 간선의 집합 E로 정의하여 G=(V, E)로 씁니다. 예를 들어 네 작업 지점을 V={A, B, C, D}로 두고 직접 이동 가능한 관계를 E={{A,B}, {A,C}, {B,D}}로 두면 무방향 그래프가 됩니다. 중괄호로 나타낸 간선 {A,B}는 A와 B의 순서를 구분하지 않습니다.

흐름이 한쪽으로만 가능하면 방향 그래프를 사용합니다. 이때 간선은 순서쌍 (A,B)로 나타내며 A에서 B로 가는 간선과 B에서 A로 가는 간선은 서로 다릅니다. 한 그래프에 방향 간선과 무방향 간선이 함께 있으면 혼합 그래프입니다. 방향성은 단순한 화살표 장식이 아니라 도달 가능성과 경로의 성립 여부를 바꾸는 자료입니다.

종류	간선의 뜻	판별할 핵심	학습용 상황
무방향 그래프	{u,v}, 순서 없음	관계를 양쪽에서 동일하게 볼 수 있는가	서로 연결된 통신 장비
방향 그래프	(u,v), u에서 v로 향함	출발과 도착을 바꾸어도 같은 관계인가	선수 과목의 이수 순서
혼합 그래프	두 종류의 간선이 공존	관계별 방향성이 서로 다른가	일방·양방 통행이 섞인 이동망
가중 그래프	간선에 수치가 붙음	수치가 거리·비용·시간 중 무엇인가	이동 시간까지 기록한 도로망
다중 그래프	같은 정점 쌍에 여러 간선 허용	관계가 여러 개 존재할 수 있는가	두 도시 사이의 여러 교통편

루프는 한 정점에서 출발해 같은 정점으로 연결되는 길이 1의 간선입니다. 다중 그래프와 루프를 허용할지 여부는 그래프 모델의 규칙에 따라 달라집니다. 따라서 “정점 수만 알면 간선 수를 언제나 같은 공식으로 계산할 수 있다”는 생각은 위험합니다. 최대 간선 수 공식은 서로 다른 정점 사이에 중복 간선과 루프가 없는 단순한 경우를 전제로 합니다.

간선 수 공식은 방향과 중복 허용 조건을 함께 읽는다

정점이 n개이고 서로 다른 두 정점 사이에 간선을 하나만 허용하는 무방향 그래프에서는 정점 두 개를 순서 없이 고릅니다. 따라서 가능한 간선의 최대 개수는 nC2=n(n-1)/2입니다. 방향 그래프에서는 출발 정점과 도착 정점의 순서가 중요하므로 서로 다른 정점 두 개를 순서 있게 고르고 최대 nP2=n(n-1)개가 됩니다.

예를 들어 정점이 5개라면 무방향 그래프의 최대 간선 수는 5×4÷2=10개이고, 방향 그래프의 최대 간선 수는 5×4=20개입니다. 무방향에서는 A-B와 B-A를 하나로 세지만 방향에서는 A→B와 B→A를 각각 세기 때문에 정확히 두 배가 됩니다. 루프나 평행 간선을 허용하면 이 계산의 전제가 깨집니다.

모든 서로 다른 정점 쌍이 간선으로 연결된 그래프를 완전 그래프라고 합니다. 반대로 정점은 있지만 간선 집합이 공집합인 그래프는 널 그래프입니다. 널 그래프의 각 정점은 다른 어떤 정점과도 인접하지 않는 독립 정점입니다.

공식 선택의 함정: 문제에 정점 수만 보인다고 바로 n(n-1)/2를 쓰지 않습니다. 방향 유무 → 루프 허용 여부 → 같은 정점 쌍의 중복 간선 허용 여부를 먼저 확인한 뒤 공식을 선택해야 합니다.

인접은 한 칸의 관계이고 경로는 이어지는 관계의 열이다

무방향 그래프에서 간선 {u,v}가 존재하면 u와 v는 서로 인접합니다. 방향 그래프에서는 u에서 v로 가는 간선 (u,v)가 있더라도 반대 방향 간선이 있다는 뜻은 아닙니다. 방향 그래프의 한 정점으로 들어오는 간선 수를 진입 차수, 그 정점에서 나가는 간선 수를 진출 차수라고 하며, 두 수의 합이 그 정점의 차수가 됩니다. 무방향 그래프의 차수는 그 정점에 연결된 간선 수입니다.

경로는 한 간선의 끝 정점이 다음 간선의 시작 정점으로 이어지는 간선의 열이며, 보통 그 간선들이 지나는 정점의 순서로 표시합니다. 경로의 길이는 방문한 정점 수가 아니라 경로에 포함된 간선 수입니다. A-B-C-D라면 정점은 네 개지만 간선은 세 개이므로 길이는 3입니다.

용어	중복을 금지하는 대상	판별 방법
단순 경로	경로의 모든 정점	정점 순서에 같은 정점이 다시 등장하지 않는지 본다
기본 경로	경로의 모든 간선	같은 간선을 두 번 사용하지 않았는지 본다
사이클	출발과 도착을 제외한 단순성	출발점과 도착점이 같은 단순 경로인지 본다

단순 경로이면 같은 정점을 다시 방문하지 않으므로 같은 간선도 다시 사용할 수 없습니다. 따라서 단순 경로는 기본 경로이지만, 기본 경로가 항상 단순 경로인 것은 아닙니다. 서로 다른 간선을 사용하면서도 어떤 정점을 다시 방문할 수 있기 때문입니다. 두 정의를 외울 때는 “단순은 정점, 기본은 간선”이라는 검사 대상을 먼저 구분하는 것이 안전합니다.

사이클의 유무가 트리와 DAG의 경계를 만든다

사이클이 하나 이상 존재하면 사이클 그래프이고, 사이클이 없으면 무사이클 그래프입니다. 방향 그래프에서 방향을 따라 출발점으로 돌아오는 사이클이 없는 그래프를 DAG, 즉 방향 무사이클 그래프라고 합니다. 간선을 무시하고 그림만 둥글게 보인다고 사이클인 것은 아닙니다. 방향 그래프에서는 모든 화살표를 올바른 방향으로 따라가 실제로 출발 정점에 돌아와야 합니다.

트리는 연결된 무사이클 무방향 그래프입니다. 무사이클이라는 조건만으로는 트리가 되지 않습니다. 정점들이 여러 묶음으로 끊어져 있으면 각각이 트리일 수는 있어도 전체는 하나의 트리가 아닙니다. 또한 DAG는 방향 그래프이므로 그 자체를 무방향 트리와 같은 개념으로 취급할 수 없습니다.

오개념 교정: “사이클이 없다”는 사실은 트리의 필요조건일 뿐 충분조건이 아닙니다. 무방향인지, 모든 정점이 하나의 연결 성분에 속하는지까지 확인해야 트리라고 결론낼 수 있습니다.

추상 자료형은 그래프가 해야 할 일을 연산으로 분리한다

그래프의 추상 자료형은 정점과 간선의 유한 집합을 객체로 보고, 그 내부 저장 방식과 무관하게 제공해야 할 연산을 정의합니다. 그래프를 인접 행렬로 저장하든 인접 리스트로 저장하든 사용자는 그래프 생성, 정점·간선 삽입과 삭제, 인접 여부 확인 같은 동일한 기능을 요청할 수 있어야 합니다.

연산 묶음	강의의 대표 연산	연산이 답하는 질문
생명 주기	GraphCreate, DestroyGraph, 그래프 복사	그래프를 만들고 복제하고 메모리를 반납하는가
구조 변경	InsertVertex, InsertEdge, DeleteVertex, DeleteEdge	대상과 관계를 어떻게 추가하거나 제거하는가
조회	Search, IsAdjacent, ExistPath, PathLength	정점·인접·경로와 길이를 어떻게 확인하는가
순회	BFS, DFS	연결된 정점을 어떤 순서로 방문하는가

여기서 중요한 구분은 IsAdjacent(u,v)와 ExistPath(u,v)입니다. 인접 여부는 두 정점 사이에 직접 간선이 있는지 묻지만, 경로 존재 여부는 다른 정점을 거쳐서라도 도달할 수 있는지를 묻습니다. A→B와 B→C가 있을 때 A와 C는 직접 인접하지 않지만 A에서 C로 가는 경로는 존재합니다.

인접 행렬은 행을 출발점, 열을 도착점으로 읽는다

정점이 n개인 그래프의 인접 행렬은 n×n 행렬입니다. 방향 그래프에서 원소 aij는 정점 i에서 정점 j로 가는 간선이 있으면 1, 없으면 0입니다. 즉 행은 출발 정점, 열은 도착 정점입니다. 이 원칙을 놓치면 방향을 반대로 읽게 됩니다.

학습용 예로 배송 단계 V={A,B,C,D}와 방향 간선 E={(A,B),(A,C),(B,D),(C,B),(C,D)}를 생각해 봅시다. A에서 B와 C로, B에서 D로, C에서 B와 D로 이동할 수 있습니다. 정점 순서를 A, B, C, D로 고정하면 인접 행렬은 다음과 같습니다.

출발＼도착	A	B	C	D	행의 합
A	0	1	1	0	2
B	0	0	0	1	1
C	0	1	0	1	2
D	0	0	0	0	0

행 A의 B열과 C열이 1이므로 A의 진출 차수는 2입니다. 열 B에는 A행과 C행에 1이 있으므로 B의 진입 차수도 2입니다. A행 D열은 0이어서 A와 D는 직접 인접하지 않지만, A→B→D와 A→C→D 같은 길이 2의 경로는 존재합니다. 이렇게 행렬 한 칸은 직접 관계를, 여러 칸의 연결은 경로를 뜻합니다.

무방향 그래프에서는 {i,j}가 있으면 aij와 aji가 함께 1이 되므로 주대각선을 기준으로 대칭입니다. 방향 그래프는 두 방향의 간선이 모두 있을 때만 대응하는 두 칸이 함께 1이므로 일반적으로 대칭이 아닙니다. 루프가 없으면 주대각선은 모두 0이고, 루프가 있으면 해당 정점의 대각 원소가 1이 됩니다.

가중 행렬은 1 대신 간선의 값을 보존한다

가중 그래프의 인접 행렬에서는 간선이 있는 위치에 1 대신 가중치 wij를 저장합니다. 앞의 배송 예에서 A→B가 4분, A→C가 7분, B→D가 5분, C→B가 2분, C→D가 3분이라고 가정하면 행렬의 해당 위치에 4, 7, 5, 2, 3을 넣습니다. 이 예에서는 모든 가중치가 양수라는 조건 아래 0을 “간선 없음”으로 사용합니다.

가중치는 맥락을 잃으면 의미가 달라질 수 있습니다. 비용 그래프의 3과 시간 그래프의 3은 같은 숫자라도 최적화의 뜻이 다릅니다. 또한 방향 가중 그래프에서 A→B의 값과 B→A의 값은 서로 다를 수 있습니다. 따라서 행렬을 만들기 전에 정점 순서, 간선 방향, 가중치의 단위, 간선이 없음을 표시하는 값을 함께 선언해야 합니다.

행렬 검산: 정점 순서를 고정했는가 → 행을 출발점으로 읽었는가 → 무방향이면 대칭인가 → 루프가 없다면 대각선이 0인가 → 가중치 단위와 ‘간선 없음’의 표기가 일관적인가를 차례로 확인합니다.

인접 리스트는 각 정점이 실제 이웃만 가리키게 한다

인접 리스트는 인접 행렬의 각 행을 연결 리스트로 바꾼 표현입니다. 정점마다 헤드 노드를 두고, 그 정점에 인접한 정점만 순차적으로 연결합니다. 앞의 방향 그래프는 A: B→C, B: D, C: B→D, D: 비어 있음으로 나타낼 수 있습니다. 방향 그래프의 기본 인접 리스트는 각 정점에서 나가는 간선을 기록합니다.

무방향 간선 {A,B}는 A의 리스트에 B를, B의 리스트에 A를 각각 기록합니다. 따라서 무방향 그래프의 모든 리스트 길이를 합하면 각 간선이 양 끝점에서 한 번씩 나타나 2|E|가 됩니다. 방향 그래프의 진출 인접 리스트에서는 모든 리스트 길이의 합이 간선 수 |E|와 같습니다.

판단 기준	인접 행렬	인접 리스트
기본 공간	정점 수에 따라 n×n칸 필요	정점 헤드와 실제 간선 정보 중심
두 정점의 직접 인접 확인	해당 한 칸을 바로 확인	한 정점의 리스트에서 상대 정점을 탐색
한 정점의 모든 이웃 열거	해당 행 전체를 확인	그 정점의 연결 리스트만 따라감
간선이 적은 그래프	0인 칸이 많이 남음	존재하는 관계만 저장하기 쉬움
표현의 핵심 장점	정점 쌍의 관계를 일정한 위치에서 확인	실제 이웃을 직접 순회

표현 선택은 어느 것이 항상 더 좋다는 결론이 아닙니다. 모든 정점 쌍의 관계를 자주 물으면 행렬이 단순하고, 실제로 연결된 이웃을 따라가는 작업이 중심이며 간선이 적으면 리스트가 자연스럽습니다. 다중 간선이나 가중치를 저장할 때는 리스트 노드나 행렬 원소가 무엇을 담을지도 별도로 정해야 합니다.

하나의 예를 모델에서 저장 구조까지 변환해 본다

앞의 배송 예를 처음부터 재구성해 봅시다. 배송 단계 A, B, C, D를 정점으로 두고 “한 단계에서 바로 넘길 수 있음”을 간선으로 정의합니다. 넘기는 방향이 있으므로 방향 그래프이며, 소요 시간을 비교하려면 간선에 분 단위 가중치를 붙입니다. 이 결정으로 그래프 종류와 각 기호의 의미가 먼저 고정됩니다.

1. 집합 작성: V={A,B,C,D}, E={(A,B),(A,C),(B,D),(C,B),(C,D)}로 관계를 빠짐없이 적습니다.
2. 국소 관계 확인: A의 진출 이웃은 B와 C이고, B의 진입 이웃은 A와 C입니다. D는 나가는 간선이 없지만 들어오는 간선은 B와 C에서 두 개 있습니다.
3. 경로 판정: A와 D 사이에 직접 간선은 없지만 A→B→D와 A→C→D가 있으므로 도달할 수 있습니다. 두 경로의 길이는 모두 간선 두 개인 2입니다.
4. 행렬 변환: A, B, C, D 순서로 행과 열을 만들고 각 방향 간선의 출발 행·도착 열을 1로 채웁니다.
5. 리스트 변환: 각 행의 1이 있는 열만 이어 A는 B·C, B는 D, C는 B·D, D는 빈 리스트로 기록합니다.

이 예에 C→A를 추가하면 A→C→A라는 방향 사이클이 생기므로 더 이상 DAG가 아닙니다. 반대로 C→B를 삭제해도 A→C→D가 남으므로 A에서 D로 가는 경로는 여전히 존재합니다. 이처럼 간선 하나의 변경이 인접 여부, 경로 수, 사이클 성질에 각각 다른 영향을 줄 수 있습니다.

스스로 점검: 새 간선 D→A를 추가했을 때 행렬의 어느 칸이 바뀌고, 어느 인접 리스트에 어떤 정점이 추가되며, 어떤 새 사이클이 생기는지 순서대로 말해 보세요. 정답은 D행 A열, D의 리스트에 A, A→B→D→A 또는 A→C→D→A입니다.

새 그래프 문제는 모델·관계·표현의 세 층으로 푼다

그래프 문제에서 자주 생기는 오류는 그림의 모양, 수학적 성질, 저장 구조를 한꺼번에 판단하는 데서 시작합니다. 먼저 현실 관계를 그래프로 모델링하고, 그다음 인접·경로·차수·사이클 같은 관계를 판정한 뒤, 마지막에 행렬이나 리스트로 옮기면 층별 검산이 가능합니다.

• 모델 층: 정점과 간선의 의미, 방향, 가중치, 중복 간선과 루프 허용 여부를 확정합니다.
• 관계 층: 직접 인접과 경로 존재를 구분하고, 경로 길이·차수·사이클을 간선 방향에 맞게 계산합니다.
• 연산 층: 생성·변경·조회·순회 중 무엇을 요구하는지 추상 자료형의 연산으로 바꿉니다.
• 표현 층: 정점 순서를 고정한 뒤 행렬의 행·열 또는 리스트의 헤드·이웃으로 변환합니다.
• 검산 층: 무방향 행렬의 대칭, 차수와 리스트 길이, 행렬의 1과 간선 집합이 서로 일치하는지 확인합니다.

마지막 판단: 그래프 그림을 보자마자 행렬부터 채우지 마세요. “무엇이 정점이고 어떤 관계가 어느 방향으로 존재하는가”를 집합으로 먼저 말한 뒤, 직접 관계와 이어진 경로를 분리하고, 사용하려는 연산에 맞는 표현을 선택하면 새로운 그래프도 같은 절차로 해석할 수 있습니다.

예상문제 10선

1. 그래프 G=(V,E)에서 V와 E의 의미를 올바르게 연결한 것은?

① V는 경로 길이, E는 정점의 차수이다 ② V는 가중치 집합, E는 방향 집합이다 ③ V는 인접 행렬, E는 인접 리스트이다 ④ V는 정점 집합, E는 간선 집합이다

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 경로 길이와 차수는 그래프에서 계산하는 성질이지 그래프를 이루는 두 집합의 뜻이 아니다.
• ② 오답: 가중치와 방향은 간선에 부여할 수 있는 속성이지만 V와 E의 기본 정의가 아니다.
• ③ 오답: 행렬과 리스트는 같은 그래프를 저장하는 표현 방법이다.
• ④ 정답: 그래프는 대상인 정점의 집합 V와 관계인 간선의 집합 E로 정의한다.

2. 무방향 간선 {A,B}와 방향 간선 (A,B)의 차이를 가장 정확히 설명한 것은?

① 두 표기는 모두 A에서 B로만 이동할 수 있다는 뜻이다 ② 전자는 순서를 구분하지 않고, 후자는 A에서 B로 향하는 순서를 구분한다 ③ 전자는 가중 간선이고, 후자는 가중치가 없는 간선이다 ④ 전자는 루프이고, 후자는 다중 간선이다

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 중괄호의 무방향 간선은 두 끝점의 순서를 구분하지 않는다.
• ② 정답: 무방향 간선은 A-B와 B-A가 같은 관계이고, 방향 간선은 출발과 도착이 정해진다.
• ③ 오답: 괄호의 종류는 방향성을 나타내며 가중치 유무를 정하지 않는다.
• ④ 오답: 루프는 양 끝점이 같은 간선이고 다중 간선은 같은 정점 쌍 사이의 여러 간선이다.

3. 루프와 중복 간선이 없는 정점 6개의 무방향 그래프가 가질 수 있는 최대 간선 수는?

① 6개 ② 12개 ③ 15개 ④ 30개

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 정점마다 간선 하나만 대응시키는 계산으로, 가능한 정점 쌍을 모두 세지 않았다.
• ② 오답: 무방향 정점 쌍의 조합 공식과 일치하지 않는 값이다.
• ③ 정답: 순서 없는 두 정점의 선택 수는 6×5÷2=15이다.
• ④ 오답: 6×5=30은 방향을 구분하는 단순 방향 그래프의 최대 간선 수다.

4. 현실의 관계를 그래프로 만들고 저장 표현으로 옮기는 순서로 가장 적절한 것은?

① 대상·관계 정의 → 방향·가중치 결정 → V와 E 작성 → 행렬 또는 리스트 변환 ② 행렬 크기 결정 → 모든 칸을 1로 채움 → 정점 의미 선택 → 간선 삭제 ③ 경로 길이 계산 → 표현 삭제 → 가중치 제거 → 정점 집합 작성 ④ 인접 리스트 작성 → 관계 기준 결정 → 정점 순서 변경 → 방향 추정

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 모델의 의미와 간선 속성을 먼저 확정한 뒤 집합을 만들고 저장 구조로 변환해야 정보가 일관된다.
• ② 오답: 간선 의미를 정하지 않고 행렬을 채우면 각 1이 어떤 관계를 뜻하는지 알 수 없다.
• ③ 오답: 경로는 정점과 간선이 정의된 뒤에 계산할 수 있는 성질이다.
• ④ 오답: 리스트는 방향과 관계가 확정된 뒤 만들어야 하며 저장 결과에서 방향을 추정하는 순서가 아니다.

5. 방향 간선 (A,B), (A,C), (C,B)가 있을 때 B의 진입 차수와 A의 진출 차수는?

① B의 진입 1, A의 진출 1 ② B의 진입 1, A의 진출 2 ③ B의 진입 2, A의 진출 2 ④ B의 진입 3, A의 진출 0

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: B로 들어오는 간선과 A에서 나가는 간선을 각각 하나씩 빠뜨렸다.
• ② 오답: A의 두 진출은 맞지만 B에는 A와 C에서 간선이 들어온다.
• ③ 정답: B의 진입 간선은 A→B와 C→B 두 개이고 A의 진출 간선은 A→B와 A→C 두 개다.
• ④ 오답: 전체 간선 수를 B의 진입 차수로 오인했고 A에는 나가는 간선이 실제로 존재한다.

6. “사이클이 없는 그래프는 모두 트리이다”라는 판단의 오류를 바로잡은 것은?

① 사이클이 없는 그래프는 정점이 반드시 하나뿐이다 ② 트리는 반드시 하나 이상의 방향 사이클을 가져야 한다 ③ 무사이클 여부는 행렬의 크기만으로 결정한다 ④ 트리이려면 무방향이고 무사이클일 뿐 아니라 모든 정점이 연결되어야 한다

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 여러 정점을 가지면서 사이클이 없는 그래프도 얼마든지 존재한다.
• ② 오답: 무방향 트리는 사이클이 없어야 하며 방향 사이클을 요구하지 않는다.
• ③ 오답: 같은 크기의 행렬이라도 간선 배치에 따라 사이클 유무가 달라진다.
• ④ 정답: 무사이클만 확인하면 끊어진 숲도 포함되므로 무방향성과 연결성을 함께 검사해야 한다.

7. 경로가 A→C→B→D일 때 경로의 길이는?

① 2 ② 3 ③ 4 ④ 7

정답입니다.

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

정답 및 해설 보기

정답: ②

• ① 오답: 중간 정점만 세면 C와 B 두 개지만 경로 길이는 중간 정점 수가 아니다.
• ② 정답: A→C, C→B, B→D의 간선 세 개를 지나므로 길이는 3이다.
• ③ 오답: 네 정점의 개수를 경로 길이로 잘못 사용했다.
• ④ 오답: 정점과 간선의 수를 더하지 않으며 경로 길이는 간선 수만 센다.

8. 인접 행렬과 인접 리스트에 대한 설명으로 옳은 것은?

① 행렬은 정점 쌍의 칸을 확인하고, 리스트는 각 정점의 실제 이웃을 연결해 저장한다 ② 행렬은 방향 그래프에만, 리스트는 무방향 그래프에만 사용할 수 있다 ③ 리스트는 모든 정점 쌍을 반드시 n×n 칸에 저장한다 ④ 행렬은 가중치를 저장할 수 없고 0과 1만 허용한다

정답입니다.

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

정답 및 해설 보기

정답: ①

• ① 정답: 행렬은 행·열의 교차 칸에 관계를 두고 리스트는 존재하는 이웃을 노드로 연결한다.
• ② 오답: 두 표현 모두 방향 그래프와 무방향 그래프에 사용할 수 있다.
• ③ 오답: n×n 칸은 인접 행렬의 구조이며 리스트는 정점별 이웃을 연결한다.
• ④ 오답: 가중 그래프의 행렬은 간선 위치에 가중치를 저장할 수 있다.

9. 정점 순서가 A, B, C인 방향 그래프의 인접 행렬에서 A행 C열이 1이라는 뜻은?

① C에서 A로 가는 경로가 반드시 두 개 존재한다 ② A와 C가 같은 정점이다 ③ A의 진입 차수가 1이라는 뜻이다 ④ A에서 C로 가는 직접 방향 간선이 존재한다

정답입니다.

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

정답 및 해설 보기

정답: ④

• ① 오답: 한 칸의 1은 반대 방향의 경로나 경로 개수를 보장하지 않는다.
• ② 오답: 같은 정점에 대한 정보는 주대각선 칸이며 A행 C열은 서로 다른 정점의 관계다.
• ③ 오답: 행 A는 A에서 나가는 관계를 나타내므로 진입 차수를 뜻하지 않는다.
• ④ 정답: 방향 인접 행렬에서 행은 출발 정점, 열은 도착 정점이므로 A→C가 있다.

10. 간선이 적은 대규모 그래프에서 각 정점의 실제 이웃을 반복해서 방문하려 할 때 가장 타당한 판단은?

① 그래프의 방향과 관계 의미를 정하지 않고 모든 정점 쌍을 간선으로 만든다 ② 경로와 인접을 같은 뜻으로 보고 행렬의 대각선만 조사한다 ③ 모델을 확정한 뒤 실제 이웃만 연결하는 인접 리스트를 우선 검토한다 ④ 정점 수와 무관하게 인접 행렬이 언제나 공간을 더 적게 쓴다고 가정한다

정답입니다.

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

정답 및 해설 보기

정답: ③

• ① 오답: 관계 기준 없이 완전 그래프를 만들면 원래 데이터의 의미와 희소성이 사라진다.
• ② 오답: 인접은 직접 간선, 경로는 이어진 간선 열이며 대각선만으로 둘을 판정할 수 없다.
• ③ 정답: 존재하는 간선이 적고 이웃 순회가 중심이면 실제 이웃을 연결하는 리스트가 목적에 잘 맞는다.
• ④ 오답: 행렬은 정점 수에 따라 n×n칸이 필요하므로 간선이 적을 때 빈 칸이 많이 생길 수 있다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 그래프의 개념, 성질, 추상 자료형과 표현 방법을 학습 목적에 맞게 재구성한 비공식 학습자료입니다.

• 작성·편집: 올에이클래스 학습연구팀
• 주요 근거: 한국방송통신대학교 자료구조 14강 「그래프 Ⅰ」 강의록
• 보충 자료: 외부 자료는 사용하지 않았으며 배송 관계, 행렬, 경로와 계산 예제는 강의 범위 안에서 학습용으로 직접 구성했습니다.
• 편집 원칙: 올에이클래스 편집 정책
• 최종 내용 검토: 2026-08-23