تطبيق 8 خوارزميات أساسية للرسوم البيانية في جافاسكريبت: دليل شامل

تُعد الرسوم البيانية (Graphs) من أهم هياكل البيانات في علوم الحاسوب، وتُستخدم لنمذجة العلاقات المعقدة بين الكيانات المختلفة. في هذا المقال الشامل، سنغوص في عالم خوارزميات الرسوم البيانية ونستعرض كيفية تطبيق 8 من أهمها باستخدام لغة JavaScript. سنركز على حلول لمشاكل البحث والتركيبات (مثل عمليات الاجتياز، أقصر المسارات، والمطابقة) المستوحاة من كتاب Elements of Programming Interviews الشهير.

على الرغم من أن المنطق الأساسي وراء نمذجة هذه المشاكل لا يعتمد على لغة برمجة معينة، إلا أن مقتطفات الشفرة التي سنقدمها هنا تستفيد من بعض خصائص JavaScript الفريدة. لقد قمنا بتقسيم حل كل مشكلة إلى ثلاثة أقسام رئيسية: نظرة عامة على الحل، الشفرة الزائفة (Pseudocode)، وأخيرًا الشفرة الفعلية بلغة JavaScript.

لضمان فهمك الكامل وقدرتك على اختبار هذه الحلول، يمكنك تشغيل مقتطفات الشفرة مباشرةً في أدوات المطور (Dev Tools) بمتصفح Chrome، أو استخدام بيئة Node.js لتشغيلها من سطر الأوامر، مما يمنحك تجربة عملية لا تقدر بثمن.

تنفيذ الرسوم البيانية (Graph Implementation)

تُعد قائمة التجاور (Adjacency List) ومصفوفة التجاور (Adjacency Matrix) هما التمثيلان الأكثر شيوعًا للرسوم البيانية. في سياق المشاكل التي سنتناولها، والتي غالبًا ما تكون لرسوم بيانية متفرقة (Sparse Graphs) تحتوي على عدد قليل من الحواف، يُفضل استخدام قائمة التجاور. يعود هذا التفضيل إلى أن عمليات الرأس (Vertex Operations) في هذا النهج تستغرق وقتًا ثابتًا (مثل إضافة رأس O(1)) ووقتًا خطيًا (مثل حذف رأس O(V+E))، حيث V هو عدد الرؤوس و E هو عدد الحواف. لذلك، سنعتمد هذا التنفيذ في معظم الأمثلة.

دعونا نبدأ بتنفيذ بسيط لرسوم بيانية غير موجهة (Undirected) وغير موزونة (Unweighted) باستخدام قائمة التجاور. سنستخدم كائنًا (adjacencyList) يحتوي على جميع رؤوس الرسم البياني كمفاتيح (keys)، وستكون القيم المقابلة لها مصفوفة (array) تحتوي على جميع الرؤوس المتجاورة. على سبيل المثال، إذا كان الرأس 1 متصلًا بالرأسين 2 و 4، فستكون قائمة التجاور كالتالي: { 1 : [ 2, 4 ] }، وهكذا لبقية الرؤوس.

لبناء الرسم البياني، سنحتاج إلى دالتين أساسيتين: addVertex و addEdge. تُستخدم الدالة addVertex لإضافة رأس جديد إلى القائمة. أما الدالة addEdge فتُستخدم لربط الرؤوس عن طريق إضافة الرؤوس المتجاورة إلى مصفوفتي المصدر (source) والوجهة (destination)، نظرًا لأن الرسم البياني غير موجه. لتحويله إلى رسم بياني موجه (Directed Graph)، يمكننا ببساطة إزالة الأسطر 14-16 و 18 من الشفرة أدناه. قبل إزالة أي رأس، يجب علينا أولاً المرور عبر مصفوفة الرؤوس المجاورة وإزالة جميع الاتصالات المحتملة لهذا الرأس.

رسم بياني غير موجه وغير موزون مُنفذ باستخدام قائمة التجاور.

 class Graph {
  constructor () {
    this.adjacencyList = {};
  }

  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }

  addEdge(source, destination) {
    if (!this.adjacencyList[source]) {
      this.addVertex(source);
    }
    if (!this.adjacencyList[destination]) {
      this.addVertex(destination);
    }
    this.adjacencyList[source].push(destination);
    this.adjacencyList[destination].push(source);
  }

  removeEdge(source, destination) {
    this.adjacencyList[source] = this.adjacencyList[source].filter(
      vertex => vertex !== destination
    );
    this.adjacencyList[destination] = this.adjacencyList[destination].filter(
      vertex => vertex !== source
    );
  }

  removeVertex(vertex) {
    while (this.adjacencyList[vertex]) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }
}

