جلسهی 35: درهمسازی و گرافها Hashing and Graphs
الگوهای پرکاربرد dict و Counter (مثل two-sum و گروهبندی آناگرامها) را میبینیم، گراف را با فهرست مجاورت (adjacency list) مدل میکنیم و با BFS کوتاهترین مسیر را پیدا میکنیم.
در این جلسه یاد میگیری
- با
dict،Counterوdefaultdictمسائل شمارش و گروهبندی را درO(n)حل کنید. - الگوی «مکمل دیدهشده» (
two-sum) و پیشوند جمع باdictرا به کار ببرید. - گراف را از فهرست یالها به فهرست مجاورت تبدیل کنید.
- با
BFSوdequeفاصله و مسیر کوتاهترین را در گراف و شبکه (grid) پیدا کنید.
درس
dict و set با hash کار میکنند: کلید به یک عدد تبدیل میشود و مستقیم به خانهی مربوط میرود؛ خواندن و نوشتن میانگین O(1). کلید باید hashable (تغییرناپذیر) باشد: str، int، tuple بله؛ list نه.
from collections import Counter, defaultdict
words = "to be or not to be".split()
print(Counter(words).most_common(2))
groups = defaultdict(list)
for w in words:
groups[len(w)].append(w)
print(dict(groups))الگوی two-sum: بهجای امتحان همهی جفتها (O(n²))، در یک گذر برای هر x بپرسید آیا target - x قبلاً دیده شده؛ dict مقدار ← اندیس آن را در O(1) جواب میدهد. همین ایده با پیشوند جمع، «تعداد زیرآرایههایی با جمع k» را در O(n) حل میکند.
def two_sum(nums, target):
seen = {}
for j, x in enumerate(nums):
if target - x in seen:
return seen[target - x], j
seen[x] = j
return None
print(two_sum([2, 7, 11, 15], 9))گراف = گرهها (node) + یالها (edge). فهرست مجاورت یک dict از گره به لیست همسایههاست؛ حافظه O(V + E). در گراف بدون جهت هر یال را در دو جهت اضافه کنید.
from collections import defaultdict
edges = [("A", "B"), ("A", "C"), ("B", "D")]
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
print(dict(graph))جستوجوی سطحاول (BFS) از مبدأ لایهبهلایه پیش میرود: اول همهی گرههای با فاصلهی ۱، بعد ۲ و... پس در گراف بدون وزن، اولین باری که به گرهای میرسیم کوتاهترین فاصله را داریم. صف (deque) + dist (که نقش visited را هم دارد)؛ زمان O(V + E).
from collections import deque
def bfs(graph, start):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist:
dist[nxt] = dist[node] + 1
queue.append(nxt)
return distبرای بازسازی مسیر، هنگام کشف هر گره والدش (parent) را ذخیره کنید و از مقصد به عقب برگردید. شبکهی دوبعدی (grid) هم گراف است: هر خانهی باز یک گره و چهار همسایهی بالا/پایین/چپ/راست یالها هستند.
def path_to(parent, goal):
path = []
while goal is not None:
path.append(goal)
goal = parent[goal]
return path[::-1]
print(path_to({"A": None, "B": "A", "D": "B"}, "D"))مثالهای این جلسه
- مثال دیکشنری در پایتون: print(dict(groups))
- مثال تابع در پایتون: def two_sum(nums, target):
- مثال دیکشنری در پایتون: print(dict(graph))
- مثال تابع در پایتون: def bfs(graph, start):
- مثال تابع در پایتون: def path_to(parent, goal):
چالشها
- Top Words (آسان)
- Two Sum (آسان)
- Adjacency List (آسان)
- Anagram Groups (متوسط)
- BFS Order (متوسط)
- Degrees of Separation (متوسط)
- First Unique Character (متوسط)
- Route Planner (سخت)
- Grid Shortest Path (سخت)
- Connected Components (سخت)
- Subarrays with Sum K (متوسط)
- Build Order (سخت)