그래프는 여러 노드(정점)가 선(간선)으로 서로 연결된 자료구조입니다.
버스 정류장(정점)이 노선(간선)으로 연결된 형태입니다. 여러 노선이 교차하는 복잡한 구조입니다.
링크드인, 페이스북 등에서 사람(정점)들이 친구 관계(간선)로 연결된 형태입니다.
도시(정점)와 도시를 잇는 도로나 항공 노선(간선)이 그래프 구조입니다.
A graph is a data structure where multiple nodes (vertices) are connected by edges.
Bus stops (vertices) connected by routes (edges). Multiple routes intersect creating complex structures.
On LinkedIn or Facebook, people (vertices) are connected by friendships (edges).
Cities (vertices) connected by roads or flight routes (edges) form graph structures.
A tree is a special case of a graph — a connected graph with no cycles. Graphs can have cycles, disconnected parts, and directed edges!
간선에 방향이 없습니다. A→B로 갈 수 있으면 B→A로도 갈 수 있습니다.
간선에 방향이 있습니다. 화살표 방향으로만 이동 가능합니다.
간선마다 가중치(비용, 거리 등)가 부여된 그래프입니다.
Edges have no direction. If A connects to B, then B also connects to A.
Edges have direction (arrows). Movement only allowed in the arrow's direction.
Each edge carries a weight (cost, distance, etc.). Used for shortest path, minimum cost problems.
G1 undirected: V={A,B,C,D}, E={(A,B),(A,C),(A,D),(B,C),(C,D)}
G3 directed: V={A,B,C,D}, E=<A,B>,<A,C>,<D,A>,<D,C>
그래프를 코드로 구현할 때 인접 행렬(Adjacency Matrix)을 사용합니다. 정점이 N개이면 N×N 크기의 2차원 배열로 표현합니다.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 1 |
| B | 1 | 0 | 1 | 0 |
| C | 1 | 1 | 0 | 1 |
| D | 1 | 0 | 1 | 0 |
무방향 그래프의 인접 행렬은 대각선을 기준으로 서로 대칭됩니다. A→B = 1이면 B→A도 반드시 1입니다.
An adjacency matrix represents a graph as an N×N 2D array, where N is the number of vertices.
| A | B | C | D | |
|---|---|---|---|---|
| A | 0 | 1 | 1 | 0 |
| B | 0 | 0 | 0 | 0 |
| C | 0 | 0 | 0 | 0 |
| D | 1 | 0 | 1 | 0 |
A directed graph's matrix is NOT symmetric. A→B=1 does not mean B→A=1. Only outgoing edges from each vertex are marked.
## G1 무방향 그래프 ## 0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0 ## G3 방향 그래프 ## 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0
Graph(size) creates an size×size 2D array filled with 0. Each cell graph[i][j] represents the edge from vertex i to vertex j.
For undirected graphs, always set both directions: graph[0][1]=1 AND graph[1][0]=1.
For directed graphs, only set the outgoing direction: A→B means graph[0][1]=1 only.
## G1 Undirected ## 0 1 1 1 (A→B,C,D) 1 0 1 0 (B→A,C) 1 1 0 1 (C→A,B,D) 1 0 1 0 (D→A,C) ## G3 Directed ## 0 1 1 0 (A→B,C) 0 0 0 0 (B→none) 0 0 0 0 (C→none) 1 0 1 0 (D→A,C)
정점 번호를 이름으로 지정하면 더 직관적입니다.
Using names as variable indices makes code more readable.
문별, 솔라, 휘인, 쯔위, 선미, 화사 = 0,1,2,3,4,5
Now G1.graph[문별][솔라] = 1 is much clearer than G1.graph[0][1] = 1!
Adds row and column headers using nameAry so the matrix is human-readable.
문별 솔라 휘인 쯔위 선미 화사 문별 0 1 1 0 0 0 솔라 1 0 0 1 0 0 휘인 1 0 0 1 0 0 쯔위 0 1 1 0 1 1 선미 0 0 0 1 0 1 화사 0 0 0 1 1 0
Python allows Korean variable names! 문별 = 0 is valid Python. This makes the graph code read like natural language.
Graph 클래스로 4개 정점(A,B,C,D)의 무방향 그래프 G1과 방향 그래프 G3을 구현하고, 인접 행렬을 출력하시오. (Code09-01)
4개 정점의 무방향 그래프를 구현하시오. 간선: A-D, B-C, B-D, C-B, D-A, D-B
Implement undirected graph G1 and directed graph G3 with 4 vertices (A,B,C,D) using Graph class. Print the adjacency matrices. (Code09-01)
Implement an undirected graph with 4 vertices. Edges: A-D, B-C, B-D, C-B, D-A, D-B
그래프의 모든 정점을 방문하는 방법 중 하나로, 한 방향으로 갈 수 있을 때까지 깊이 들어간 후, 더 이상 갈 곳이 없으면 되돌아와서 다른 방향으로 탐색합니다.
스택(stack) : 현재 경로를 기억하여 되돌아갈 때 사용
방문 배열(visitedAry) : 이미 방문한 정점을 기록하여 중복 방문 방지
DFS는 미로 찾기와 같습니다. 한 길로 끝까지 가보고, 막히면 갈림길로 돌아와서 다른 길로 가는 방식입니다!
DFS visits all vertices in a graph by going as deep as possible in one direction, then backtracking when there's nowhere else to go.
Stack : remembers the current path for backtracking
Visited Array (visitedAry) : records visited vertices to avoid revisiting
DFS is like solving a maze: go down one path until you hit a dead end, then backtrack to the last fork and try another path!
시작 정점: A(0) / 인접 행렬 기준으로 탐색
A → C → B → D
Start vertex: A(0) / Scan adjacency matrix row by row
A → C → B → D
그래프 생성 후, 스택과 방문 배열을 이용한 DFS 탐색
방문 순서 -->A C B D
Build graph, then traverse using stack + visited array
for loop: scan row current in adjacency matrix → find first unvisited neighbor
if next != None: move forward (push)
else: backtrack (pop)
chr(ord('A')+0) = 'A'
chr(ord('A')+1) = 'B'
chr(ord('A')+2) = 'C'
Converts index 0,1,2,3 → 'A','B','C','D'
DFS uses a stack (LIFO) → goes deep first.
BFS uses a queue (FIFO) → goes wide first.
Same graph, different visit orders!
DFS를 이용하면 두 정점이 연결되어 있는지 확인할 수 있습니다. 시작 정점(0번)에서 DFS를 수행한 후, 찾는 정점이 방문 기록에 있으면 연결된 것입니다.
Code09-03_의 DFS와 거의 동일하지만, 마지막에 findVtx in visitedAry를 확인하여 True/False를 반환합니다. 이 함수는 Part 3의 최소 신장 트리에서도 사용됩니다!
Using DFS, we can check if two vertices are connected. Run DFS from vertex 0, then check if the target vertex appears in the visited list.
1. Run full DFS from vertex 0
2. After DFS completes, check: findVtx in visitedAry
3. If True → the vertex is reachable (connected)
4. If False → the vertex is NOT reachable (disconnected)
• Wrapped in a function (reusable)
• Checks != 0 instead of == 1 (works with weighted graphs too!)
• Returns True/False instead of printing
This function is essential for Kruskal's algorithm — it checks if removing an edge disconnects the graph.
4개 정점(A,B,C,D)의 무방향 그래프를 생성하고, 정점 A에서 DFS 탐색을 수행하여 방문 순서를 출력하시오.
6명(문별,솔라,휘인,쯔위,선미,화사)의 친구 관계 그래프에서 DFS 탐색을 수행하여 방문 순서를 이름으로 출력하시오.
Create an undirected graph with 4 vertices (A,B,C,D), perform DFS from vertex A, and print the visit order.
Perform DFS on a 6-person friend graph (문별,솔라,휘인,쯔위,선미,화사) and print the visit order using names.
신장 트리(Spanning Tree): 모든 정점을 포함하면서 사이클이 없는 부분 그래프입니다. 정점이 N개이면 간선은 정확히 N-1개입니다.
최소 신장 트리(MST): 간선의 가중치 합이 최소인 신장 트리입니다.
6개 도시를 자전거 도로로 연결할 때, 모든 도시를 연결하면서 건설 비용(가중치)을 최소화하려면 MST를 구하면 됩니다!
Spanning Tree: A subgraph that includes ALL vertices with NO cycles. With N vertices, it has exactly N-1 edges.
Minimum Spanning Tree (MST): The spanning tree with the minimum total edge weight.
Connect 6 cities with bicycle roads at minimum cost. All cities must be reachable, but we want the cheapest total construction!
• N vertices → exactly N-1 edges
• All vertices are connected (reachable from any vertex)
• No cycles (removing any edge disconnects)
• Total weight is minimized
If graph has 6 vertices → MST has exactly 5 edges (6-1=5).
Start with all edges, keep removing the most expensive ones while ensuring connectivity!
가중치가 가장 큰 간선부터 제거하되, 그래프가 분리되지 않는 경우에만 제거합니다.
findVertex()로 양쪽 정점이 여전히 연결되는지 확인비싼 도로부터 하나씩 없애보기! 없애도 모든 도시가 연결되면 없애고, 끊어지면 다시 살리기!
Remove edges from highest weight first, but only if removing doesn't disconnect the graph.
findVertex() to check if both endpoints are still connected1. edgeAry = list of [weight, start, end]
2. Sort descending by weight
3. Remove duplicates (undirected → each edge listed twice)
4. While len(newAry) > gSize-1: try removing
6개 도시, 8개 간선의 가중치 그래프
| 간선 | 가중치 | 결과 |
|---|---|---|
| 서울↔광주 | 50 | 제거해도 연결됨 → 삭제! |
| 서울↔속초 | 40 | 제거해도 연결됨 → 삭제! |
| 대전↔부산 | 30 | 제거해도 연결됨 → 삭제! |
| 광주↔부산 | 25 | 제거하면 부산 끊어짐 → 복구! |
| 대전↔광주 | 20 | 제거하면 끊어짐 → 복구! |
춘천↔서울(10), 서울↔대전(11), 속초↔대전(12), 대전↔광주(20), 광주↔부산(25)
총 비용 = 10+11+12+20+25 = 78
6 cities, 8 edges weighted graph
50 (서울↔광주) → removed
40 (서울↔속초) → removed
30 (대전↔부산) → removed
25 (광주↔부산) → kept! (would disconnect)
20 (대전↔광주) → kept! (would disconnect)
Scan adjacency matrix → collect [weight, start, end] for each non-zero cell.
sorted(..., reverse=True) puts the heaviest edge first so we try removing it.
Undirected graphs list each edge twice (A→B and B→A). Taking every 2nd entry gives unique edges.
1. Temporarily remove edge (set to 0)
2. Check findVertex(G1, start) and findVertex(G1, end)
3. Both True → graph still connected → delete from list
4. Either False → graph disconnected → restore the edge, move to next
len(newAry) > gSize-1
We stop when exactly N-1 edges remain — that's the MST!
5개 편의점이 그래프로 연결되어 있고, 각 편의점에 허니버터칩 재고가 있습니다. DFS로 모든 편의점을 방문하며 가장 많은 재고를 보유한 편의점을 찾습니다.
허니버터칩 최대 보유 편의점(개수) --> MiniStop ( 90 )
5 stores connected as a graph, each with honey butter chip inventory. Use DFS to visit all stores and find the one with the most inventory.
Standard DFS + max tracking:
At each new visit, compare storeAry[current][1] with maxCount. Update if larger.
storeAry[i][0] = store name
storeAry[i][1] = chip count
This is a common pattern: parallel data alongside the graph!
GS25(30) → CU(60) → Seven11(10) → MiniStop(90) → Emart24(40)
Winner: MiniStop with 90 chips!
6개 도시(서울, 뉴욕, 런던, 북경, 방콕, 파리)를 해저 케이블로 연결할 때, 최소 비용으로 모든 도시를 연결합니다.
도시 이름과 간선 가중치만 바꾸면 동일한 크루스칼 알고리즘을 적용할 수 있습니다.
Connect 6 cities (서울, 뉴욕, 런던, 북경, 방콕, 파리) with undersea cables at minimum total cost.
1. Build weighted graph with city distances
2. Create edge list, sort descending
3. Remove duplicates
4. Remove heaviest edges while connected
5. Result: MST with 5 edges
Ex09-02 sorts reverse=False (ascending) in the code, but the removal logic stays the same — it still processes from the end of the sorted list to remove heavy edges first. The approach works either way!
서울↔북경(10), 방콕↔파리(20), 런던↔방콕(30), 북경↔뉴욕(40), 북경↔방콕(50)
Total = 150
5개 편의점 네트워크에서 DFS로 모든 편의점을 방문하여 허니버터칩을 가장 많이 보유한 편의점을 찾으시오.
6개 도시를 해저 케이블로 연결하는 최소 비용 연결도를 크루스칼 알고리즘으로 구하시오.
Use DFS on a 5-store network to find the store with the most honey butter chips.
Find the minimum cost undersea cable connection for 6 cities using Kruskal's algorithm.