اجتياز الرسوم البيانية (Graph Traversals)

بناءً على تنفيذنا للرسوم البيانية في القسم السابق، سنتناول الآن اثنتين من أهم خوارزميات اجتياز الرسوم البيانية: البحث أولاً بالعمق (Depth First Search - DFS) والبحث أولاً بالعرض (Breadth First Search - BFS).

البحث أولاً بالعرض (Breadth First Search – BFS)

تُعد خوارزمية BFS طريقة منهجية لزيارة رؤوس الرسم البياني مستوى تلو الآخر. لمنع زيارة نفس الرأس أكثر من مرة، نحتفظ بكائن visited لتتبع الرؤوس التي تمت زيارتها. نظرًا لأننا نحتاج إلى معالجة الرؤوس بترتيب “الأول يدخل، الأول يخرج” (First In First Out - FIFO)، فإن بنية بيانات الطابور (Queue) هي الخيار الأمثل لهذه الخوارزمية.

 function BFS
  Initialize an empty queue, empty 'result' array & a 'visited' map
  Add the starting vertex to the queue & visited map
  While Queue is not empty :
    - Dequeue and store current vertex
    - Push current vertex to result array
    - Iterate through current vertex's adjacency list :
      - For each adjacent vertex, if vertex is unvisited :
        - Add vertex to visited map
        - Enqueue vertex
  Return result array

البحث أولاً بالعمق (Depth First Search – DFS)

تختلف خوارزمية DFS عن BFS في طريقة الزيارة؛ فهي تستكشف الرؤوس بعمق قدر الإمكان قبل التراجع. نظرًا لأننا نحتاج إلى معالجة الرؤوس بترتيب “الأخير يدخل، الأول يخرج” (Last In First Out - LIFO)، فإن بنية بيانات المكدس (Stack) هي الأنسب هنا. نبدأ من رأس معين، ثم ندفع الرؤوس المجاورة له إلى المكدس. عندما يتم إخراج رأس من المكدس، يتم تمييزه كمُزار في كائن visited، ثم يتم دفع رؤوسه المجاورة إلى المكدس. بهذه الطريقة، تستكشف الخوارزمية دائمًا مستوى جديدًا من العمق.
يمكن أيضًا تنفيذ DFS بشكل تكراري (Recursively) باستخدام استدعاءات المكدس الجوهرية للغة البرمجة، ويبقى المنطق الأساسي والتعقيد الزمني كما هو.

 function DFS
  Initialize an empty stack, empty 'result' array & a 'visited' map
  Add the starting vertex to the stack & visited map
  While Stack is not empty :
    - Pop and store current vertex
    - Push current vertex to result array
    - Iterate through current vertex's adjacency list :
      - For each adjacent vertex, if vertex is unvisited :
        - Add vertex to visited map
        - Push vertex to stack
  Return result array

Graph.prototype.bfs = function (start) {
  const queue = [start];
  const result = [];
  const visited = {};
  visited[start] = true;
  let currentVertex;

  while (queue.length) {
    currentVertex = queue.shift();
    result.push(currentVertex);

    this.adjacencyList[currentVertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.push(neighbor);
      }
    });
  }
  return result;
}

Graph.prototype.dfsRecursive = function (start) {
  const result = [];
  const visited = {};
  const adjacencyList = this.adjacencyList;

  (function dfs(vertex) {
    if (!vertex) return null;
    visited[vertex] = true;
    result.push(vertex);

    adjacencyList[vertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        return dfs(neighbor);
      }
    })
  })(start);
  return result;
}

Graph.prototype.dfsIterative = function (start) {
  const result = [];
  const stack = [start];
  const visited = {};
  visited[start] = true;
  let currentVertex;

  while (stack.length) {
    currentVertex = stack.pop();
    result.push(currentVertex);

    this.adjacencyList[currentVertex].forEach(neighbor => {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        stack.push(neighbor);
      }
    });
  }
  return result;
}

مشكلة البحث في المتاهة (Search Maze Problem)

نص المشكلة:

