دور اویلری (هیرهولتسر)

دوری پیدا می‌کند که از هر یال دقیقاً یک بار می‌گذرد؛ هر جا گیر کرد، یک دور فرعی را در مسیر جا می‌دهد.

دور اویلری گذرگاه بسته‌ای است که از هر یال دقیقاً یک بار می‌گذرد (مسئله‌ی پل‌های کونیگسبرگ). اویلر نشان داد در گراف همبند چنین دوری هست اگر و فقط اگر درجه‌ی همه‌ی گره‌ها زوج باشد.

ادامه‌ی توضیح ↓

زمان: O(V + E)
حافظه: O(V + E)
گریمالدی، فصل ۱۱
جانسون‌باو، فصل ۸

ورودی:

V=6 · E=12 · src=Aخروجی PDF

هشت‌وجهی: شش گره که درجه‌ی همه ۴ است؛ گذرگاه اول زود بسته می‌شود و بقیه به‌صورت دورهای فرعی جا داده می‌شوند.

def euler_circuit(graph, src):
for v in graph:
if len(graph[v]) % 2 == 1:
return None
remaining = {v: list(graph[v]) for v in graph}
edge_count = sum(len(graph[v]) for v in graph) // 2
used = []
stack = [src]
circuit = []
while stack:
u = stack[-1]
if remaining[u]:
v, w = remaining[u].pop(0)
remaining[v].remove((u, w))
used.append((u, v, w))
stack.append(v)
else:
circuit.append(stack.pop())
if len(used) < edge_count:
return None
circuit.reverse()
return circuit

ناوردا: پشته همیشه یک گذرگاه از s است و circuit (برعکس) انتهای دور نهایی است؛ هر گره‌ای که گیر کند دیگر یال آزاد ندارد.

شروع اجرا

گره‌ی جاری (u)
یال‌های پیموده‌شده
یالِ در حال بررسی

پشته `stack`

خالی

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

src'A'

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

graph dict

'A': [('B', 1), ('C', 1), ('D', 1), ('E', 1)]
'B': [('A', 1), ('F', 1), ('C', 1), ('E', 1)]
'C': [('A', 1), ('F', 1), ('B', 1), ('D', 1)]
'D': [('A', 1), ('F', 1), ('C', 1), ('E', 1)]
'E': [('A', 1), ('F', 1), ('D', 1), ('B', 1)]
'F': [('B', 1), ('C', 1), ('D', 1), ('E', 1)]

Call stack

euler_circuit()خط 1

گام ۱ از ۱۵۹

توضیح

ایده

الگوریتم هیرهولتسر

از مبدأ راه بیفت و هر بار از یک یال آزاد بگذر (و آن را مصرف کن). گره‌ها را روی پشته بگذار.
چون درجه‌ها زوج‌اند، فقط در گره‌ای گیر می‌کنی که دور را بسته باشد.
وقتی گره‌ی بالای پشته یال آزاد ندارد، آن را از پشته بردار و به circuit اضافه کن. اگر گره‌ی زیرین هنوز یال آزاد دارد، از آنجا یک دور فرعی شروع می‌شود که خودبه‌خود در جای درست جا می‌گیرد.

در پایان، circuit برعکس‌شده همان دور اویلری است.

هزینه

هر یال یک بار پیموده و هر گره‌ی پشته یک بار برداشته می‌شود: O(V + E).

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

یال‌های رنگی پیموده شده‌اند؛ پشته زیر گراف است.
ورودی «پاپیون» را ببین: لحظه‌ای که A گیر می‌کند و دور فرعی از C شروع می‌شود.