AlgoVerse

نقاط مفصلی

گره‌هایی را پیدا می‌کند که با حذفشان گراف تکه می‌شود؛ با یک DFS و مقدار low هر گره (کمترین زمان کشفی که از زیردرختش قابل دسترس است).

نقطه‌ی مفصلی (گره‌ی برشی) گره‌ای است که با حذفش گراف همبند تکه می‌شود. امتحان حذف تک‌تک گره‌ها O(V·(V + E)) هزینه دارد؛ یک DFS کافی است:

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

دو مثلث که با یک پل D — E به هم وصل‌اند؛ D و E نقطه‌ی مفصلی‌اند.

  1. def articulation_points(graph, src):
  2. disc = {v: 0 for v in graph}
  3. low = {v: 0 for v in graph}
  4. cut = set()
  5. timer = [0]
  6. for s in graph:
  7. if disc[s] == 0:
  8. visit(graph, s, None, disc, low, cut, timer)
  9. return cut
  12. def visit(graph, u, parent, disc, low, cut, timer):
  13. timer[0] = timer[0] + 1
  14. disc[u] = timer[0]
  15. low[u] = timer[0]
  16. children = 0
  17. for v, _ in graph[u]:
  18. if disc[v] == 0:
  19. children = children + 1
  20. visit(graph, v, u, disc, low, cut, timer)
  21. low[u] = min(low[u], low[v])
  22. if parent is not None:
  23. if low[v] >= disc[u]:
  24. cut.add(u)
  25. elif v != parent:
  26. low[u] = min(low[u], disc[v])
  27. if parent is None:
  28. if children > 1:
  29. cut.add(u)

ناوردا: low[u] کمترین disc است که از زیردرخت u با حداکثر یک یال برگشتی می‌شود به آن رسید.

شروع اجرا

ABCDEFG
  • گره‌ی جاری (u)
  • درخت پیمایش (از parent)
  • یالِ در حال بررسی

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

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

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

src'A'

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

graph dict
  • 'A': [('B', 1), ('D', 1)]
  • 'B': [('A', 1), ('D', 1)]
  • 'C': [('D', 1)]
  • 'D': [('B', 1), ('A', 1), ('E', 1), ('C', 1)]
  • 'E': [('D', 1), ('F', 1), ('G', 1)]
  • 'F': [('E', 1), ('G', 1)]
  • 'G': [('F', 1), ('E', 1)]

Call stack

  1. articulation_points()خط 1
گام ۱ از ۱۵۰
خط سیاه = discover · خط نارنجی = گام کلیدیdiscover: 0/7 · check: 0/16 · back_edge: 0/4 · pull_low: 0/6 · test: 0/5 · cut_vertex: 0/3 · root_test: 0/1 · tree_done: 0/1

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

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

    • check
    • ورودی فعلی (n=7)
    050100481216202428n = تعداد گره‌هاcheck
    نمایش به شکل جدول
    ncheck
    410.4
    827.6
    1241.6
    1656
    2070.8
    2474.4
    2894.4
    توضیح

    ایده

    نقطه‌ی مفصلی (گره‌ی برشی) گره‌ای است که با حذفش گراف همبند تکه می‌شود. امتحان حذف تک‌تک گره‌ها O(V·(V + E)) هزینه دارد؛ یک DFS کافی است:

    • disc[u]: زمان کشف u.
    • low[u]: کمترین زمان کشفی که از زیردرخت u (با یال‌های درخت و حداکثر یک یال برگشتی) می‌شود به آن رسید.

    قاعده

    • گره‌ی غیرریشه‌ی u نقطه‌ی مفصلی است اگر فرزندی مثل v داشته باشد که low[v] ≥ disc[u]؛ یعنی زیردرخت v بدون عبور از u به بالاتر راهی ندارد.
    • ریشه نقطه‌ی مفصلی است اگر در درخت DFS بیش از یک فرزند داشته باشد.

    هزینه

    یک DFS: O(V + E).

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

    • عدد کنار هر گره low آن است؛ ببین یال‌های برگشتی چطور آن را کم می‌کنند.
    • مجموعه‌ی cut در پنل حافظه نقاط مفصلی پیداشده است.