“بالنظر إلى مصفوفة ثنائية الأبعاد تحتوي على مدخلات بيضاء وسوداء تمثل متاهة بنقاط دخول وخروج محددة، أوجد مسارًا من نقطة الدخول إلى نقطة الخروج، إن وجد.” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

سنقوم بتمثيل المداخل البيضاء بالأصفار (0) والمداخل السوداء بالآحاد (1). تمثل المداخل البيضاء المناطق المفتوحة، بينما تمثل المداخل السوداء الجدران. يتم تمثيل نقاط الدخول والخروج كمصفوفة، حيث يشغل الفهرس 0 والفهرس 1 مؤشرات الصف والعمود على التوالي.

متاهة ممثلة بمصفوفة ثنائية الأبعاد.

الحل:

للتنقل بين المواقع المختلفة في المتاهة، سنقوم بتضمين الحركات الأربع الممكنة (يمين، أسفل، يسار، أعلى؛ بدون حركات قطرية) في مصفوفة directions:

[ [ 0 , 1 ], [ 1 , 0 ], [ 0 , -1 ], [ -1 , 0 ] ]

لتتبع الخلايا التي زرناها بالفعل، سنقوم باستبدال المداخل البيضاء (0) بمداخل سوداء (1). في الأساس، نستخدم خوارزمية DFS بشكل تكراري لاجتياز المتاهة. الشرط الأساسي الذي ينهي التكرار هو إما أن نكون قد وصلنا إلى نقطة الخروج ونعيد true، أو أننا زرنا كل مدخل أبيض ولم نجد المسار ونعيد false.

من الأمور الهامة الأخرى التي يجب مراعاتها هو التأكد من أننا دائمًا ضمن حدود المتاهة، وأننا نتقدم فقط إذا كنا في مدخل أبيض. ستتولى الدالة isFeasible هذه المهمة.

• التعقيد الزمني: O(V+E)، حيث V هو عدد الرؤوس (الخلايا) و E هو عدد الحواف (الحركات الممكنة).

 function hasPath
  Start at the entry point
  While exit point has not been reached
    1. Move to the top cell
    2. Check if position is feasible (white cell & within boundary)
    3. Mark cell as visited (turn it into a black cell)
    4. Repeat steps 1-3 for the other 3 directions

 var hasPath = function (maze, start, destination) {
  maze[start[0]][start[1]] = 1;
  return searchMazeHelper(maze, start, destination);
};

function searchMazeHelper(maze, current, end) {
  // dfs
  if (current[0] == end[0] && current[1] == end[1]) {
    return true;
  }

  let neighborIndices, neighbor;
  // Indices: 0->top,1->right, 2->bottom, 3->left
  let directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0]
  ];

  for (const direction of directions) {
    neighborIndices = [current[0] + direction[0], current[1] + direction[1]];
    if (isFeasible(maze, neighborIndices)) {
      maze[neighborIndices[0]][neighborIndices[1]] = 1;
      if (searchMazeHelper(maze, neighborIndices, end)) {
        return true;
      }
    }
  }
  return false;
}

function isFeasible(maze, indices) {
  let x = indices[0],
    y = indices[1];
  return x >= 0 && x < maze.length && y >= 0 && y < maze[x].length && maze[x][y] === 0;
}

var maze = [
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [1, 1, 0, 1, 1],
  [0, 0, 0, 0, 0]
]
hasPath(maze, [0, 4], [3, 2]);

مشكلة تلوين مصفوفة بوليانية (Paint a Boolean Matrix)

نص المشكلة:

“نفذ روتينًا يأخذ مصفوفة بوليانية A من الأبعاد n x m، بالإضافة إلى إدخال (x, y)، ويقوم بقلب لون المنطقة المرتبطة بـ (x, y).” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

سيتم تمثيل اللونين بالأصفار (0) والآحاد (1). في المثال أدناه، نبدأ من مركز المصفوفة ([1,1]). لاحظ أنه من هذا الموضع، لا يمكننا الوصول إلا إلى الجزء العلوي الأيسر من المصفوفة المثلثية. لا يمكن الوصول إلى الموضع الأيمن السفلي ([2,2]). وبالتالي، في نهاية العملية، سيكون هذا هو اللون الوحيد الذي لم يتم قلبه.

مصفوفة بوليانية n x m قبل وبعد قلب الألوان.

الحل:

