نمایش گراف، جستجوی سطح‌اول، و جستجوی عمق‌اول

یک گراف چه چیزی را نشان می‌دهد

یک Graph (گراف) G = (V, E) از یک مجموعه Vertices (رأس‌ها) V و یک مجموعه Edges (یال‌ها) E که جفت‌های رأس را متصل می‌کنند تشکیل شده است. گراف‌ها یا Directed (جهت‌دار) هستند، جایی که یال‌ها یک جهت مشخص دارند، یا Undirected (بدون‌جهت)، جایی که یال‌ها متقارن‌اند. گراف‌ها طیف عظیمی از ساختارهای دنیای واقعی را مدل‌سازی می‌کنند: شبکه‌های جاده، ارتباطات اجتماعی، زنجیره‌های وابستگی در build های نرم‌افزار، و خود وب، جایی که صفحات به صفحات دیگر لینک می‌شوند.

نمایش گراف‌ها در حافظه

لیست‌های مجاورت

یک نمایش Adjacency List (لیست مجاورت) برای هر رأس، یک لیست پیوندی (که پیش‌تر در این مجموعه بحث شد) از رأس‌های همسایه‌اش را ذخیره می‌کند.

مثال گراف جهت‌دار:
1 → 2, 1 → 3
2 → 3
3 → 1

نمایش لیست مجاورت:
Adj[1] = [2, 3]
Adj[2] = [3]
Adj[3] = [1]

این نمایش از فضای Θ(V + E) استفاده می‌کند، که برای Sparse Graphs (گراف‌های تنک) (گراف‌هایی با یال‌های نسبتاً کم در مقایسه با حداکثر ممکن) کارآمد است. یافتن همه همسایگان یک رأس زمانی متناسب با درجه‌اش می‌گیرد، اما بررسی اینکه آیا یک یال خاص وجود دارد نیازمند اسکن کل لیست مجاورت یک نقطه‌انتهایی است، که در بدترین‌حالت O(V) زمان می‌گیرد.

ماتریس‌های مجاورت

یک Adjacency Matrix (ماتریس مجاورت) از یک ماتریس V × V استفاده می‌کند، جایی که ورودی A[i][j] نشان می‌دهد آیا یک یال از رأس i به رأس j وجود دارد.

همان گراف به‌عنوان یک ماتریس مجاورت:
    1  2  3
1 [ 0  1  1 ]
2 [ 0  0  1 ]
3 [ 1  0  0 ]

این نمایش از فضای Θ(V²) استفاده می‌کند صرف‌نظر از اینکه واقعاً چند یال وجود دارد، که آن را برای گراف‌های تنک هدرده می‌کند، اما زمان O(1) برای بررسی اینکه آیا هر یال خاصی وجود دارد ارائه می‌دهد، مزیتی که لیست‌های مجاورت نمی‌توانند با آن مطابقت کنند. ماتریس‌های مجاورت برای Dense Graphs (گراف‌های چگال) (جایی که E نزدیک به V² است) یا هروقت پرس‌وجوهای وجود-یال مکرر مورد نیاز باشند ترجیح داده می‌شوند.

جستجوی سطح‌اول: کاوش سطح‌به‌سطح

Breadth-First Search (BFS) یک گراف را به‌سمت بیرون از یک رأس منبع کاوش می‌کند، و همه رأس‌ها در فاصله ۱ را پیش از هر رأس در فاصله ۲ بازدید می‌کند، و همین‌طور، با استفاده از ساختار داده صف که پیش‌تر در این مجموعه بحث شد برای حفظ این ترتیب دقیق.

BFS(G, s):
  برای هر رأس u در G.V - {s}:
      u.color = WHITE
      u.d = infinity
      u.p = NIL
  s.color = GRAY
  s.d = 0
  s.p = NIL
  Q = صف خالی
  ENQUEUE(Q, s)
  تا زمانی که Q خالی نباشد:
      u = DEQUEUE(Q)
      برای هر v در Adj[u]:
          اگر v.color == WHITE:
              v.color = GRAY
              v.d = u.d + 1
              v.p = u
              ENQUEUE(Q, v)
      u.color = BLACK

رنگ هر رأس وضعیت کاوش آن را ردیابی می‌کند: WHITE (کشف‌نشده)، GRAY (کشف‌شده، اما همسایگانش هنوز کاملاً کاوش نشده‌اند)، و BLACK (کاملاً کاوش‌شده). ویژگی d کوتاه‌ترین فاصله از منبع را ثبت می‌کند، و p اسلاف را ثبت می‌کند، که اجازه می‌دهد مسیر کوتاه‌ترین واقعی با دنبال کردن اشاره‌گرهای اسلاف به‌عقب از هر رأس تا منبع بازسازی شود.

چرا BFS کوتاه‌ترین مسیرها را پیدا می‌کند

از آنجا که صف رأس‌ها را دقیقاً به همان ترتیبی که کشف شدند پردازش می‌کند، و BFS فقط یک فاصله به یک رأس در اولین باری که کشف می‌شود اختصاص می‌دهد، فاصله ثبت‌شده هر رأس d تضمین می‌شود کوتاه‌ترین فاصله واقعی‌اش (برحسب تعداد یال) از منبع باشد، ویژگی‌ای که می‌تواند با یک استدلال استقرایی روی سطوح فاصله به‌طور دقیق اثبات شود.

