ملخص Graph للمقابلات البرمجية

مقدمة

الـGraph هو بنية تحتوي مجموعة من الكائنات (عقد أو رؤوس) حيث يمكن أن توجد حواف بين هذه العقد/الرؤوس. ويمكن أن تكون الحواف موجهة أو غير موجهة ويمكن أن تحمل قيماً اختيارياً (Graph موزون). الـTrees هي Graphs غير موجهة يوجد فيها مسار واحد بالضبط بين أي عقدتين ولا يمكن أن توجد فيها دورات.

تُستخدم الـGraphs عادةً لنمذجة العلاقات بين كيانات غير مرتبة، مثل:

الصداقة بين الناس — كل عقدة تمثل شخصاً، وتمثل الحواف بين العقد أن هذين الشخصين صديقان.
المسافات بين المواقع — كل عقدة تمثل موقعاً، وتمثل الحافة بين العقدتين أن هذين الموقعين متصلان. وتمثل قيمة الحافة المسافة.

كن على دراية بتمثيلات الـGraphs المختلفة وAlgorithms البحث في الـGraphs وتعقيداتها الزمنية والمكانية.

مصادر التعلم

قراءات
- From Theory To Practice: Representing Graphs، basecs
- Deep Dive Through A Graph: DFS Traversal، basecs
- Going Broad In A Graph: BFS Traversal، basecs
إضافية (فقط إذا كان لديك وقت)
- Finding The Shortest Path, With A Little Help From Dijkstra، basecs
- Spinning Around In Cycles With Directed Acyclic Graphs، basecs

تمثيلات الـGraphs

قد تُعطى قائمة بالحواف وعليك بناء Graph خاص بك من الحواف حتى تتمكن من إجراء اجتياز عليها. تمثيلات الـGraphs الشائعة هي:

Matrix التجاور
قائمة التجاور
Hash Table من Hash Tables

سيكون استخدام Hash Table من Hash Tables الأسلوب الأبسط أثناء مقابلات الـAlgorithms. ونادراً ما ستحتاج إلى استخدام Matrix أو قائمة تجاور في أسئلة الـGraphs أثناء المقابلات.

في مقابلات الـAlgorithms، تُعطى الـGraphs عادةً في المدخلات على هيئة Arrays ثنائية الأبعاد حيث تكون الخلايا هي العقد ويمكن لكل خلية الانتقال إلى خلاياها المجاورة (أعلى/أسفل/يسار/يمين). لذا من المهم أن تكون على دراية باجتياز Array ثنائية الأبعاد. وعند اجتياز الـArray، تأكد دائماً من أن موضعك الحالي داخل حدود الـArray وأنه لم يُزر من قبل.

الـtime complexity

|V| هو عدد الرؤوس بينما |E| هو عدد الحواف.

الـAlgorithm	Big-O
DFS	O(\|V\| + \|E\|)
BFS	O(\|V\| + \|E\|)
الترتيب الطوبولوجي	O(\|V\| + \|E\|)

أمور يجب الانتباه إليها أثناء المقابلات

قد يكون الـGraph الشجري الشكل Graph يتيح الدورات، ولن يعمل الحل العودي الساذج. وفي تلك الحالة ستحتاج إلى معالجة الدورات والاحتفاظ بمجموعة من العقد المزارة أثناء الاجتياز.
تأكد من أنك تتعقب العقد المزارة بشكل صحيح وأنك لا تزور كل عقدة أكثر من مرة. وإلا فقد ينتهي الأمر بشيفرتك في حلقة لا نهائية.

الحالات الحدّية

Graph فارغ
Graph بعقدة أو عقدتين
Graphs غير متصلة
Graph يحتوي دورات

Algorithms البحث في الـGraphs

شائعة — BFS، DFS
غير شائعة — الترتيب الطوبولوجي، Algorithm Dijkstra
شبه معدومة — Algorithm Bellman-Ford، Algorithm Floyd-Warshall، Algorithm Prim، Algorithm Kruskal. وعلى الأرجح أن محاورك لا يعرفها أيضاً.

DFS

DFS هو Algorithm اجتياز Graphs تستكشف أبعد ما يمكن على طول كل فرع قبل التراجع. ويُستخدم عادةً Stack لتتبع العقد الموجودة على مسار البحث الحالي. ويمكن إنجاز ذلك إما بـStack Recursion ضمني، أو بهيكل بيانات Stack فعلي.

قالب بسيط لإجراء بحث بالعمق أولاً على Array:

def dfs(matrix):
  # Check for an empty matrix/graph.
  if not matrix:
    return []

  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def traverse(i, j):
    if (i, j) in visited:
      return

    visited.add((i, j))
    # Traverse neighbors.
    for direction in directions:
      next_i, next_j = i + direction[0], j + direction[1]
      if 0 <= next_i < rows and 0 <= next_j < cols:
        # Add in question-specific checks, where relevant.
        traverse(next_i, next_j)

  for i in range(rows):
    for j in range(cols):
      traverse(i, j)