على غرار المشكلة السابقة، سنقوم بتعريف مصفوفة لتحديد الحركات الأربع الممكنة. سنستخدم خوارزمية BFS لاجتياز الرسم البياني. سنقوم بتعديل دالة isFeasible قليلًا؛ ستظل تتحقق مما إذا كان الموضع الجديد ضمن حدود المصفوفة. الشرط الآخر هو أن يكون الموضع الجديد بنفس لون الموضع السابق. إذا استوفى الموضع الجديد هذه المتطلبات، فسيتم قلب لونه.

• التعقيد الزمني: O(mn)، حيث m هو عدد الصفوف و n هو عدد الأعمدة في المصفوفة.

 function flipColor
  Start at the passed coordinates and store the color
  Initialize queue
  Add starting position to queue
  While Queue is not empty :
    - Dequeue and store current position
    - Move to the top cell
      1. Check if cell is feasible
      2. If feasible,
        - Flip color
        - Enqueue cell
      3. Repeat steps 1-2 for the other 3 directions

 function flipColor(image, x, y) {
  let directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0]
  ];
  let color = image[x][y];
  let queue = [];
  image[x][y] = Number(!color);
  queue.push([x, y]);

  let currentPosition, neighbor;
  while (queue.length) {
    currentPosition = queue.shift();
    for (const direction of directions) {
      neighbor = [currentPosition[0] + direction[0], currentPosition[1] + direction[1]];
      if (isFeasible(image, neighbor, color)) {
        image[neighbor[0]][neighbor[1]] = Number(!color);
        queue.push([neighbor[0], neighbor[1]]);
      }
    }
  }
  return image;
}

function isFeasible(image, indices, color) {
  let x = indices[0],
    y = indices[1];
  return x >= 0 && x < image.length && y >= 0 && y < image[x].length && image[x][y] == color;
}

var image = [
  [1, 1, 1],
  [1, 1, 0],
  [1, 0, 1]
];
flipColor(image, 1, 1);

مشكلة حساب المناطق المحصورة (Compute Enclosed Regions)

نص المشكلة:

“لتكن A مصفوفة ثنائية الأبعاد مدخلاتها إما W أو B. اكتب برنامجًا يأخذ A، ويستبدل جميع المدخلات W التي لا يمكنها الوصول إلى الحدود بـ B.” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

الشبكات قبل وبعد تحديد المناطق المحصورة.

الحل:

بدلاً من المرور على جميع المدخلات للبحث عن مدخلات W المحصورة، من الأكثر كفاءة أن نبدأ بمدخلات W الموجودة على الحدود. نقوم باجتياز الرسم البياني من هذه النقاط وتمييز جميع مدخلات W المتصلة بها. هذه المدخلات المميزة مضمونة بأنها ليست محصورة، لأنها متصلة بمدخل W على حدود اللوحة. هذه المعالجة المسبقة هي في الأساس مكمل لما يجب أن يحققه البرنامج.

بعد ذلك، يتم المرور على المصفوفة A مرة أخرى، ويتم تغيير مدخلات W غير المميزة (التي ستكون هي المحصورة) إلى مدخلات B. سنتتبع مدخلات W المميزة وغير المميزة باستخدام مصفوفة بوليانية (Boolean array) بنفس أبعاد A، حيث يتم تعيين المدخل المميز إلى true.

• التعقيد الزمني: O(mn)، حيث m هو عدد الصفوف و n هو عدد الأعمدة في المصفوفة.

 function fillSurroundedRegions
  1. Initialize a 'visited' array of same length as the input array pre-filled with 'false' values
  2. Start at the boundary entries
  3. If the boundary entry is a W entry and unmarked : Call markBoundaryRegion function
  4. Iterate through A and change the unvisited W entry to B

 function markBoundaryRegion
  Start with a boundary W entry
  Traverse the grid using BFS
  Mark the feasible entries as true

 function fillSurroundedRegions(board) {
  if (!board.length) {
    return;
  }

  const numRows = board.length,
    numCols = board[0].length;
  let visited = [];
  for (let i = 0; i < numRows; i++) {
    visited.push(new Array(numCols).fill(false, 0, numCols));
  }

  for (let i = 0; i < board.length; i++) {
    if (board[i][0] == 'W' && !visited[i][0]) {
      markBoundaryRegion(i, 0, board, visited);
    }
    if (board[i][board.length - 1] == 'W' && !visited[i][board.length - 1]) {
      markBoundaryRegion(i, board.length - 1, board, visited);
    }
  }

  for (let j = 0; j < board[0].length; j++) {
    if (board[0][j] == 'W' && !visited[0][j]) {
      markBoundaryRegion(0, j, board, visited);
    }
    if (board[board.length - 1][j] == 'W' && !visited[board.length - 1][j]) {
      markBoundaryRegion(board.length - 1, j, board, visited);
    }
  }

  for (let i = 1; i < board.length - 1; i++) {
    for (let j = 1; j < board.length - 1; j++) {
      if (board[i][j] == 'W' && !visited[i][j]) {
        board[i][j] = 'B';
      }
    }
  }
  return board;
}

