Graph Algorithms Practice

Problem 1 — Count Neighbors ⭐

Given an undirected graph:

N = 5
Edges:
1 2
1 3
2 4
3 5

จงหาจำนวน neighbor ของทุก vertex

Problem 2 — Directed Graph ⭐

Construct adjacency list

Edges

1 -> 2
1 -> 3
2 -> 4
3 -> 4

แสดง adjacency list ของ directed graph

Problem 3 — Adjacency Matrix ⭐⭐

Edges

1 2
1 3
2 3
3 4

สร้าง adjacency matrix ของ graph

Problem 4 — Connected Components ⭐⭐

N = 6

Edges
1 2
2 3
4 5

Graph นี้มี connected components กี่ชุด?

Problem 5 — Friend Network ⭐⭐

Operations:

F 1 2
F 2 3
F 4 5

หลังจากแต่ละ operation ให้แสดงขนาดของ friend group

Problem 6 — Detect Cycle ⭐⭐⭐

Edges

1 2
2 3
3 4
4 1

ตรวจสอบว่า graph มี cycle หรือไม่

Problem 7 — Minimum Spanning Tree ⭐⭐

1 2 1
1 3 4
2 3 2
2 4 5
3 4 3

หาค่า cost ของ Minimum Spanning Tree

Problem 8 — Build Roads ⭐⭐⭐

มีเมือง N เมือง บางเมืองมีถนนเชื่อมกันแล้ว

ต้องสร้างถนนเพิ่มกี่เส้นเพื่อให้ทุกเมืองเชื่อมกัน

Problem 9 — Course Schedule ⭐⭐

1 -> 2
1 -> 3
3 -> 4
2 -> 4

หาลำดับ Topological Sort ที่เป็นไปได้

Problem 10 — DAG Cycle Detection ⭐⭐⭐

1 -> 2
2 -> 3
3 -> 1

สามารถทำ Topological Sort ได้หรือไม่?

Solution Overview

Algorithms Used Today

Complexity Summary