از آنجا که هر رأس دقیقاً یک‌بار enqueue و dequeue می‌شود، و هر یال حداکثر دو بار بررسی می‌شود (یک‌بار از هر نقطه‌انتهایی، در حالت جهت‌دار، یا از هر دو جهت در حالت بدون‌جهت در نظر گرفته می‌شود)، BFS در زمان Θ(V + E) اجرا می‌شود — خطی در اندازه نمایش گراف.

جستجوی عمق‌اول: کاوش تا عمق ممکن اول

Depth-First Search (DFS) استراتژی کاوش مخالف را اتخاذ می‌کند: به‌جای کاوش سطح‌به‌سطح، تا حد ممکن در امتداد هر مسیر فرو می‌رود پیش از بازگشت به عقب، با استفاده از بازگشت (یا یک پشته صریح، که پیش‌تر در این مجموعه بحث شد) به‌جای یک صف.

DFS(G):
  برای هر رأس u در G.V:
      u.color = WHITE
      u.p = NIL
  time = 0
  برای هر رأس u در G.V:
      اگر u.color == WHITE:
          DFS-VISIT(G, u)

DFS-VISIT(G, u):
  time = time + 1
  u.d = time            // زمان کشف
  u.color = GRAY
  برای هر v در Adj[u]:
      اگر v.color == WHITE:
          v.p = u
          DFS-VISIT(G, v)
  u.color = BLACK
  time = time + 1
  u.f = time            // زمان پایان

برخلاف BFS، که معمولاً از یک منبع واحد اجرا می‌شود، DFS همان‌طور که در اینجا نشان داده شد کل گراف را کاوش می‌کند، و به‌طور بالقوه یک جنگل از چند درخت تولید می‌کند اگر گراف کاملاً از هیچ رأس شروع منفردی متصل نباشد.

زمان‌های کشف و پایان

هر رأس یک Discovery Time (زمان کشف) d (وقتی برای اولین‌بار بازدید می‌شود) و یک Finishing Time (زمان پایان) f (وقتی الگوریتم کاوش همه نوادگانش را تمام می‌کند) می‌گیرد. این برچسب‌های زمانی یک ویژگی تودرتوی ظریف دارند.

قضیه پرانتز: برای هر دو رأس u و v،
دقیقاً یکی از این‌ها برقرار است:
۱. بازه‌های [u.d, u.f] و [v.d, v.f] کاملاً مجزا هستند
   (هیچ‌کدام نواده دیگری در جنگل DFS نیست)
۲. [u.d, u.f] کاملاً درون [v.d, v.f] محصور است
   (u نواده v است)
۳. [v.d, v.f] کاملاً درون [u.d, u.f] محصور است
   (v نواده u است)

بازه‌ها هرگز نمی‌توانند "به‌طور جزئی هم‌پوشانی داشته باشند"

این ویژگی ساختاری، همراه با طبقه‌بندی یال‌های مواجه‌شده در طول DFS به Tree Edges، Back Edges، Forward Edges، و Cross Edges، پایه‌ای برای بسیاری الگوریتم گراف که بعداً در این مجموعه پوشش داده می‌شوند فراهم می‌کند.

تشخیص چرخه‌ها با یال‌های عقبی

یک کاربرد به‌ویژه مهم Cycle Detection (تشخیص چرخه) است: یک گراف شامل یک چرخه است اگر و فقط اگر DFS با یک Back Edge (یال عقبی) مواجه شود — یالی که از یک رأس به یکی از اسلاف خودش که هنوز خاکستری رنگ‌شده (در حال حاضر در حال کاوش، هنوز پایان‌نیافته) اشاره می‌کند.

در طول DFS، اگر یال (u, v) بررسی شود و v.color == GRAY،
این یک یال عقبی است، به این معنا که v یک اسلاف u است
که همچنان روی پشته بازگشت فعلی است — یک چرخه وجود دارد

از آنجا که DFS هر رأس را یک‌بار بازدید می‌کند و هر یال را یک‌بار بررسی می‌کند، آن نیز در زمان Θ(V + E) اجرا می‌شود، که با کارایی BFS مطابقت دارد.

چرا این دو پیمایش زیربنای تقریباً هر الگوریتم گراف هستند

BFS و DFS صرفاً تکنیک‌های پیمایش مجزا نیستند؛ آن‌ها پایه ساختاری برای تقریباً هر الگوریتم گراف که بعداً در این مجموعه پوشش داده می‌شود هستند. تضمین کوتاه‌ترین-مسیر BFS در گراف‌های بدون‌وزن مستقیماً به الگوریتم دیجکسترا برای کوتاه‌ترین مسیرهای وزن‌دار گسترش می‌یابد، و ساختار زمان کشف/پایان DFS پایه مرتب‌سازی توپولوژیک، الگوریتم‌های مؤلفه قویاً‌متصل، و تشخیص چرخه استفاده‌شده در سراسر سیستم‌های حل‌وفصل وابستگی است. تسلط بر دقیقاً چگونگی و چرایی این دو پیمایش که تضمین‌های مربوطه‌شان را تولید می‌کنند پیش از پرداختن به هر الگوریتم گراف تخصصی‌تری که ادامه دارد ضروری است.