function markBoundaryRegion(i, j, board, visited) {
  let directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0]
  ];
  const queue = [];
  queue.push([i, j]);
  visited[i][j] = true;

  let currentPosition, neighbor;
  while (queue.length) {
    currentPosition = queue.shift();
    for (const direction of directions) {
      neighbor = [currentPosition[0] + direction[0], currentPosition[1] + direction[1]];
      if (isFeasible(board, visited, neighbor)) {
        visited[neighbor[0]][neighbor[1]] = true;
        queue.push(neighbor);
      }
    }
  }
}

function isFeasible(board, visited, neighbor) {
  let x = neighbor[0],
    y = neighbor[1];
  return x >= 0 && x < board.length && y >= 0 && y < board[x].length && board[x][y] == 'W' && !visited[x][y];
}

var board = [
  ['B', 'B', 'B', 'B'],
  ['W', 'B', 'W', 'B'],
  ['B', 'W', 'W', 'B'],
  ['B', 'B', 'B', 'B']
];
fillSurroundedRegions(board);

اكتشاف الجمود (Deadlock Detection) – دورة في رسم بياني موجه

نص المشكلة:

“تستخدم إحدى خوارزميات اكتشاف الجمود رسمًا بيانيًا للانتظار (wait-for graph) لتتبع العمليات التي تنتظرها عملية معينة حاليًا. في رسم بياني الانتظار، تُمثل العمليات كعُقد، وتشير الحافة من العملية P إلى Q إلى أن Q تحتفظ بمورد تحتاجه P، وبالتالي تنتظر P من Q أن تحرر قفلها على هذا المورد. تشير الدورة (cycle) في هذا الرسم البياني إلى احتمال حدوث جمود. هذا يدفعنا إلى المشكلة التالية: اكتب برنامجًا يأخذ رسمًا بيانيًا موجهًا كمدخل ويتحقق مما إذا كان الرسم البياني يحتوي على دورة.” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

مثال على رسم بياني للانتظار (wait-for graph). (أ)

في رسم بياني الانتظار أعلاه، سيكتشف برنامجنا لاكتشاف الجمود دورة واحدة على الأقل ويعيد true. لهذه الخوارزمية، سنستخدم تطبيقًا مختلفًا قليلًا للرسم البياني الموجه لاستكشاف هياكل بيانات أخرى. ما زلنا ننفذه باستخدام قائمة التجاور (adjacency list)، ولكن بدلاً من كائن (map)، سنخزن الرؤوس في مصفوفة (array). سيتم نمذجة العمليات كرؤوس تبدأ من العملية رقم 0. سيتم نمذجة التبعية بين العمليات كحواف بين الرؤوس. سيتم تخزين الحواف (الرؤوس المتجاورة) في قائمة مرتبطة (Linked List)، والتي بدورها يتم تخزينها في الفهرس الذي يتوافق مع رقم العملية.

 class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
  }

  insertAtHead(data) {
    let temp = new Node(data);
    temp.next = this.head;
    this.head = temp;
    return this;
  }

  getHead() {
    return this.head;
  }
}

class Graph {
  constructor(vertices) {
    this.vertices = vertices;
    this.list = [];
    for (let i = 0; i < vertices; i++) {
      let temp = new LinkedList();
      this.list.push(temp);
    }
  }

  addEdge(source, destination) {
    if (source < this.vertices && destination < this.vertices) {
      this.list[source].insertAtHead(destination);
    }
    return this;
  }
}

تنفيذ رسم بياني الانتظار (wait-for graph). (أ)

الحل:

سيتم تعيين ثلاثة ألوان مختلفة لكل رأس: أبيض (white)، رمادي (gray)، وأسود (black). في البداية، تكون جميع الرؤوس بيضاء. عندما يتم معالجة رأس ما، يتم تلوينه بالرمادي، وبعد الانتهاء من معالجته، يتم تلوينه بالأسود. نستخدم خوارزمية البحث أولاً بالعمق (DFS) لاجتياز الرسم البياني.

