AlgoVerse

الگوریتم هاپکرافت–کارپ

تطابق بیشینه در گراف دوبخشی با فازها: در هر فاز با BFS لایه می‌سازد و بعد چند مسیر افزایشی کوتاه و جدا از هم را با DFS پیدا می‌کند.

روش ساده‌ی تطابق (مسیر افزایشی برای هر گره) در بدترین حالت O(V · E) است. هاپکرافت و کارپ (۱۹۷۳) در هر فاز چند مسیر افزایشی را با هم پیدا می‌کنند:

ادامه‌ی توضیح ↓
ورودی:
V=8 · E=8 · src=Aخروجی PDF

همان کارگرها و کارهای تطابق دوبخشی؛ فاز ۱ چند جفت هم‌زمان می‌سازد و فاز ۲ بقیه را با مسیرهای بلندتر پیدا می‌کند.

  1. from collections import deque
  3. INF = float("inf")
  6. def hopcroft_karp(graph, src):
  7. # Side 0 is found by two-colouring each component (the input is bipartite).
  8. side = {}
  9. for s in graph:
  10. if s in side:
  11. continue
  12. side[s] = 0
  13. stack = [s]
  14. while stack:
  15. u = stack.pop()
  16. for v, _ in graph[u]:
  17. if v not in side:
  18. side[v] = 1 - side[u]
  19. stack.append(v)
  20. left = [v for v in graph if side[v] == 0]
  21. match = {v: None for v in graph}
  22. size = 0
  23. phase = 0
  24. while True:
  25. phase = phase + 1
  26. dist, found = layers(graph, left, match)
  27. if not found:
  28. break
  29. for u in left:
  30. if match[u] is None:
  31. if augment(graph, u, match, dist):
  32. size = size + 1
  33. return size, match
  36. def layers(graph, left, match):
  37. dist = {}
  38. queue = deque()
  39. for u in left:
  40. if match[u] is None:
  41. dist[u] = 0
  42. queue.append(u)
  43. found = False
  44. while queue:
  45. u = queue.popleft()
  46. for v, _ in graph[u]:
  47. w = match[v]
  48. if w is None:
  49. found = True
  50. elif w not in dist:
  51. dist[w] = dist[u] + 1
  52. queue.append(w)
  53. return dist, found
  56. def augment(graph, u, match, dist):
  57. for v, _ in graph[u]:
  58. w = match[v]
  59. if w is None:
  60. match[u] = v
  61. match[v] = u
  62. return True
  63. if dist.get(w) == dist[u] + 1:
  64. if augment(graph, w, match, dist):
  65. match[u] = v
  66. match[v] = u
  67. return True
  68. dist[u] = INF
  69. return False

ناوردا: در هر فاز، همه‌ی مسیرهای افزایشی پیداشده کوتاه‌ترین طول ممکن را دارند و گره مشترک ندارند.

شروع اجرا

ABCDWXYZ
  • گره‌ی جاری (u)
  • یال‌های تطابق
  • یالِ در حال بررسی

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

src'A'

نارنجی = در همین گام عوض شد

graph dict
  • 'A': [('W', 1), ('X', 1)]
  • 'B': [('W', 1)]
  • 'C': [('X', 1), ('W', 1), ('Y', 1)]
  • 'D': [('Y', 1), ('Z', 1)]
  • 'W': [('A', 1), ('B', 1), ('C', 1)]
  • 'X': [('A', 1), ('C', 1)]
  • 'Y': [('C', 1), ('D', 1)]
  • 'Z': [('D', 1)]

Call stack

  1. hopcroft_karp()خط 6
گام ۱ از ۳۷۲
خط سیاه = phase · خط نارنجی = گام کلیدیfree: 0/5 · reach_free: 0/9 · phase: 0/3 · take: 0/4 · grown: 0/4 · dead_end: 0/1 · layer: 0/3 · reroute: 0/3 · no_path: 0/1

    رشد تعداد عملیات با اندازه‌ی ورودی

    میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

    • phase
    • layer
    • ورودی فعلی (n=8)
    051048121620n = تعداد گره‌هاlayerphase
    نمایش به شکل جدول
    nphaselayer
    420
    82.82.4
    122.42
    163.28.2
    2038
    توضیح

    ایده

    روش ساده‌ی تطابق (مسیر افزایشی برای هر گره) در بدترین حالت O(V · E) است. هاپکرافت و کارپ (۱۹۷۳) در هر فاز چند مسیر افزایشی را با هم پیدا می‌کنند:

    1. BFS از همه‌ی گره‌های آزاد سمت چپ، گراف را لایه‌لایه می‌کند تا به یک گره‌ی آزاد سمت راست برسد. لایه‌ی هر گره طول کوتاه‌ترین مسیر افزایشی تا آن است.
    2. DFS از هر گره‌ی آزاد چپ فقط یک لایه پایین‌تر می‌رود؛ پس فقط کوتاه‌ترین مسیرها پیدا می‌شوند. گره‌ای که به بن‌بست رسید برای بقیه‌ی فاز کنار گذاشته می‌شود.

    چرا سریع است؟

    بعد از هر فاز طول کوتاه‌ترین مسیر افزایشی دست‌کم یکی بیشتر می‌شود و می‌شود نشان داد فقط O(√V) فاز لازم است. هر فاز O(E) است: جمعاً O(E √V).

    در trace به چه چیزی نگاه کنی

    • عدد کنار گره‌های چپ لایه‌ی BFS آن‌هاست؛ یال‌های رنگی تطابق فعلی‌اند.
    • با سطح جزئیات «هر دور حلقه» فازها را یکی‌یکی ببین.