BFS

BFS هو Algorithm اجتياز Graphs تبدأ عند عقدة وتستكشف جميع العقد في العمق الحالي، قبل الانتقال إلى العقد في مستوى العمق التالي. ويُستخدم عادةً Queue لتتبع العقد التي تمت مواجهتها ولم تُستكشف بعد.

قالب مماثل لإجراء بحث بالعرض أولاً على الـArray. من المهم استخدام Queues ثنائية الطرف (deque) وليس Arrays/قوائم Python، لأن الإخراج من الـQueue ثنائي الطرف هو O(1) بينما هو O(n) للـArrays.

from collections import deque

def bfs(matrix):
  # Check for an empty matrix/graph.
  if not matrix:
    return []

  rows, cols = len(matrix), len(matrix[0])
  visited = set()
  directions = ((0, 1), (0, -1), (1, 0), (-1, 0))

  def traverse(i, j):
    queue = deque([(i, j)])
    while queue:
      curr_i, curr_j = queue.popleft()
      if (curr_i, curr_j) not in visited:
        visited.add((curr_i, curr_j))
        # Traverse neighbors.
        for direction in directions:
          next_i, next_j = curr_i + direction[0], curr_j + direction[1]
          if 0 <= next_i < rows and 0 <= next_j < cols:
            # Add in question-specific checks, where relevant.
            queue.append((next_i, next_j))

  for i in range(rows):
    for j in range(cols):
      traverse(i, j)

مع أن DFS مطبق باستخدام الـRecursion في هذا المثال، إلا أنه يمكن أيضاً تطبيقه تكرارياً على غرار BFS. ويكمن الاختلاف الجوهري بين هاتين الـAlgorithms في Data Structure الأساسي (يستخدم BFS Queue بينما يستخدم DFS Stack). ويمكن لصنف deque في Python أن يعمل كStack وكQueue معاً.

لنصائح إضافية حول BFS وDFS، يمكنك الرجوع إلى منشور LeetCode هذا

الترتيب الطوبولوجي

الترتيب الطوبولوجي لGraph موجه هو ترتيب خطي لرؤوسه بحيث أنه لكل حافة موجهة uv من الرأس u إلى الرأس v، يأتي u قبل v في الترتيب. وبتحديد أكثر، الترتيب الطوبولوجي هو اجتياز Graph تُزار فيه كل عقدة v فقط بعد زيارة جميع تبعياتها.

يُستخدم الترتيب الطوبولوجي غالباً لجدولة تسلسل من المهام أو الأعمال التي لها تبعيات على مهام/أعمال أخرى. تُمثل الأعمال بالرؤوس، وتوجد حافة من x إلى y إذا كان يجب إكمال العمل x قبل بدء العمل y.

ومثال آخر هو دراسة المساقات في الجامعة حيث تكون للمساقات متطلبات سابقة.

إليك مثالاً حيث الحواف Array من ثنائيات القيم والقيمة الأولى تعتمد على القيمة الثانية.

def graph_topo_sort(num_nodes, edges):
    from collections import deque
    nodes, order, queue = {}, [], deque()
    for node_id in range(num_nodes):
        nodes[node_id] = { 'in': 0, 'out': set() }
    for node_id, pre_id in edges:
        nodes[node_id]['in'] += 1
        nodes[pre_id]['out'].add(node_id)
    for node_id in nodes.keys():
        if nodes[node_id]['in'] == 0:
            queue.append(node_id)
    while len(queue):
        node_id = queue.popleft()
        for outgoing_id in nodes[node_id]['out']:
            nodes[outgoing_id]['in'] -= 1
            if nodes[outgoing_id]['in'] == 0:
                queue.append(outgoing_id)
        order.append(node_id)
    return order if len(order) == num_nodes else None

print(graph_topo_sort(4, [[0, 1], [0, 2], [2, 1], [3, 0]]))
# [1, 2, 0, 3]

أسئلة أساسية

هذه أسئلة أساسية للتدريب عليها إذا كنت تدرس هذا الموضوع.

أسئلة تدريب موصى بها

هذه أسئلة موصى بالتدريب عليها بعد أن تدرس الموضوع وتتدرب على الأسئلة الأساسية.

BFS
- Rotting Oranges
- Minimum Knight Moves (LeetCode Premium)
أي من البحثين
الترتيب الطوبولوجي
- Course Schedule
- Alien Dictionary (LeetCode Premium)

المصدر والرخصة

هذه الصفحة منسوخة من Tech Interview Handbook للمؤلف يانغشون تاي (Yangshun Tay)، النسخة المرجعية e1d28e8، وتُستخدم بموجب رخصة MIT — حقوق النشر (c) 2017-Present ليانغشون تاي. نص الرخصة محفوظ محلياً في /licenses/tech-interview-handbook.txt.