إذا وُجدت حافة من رأس رمادي إلى رأس رمادي آخر، فهذا يعني أننا اكتشفنا حافة خلفية (back edge) – وهي حلقة ذاتية أو حافة تتصل بأحد أسلافها – وبالتالي يتم اكتشاف دورة في الرسم البياني.

• التعقيد الزمني: O(V+E)، حيث V هو عدد الرؤوس و E هو عدد الحواف.

 function isDeadlocked
  Color all vertices white
  Run DFS on the vertices
    1. Mark current node Gray
    2. If adjacent vertex is Gray, return true
    3. Mark current node Black
  Return false

 const Colors = {
  WHITE: 'white',
  GRAY: 'gray',
  BLACK: 'black'
}
Object.freeze(Colors);

function isDeadlocked(g) {
  let color = [];
  for (let i = 0; i < g.vertices; i++) {
    color[i] = Colors.WHITE;
  }

  for (let i = 0; i < g.vertices; i++) {
    if (color[i] == Colors.WHITE) {
      if (detectCycle(g, i, color)) {
        return true;
      }
    }
  }
  return false;
};

function detectCycle(g, currentVertex, color) {
  color[currentVertex] = Colors.GRAY;
  let neighbor;
  let nextNode = g.list[currentVertex].getHead();

  while (nextNode !== null) {
    neighbor = nextNode.data;
    if (color[neighbor] == Colors.GRAY) {
      return true;
    }
    if (color[neighbor] == Colors.WHITE && detectCycle(g, neighbor, color)) {
      return true;
    }
    nextNode = nextNode.next;
  }
  color[currentVertex] = Colors.BLACK;
  return false;
}

let g = new Graph(3);
g.addEdge(0, 1);
g.addEdge(0, 2);
isDeadlocked(g);

مشكلة استنساخ الرسم البياني (Clone Graph)

نص المشكلة:

“اعتبر نوع رأس (vertex type) لرسم بياني موجه يحتوي على حقلين: تسمية عدد صحيح (integer label) وقائمة من المراجع (references) إلى رؤوس أخرى. صمم خوارزمية تأخذ مرجعًا إلى رأس u، وتنشئ نسخة من الرسم البياني على الرؤوس التي يمكن الوصول إليها من u. أعد نسخة من u.” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

الحل:

لحل هذه المشكلة، سنحتفظ بخريطة (map) تربط الرأس الأصلي بنظيره المستنسخ. ثم نقوم بنسخ الحواف (edges). سنستخدم خوارزمية BFS لزيارة الرؤوس المتجاورة (الحواف).

• التعقيد الزمني: O(N)، حيث N هو العدد الإجمالي للعقد (الرؤوس).

 function cloneGraph
  Initialize an empty map
  Run BFS
  Add original vertex as key and clone as value to map
  Copy over edges if vertices exist in map
  Return clone

 class GraphVertex {
  constructor(value) {
    this.value = value;
    this.edges = [];
  }
}

function cloneGraph(g) {
  if (g == null) {
    return null;
  }

  let vertexMap = new Map();
  let queue = [g];
  vertexMap.set(g, new GraphVertex(g.value));

  while (queue.length) {
    let currentVertex = queue.shift();
    currentVertex.edges.forEach(v => {
      if (!vertexMap.has(v)) {
        vertexMap.set(v, new GraphVertex(v.value));
        queue.push(v);
      }
      vertexMap.get(currentVertex).edges.push(vertexMap.get(v));
    });
  }
  return vertexMap.get(g);
}

let n1 = new GraphVertex(1);
let n2 = new GraphVertex(2);
let n3 = new GraphVertex(3);
let n4 = new GraphVertex(4);

n1.edges.push(n2, n4);
n2.edges.push(n1, n3);
n3.edges.push(n2, n4);
n4.edges.push(n1, n3);

cloneGraph(n1);

مشكلة إنشاء اتصالات سلكية (Making Wired Connections)

نص المشكلة:

“صمم خوارزمية تأخذ مجموعة من المسامير (pins) ومجموعة من الأسلاك التي تربط أزواجًا من المسامير، وتحدد ما إذا كان من الممكن وضع بعض المسامير في النصف الأيسر من لوحة الدوائر المطبوعة (PCB)، والبقية في النصف الأيمن، بحيث يكون كل سلك بين النصف الأيسر والأيمن. أعد هذا التقسيم، إن وجد.” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

مثال على تقسيم المسامير على لوحة الدوائر المطبوعة.

الحل:

لحل هذه المشكلة، سنقوم بنمذجة المجموعة كرسم بياني (Graph)، حيث تمثل المسامير الرؤوس (Vertices) وتمثل الأسلاك التي تربطها الحواف (Edges). سننفذ الرسم البياني باستخدام قائمة الحواف (Edge List).

التقسيم الموصوف في نص المشكلة ممكن فقط إذا أمكن تقسيم الرؤوس (المسامير) إلى “مجموعتين مستقلتين، U و V، بحيث تربط كل حافة (u,v) رأسًا من U برأس من V أو رأسًا من V برأس من U“. يُعرف هذا النوع من الرسوم البيانية بالرسم البياني ثنائي الأجزاء (Bipartite Graph).

للتحقق مما إذا كان الرسم البياني ثنائي الأجزاء، سنستخدم تقنية تلوين الرسوم البيانية (Graph Coloring). نظرًا لأننا نحتاج إلى مجموعتين من المسامير، يجب علينا التحقق مما إذا كان الرسم البياني قابلًا للتلوين بلونين (سنمثلهما بـ 0 و 1). في البداية، تكون جميع الرؤوس غير ملونة (-1). إذا تم تعيين نفس اللون لرأسين متجاورين، فإن الرسم البياني ليس ثنائي الأجزاء. لا يمكن تعيين لونين بالتناوب لرسم بياني يحتوي على دورة بطول فردي باستخدام لونين فقط، لذلك يمكننا تلوين الرسم البياني بشكل جشع (greedily).

خطوة إضافية: سنتعامل مع حالة الرسم البياني غير المتصل (disconnected graph). ستتولى حلقة for الخارجية هذه المهمة من خلال المرور على جميع الرؤوس.

• التعقيد الزمني: O(V+E)، حيث V هو عدد الرؤوس و E هو عدد الحواف.

 function isBipartite
  1. Initialize an array to store uncolored vertices
  2. Iterate through all vertices one by one
  3. Assign one color (0) to the source vertex
  4. Use DFS to reach the adjacent vertices
  5. Assign the neighbors a different color (1 - current color)
  6. Repeat steps 3 to 5 as long as it satisfies the two-colored constraint
  7. If a neighbor has the same color as the current vertex, break the loop and return false

 function isBipartite(graph) {
  let color = [];
  for (let i = 0; i < graph.length; i++) {
    color[i] = -1;
  }

  for (let i = 0; i < graph.length; i++) {
    if (color[i] == -1) {
      let stack = [];
      stack.push(i);
      color[i] = 0;

      let node;
      while (stack.length) {
        node = stack.pop();

        for (const neighbor of graph[node]) {
          if (color[neighbor] == -1) {
            stack.push(neighbor);
            color[neighbor] = 1 - color[node];
          } else if (color[neighbor] == color[node]) {
            return false;
          }
        }
      }
    }
  }
  return true;
}

isBipartite([
  [],
  [2, 4, 6],
  [1, 4, 8, 9],
  [7, 8],
  [1, 2, 8, 9],
  [6, 9],
  [1, 5, 7, 8, 9],
  [3, 6, 9],
  [2, 3, 4, 6, 9],
  [2, 4, 5, 6, 7, 8]
]);

مشكلة تحويل سلسلة نصية إلى أخرى (Transform one string to another)

نص المشكلة:

“بالنظر إلى قاموس D وسلسلتين نصيتين s و f، اكتب برنامجًا لتحديد ما إذا كانت s تنتج f. افترض أن جميع الأحرف هي أحرف صغيرة. إذا كانت s تنتج f، فأخرج طول أقصر تسلسل إنتاج؛ وإلا، أخرج -1.” – عزيز، عدنان، وآخرون. Elements of Programming Interviews.

على سبيل المثال، إذا كان القاموس D هو ["hot", "dot", "dog", "lot", "log", "cog"]، وكانت السلسلة s هي "hit" والسلسلة f هي "cog"، فإن طول أقصر تسلسل إنتاج هو 5، كالتالي: "hit" -> "hot" -> "dot" -> "dog" -> "cog".

الحل:

لحل هذه المشكلة، سنقوم بتمثيل السلاسل النصية كرؤوس (vertices) في رسم بياني غير موجه وغير موزون. ستكون هناك حافة بين رأسين إذا كانت السلاسل النصية المقابلة تختلف في حرف واحد على الأكثر. سنقوم بتنفيذ دالة (compareStrings) تحسب الفرق في الأحرف بين سلسلتين نصيتين.

بالاستناد إلى المثال السابق، ستكون الرؤوس في رسمنا البياني كالتالي:

{hit, hot, dot, dog, lot, log, cog}

وستكون الحواف، ممثلة بنهج قائمة التجاور الذي ناقشناه في قسم “تنفيذ الرسوم البيانية”، كالتالي:

{ "hit" : [ "hot" ], "hot" : [ "dot" , "lot" ], "dot" : [ "hot" , "dog" , "lot" ], "dog" : [ "dot" , "lot" , "cog" ], "lot" : [ "hot" , "dot" , "log" ], "log" : [ "dog" , "lot" , "cog" ], "cog" : [ "dog" , "log" ] }

بمجرد الانتهاء من بناء الرسم البياني، تتحول المشكلة إلى إيجاد أقصر مسار من عقدة البداية إلى عقدة النهاية. يمكن حساب هذا بشكل طبيعي باستخدام خوارزمية البحث أولاً بالعرض (Breadth First Search - BFS).

• التعقيد الزمني: O(M * M * N)، حيث M هو طول كل كلمة و N هو العدد الإجمالي للكلمات في القاموس.

 function compareStrings
  Compare two strings char by char
  Return how many chars differ

 function transformString
  1. Build graph using compareStrings function. Add edges if and only if the two strings differ by 1 character
  2. Run BFS and increment length
  3. Return length of production sequence

 function transformString(beginWord, endWord, wordList) {
  let graph = buildGraph(wordList, beginWord);
  if (!graph.has(endWord)) return 0;

  let queue = [beginWord];
  let visited = new Map();
  visited.set(beginWord, true);

  let count = 1;
  while (queue.length) {
    let size = queue.length;
    for (let i = 0; i < size; i++) {
      let currentWord = queue.shift();
      if (currentWord === endWord) {
        return count;
      }
      if (graph.has(currentWord)) {
        graph.get(currentWord).forEach(neighbor => {
          if (!visited.has(neighbor)) {
            queue.push(neighbor);
            visited.set(neighbor, true);
          }
        })
      }
    }
    count++;
  }
  return 0;
};

function compareStrings(str1, str2) {
  let diff = 0;
  for (let i = 0; i < str1.length; i++) {
    if (str1[i] !== str2[i]) diff++;
  }
  return diff;
}

function buildGraph(wordList, beginWord) {
  let graph = new Map();
  wordList.forEach((word) => {
    if (!graph.has(word)) {
      graph.set(word, []);
    }
  });

  if (!graph.has(beginWord)) {
    graph.set(beginWord, []);
  }

  let allWords = Array.from(graph.keys());
  allWords.forEach((word1) => {
    allWords.forEach((word2) => {
      if (word1 !== word2 && compareStrings(word1, word2) === 1) {
        graph.get(word1).push(word2);
      }
    });
  });

  return graph;
}

الخلاصة التقنية

نأمل أن تكون قد أدركت من خلال هذا المقال أن الجزء الأكثر تحديًا في التعامل مع مشاكل الرسوم البيانية يكمن في كيفية نمذجة المشكلة نفسها كرسم بياني فعال. بمجرد إتقان هذه الخطوة، يمكن استخدام أو تعديل خوارزميات اجتياز الرسوم البيانية الأساسية، مثل BFS و DFS، للحصول على النتائج المرجوة بكفاءة.

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

لتوسيع مجموعتك من الأدوات البرمجية، نوصي باستكشاف خوارزميات الرسوم البيانية الأخرى الهامة، مثل:

• الترتيب الطوبولوجي (Topological Ordering).
• خوارزميات أقصر المسارات (مثل Dijkstra و Floyd Warshall).
• خوارزميات أشجار الامتداد الدنيا (Minimum Spanning Trees) مثل Prim و Kruskal.

إن فهم هذه المفاهيم وتطبيقها سيعزز بشكل كبير قدراتك في حل المشكلات المعقدة في عالم البرمجة وهياكل البيانات.

المراجع:

• Aziz, Adnan, et al. Elements of Programming Interviews. 2nd ed., CreateSpace Independent Publishing Platform, 2012.