Struktur dan Algoritma Data: Graf

pengenalan

Graf ialah struktur data dengan beberapa bucu(nod) dan tepi(sambungan) di antara mereka.

Pokok ialah contoh graf. Setiap pokok ialah graf tetapi bukan setiap graf adalah pokok, contohnya, graf yang mempunyai kitaran bukan pokok. Pokok akan mempunyai satu punca dan satu laluan unik antara dua nod manakala graf boleh mempunyai banyak punca dan berbilang laluan antara bucu.

Terminologi Asas

Puncak: Nod dalam graf.

Tepi: Sambungan antara dua bucu.

Diarahkan: Apabila sambungan antara dua bucu mempunyai arah. Ini menunjukkan bahawa hanya terdapat satu cara untuk pergi dari satu puncak ke satu puncak yang lain. Contohnya boleh menjadi graf yang menunjukkan bandar(bucu) dan laluan(tepi) antaranya.

Tidak terarah: Apabila sambungan antara dua bucu pada graf berjalan dua arah. Contohnya boleh menjadi graf yang menunjukkan orang (bucu) dihubungkan oleh persahabatan mereka.

Ijazah: Bilangan tepi yang disambungkan ke bucu. Bucu graf terarah boleh mempunyai indegree atau outdegree, iaitu bilangan tepi yang menunjuk ke arah dan menjauhi bucu.

Wajaran: Graf di mana tepi mempunyai nilai sebagai pemberat. Contohnya boleh menjadi peta jalan, di mana jarak antara nod diwakili sebagai pemberat.

Kitaran: Graf yang mempunyai laluan dari sekurang-kurangnya satu bucu kembali ke dirinya sendiri.

Acyclic: Graf yang tidak mempunyai kitaran, iaitu, tiada nod yang mempunyai laluan kembali kepada dirinya sendiri. Graf Akiklik Berarah ialah sejenis graf yang boleh digunakan untuk menunjukkan aliran pemprosesan data.

Padat: Apabila graf mempunyai hampir bilangan tepi maksimum yang mungkin

Jarang: Apabila graf mempunyai hampir bilangan tepi minimum yang mungkin.

Gelung kendiri: Apabila tepi mempunyai satu bucu memaut pada dirinya sendiri.

Berbilang tepi: Apabila graf mempunyai berbilang tepi antara dua bucu.

Mudah: Apabila graf tidak mempunyai gelung kendiri atau berbilang tepi.

Untuk mendapatkan bilangan maksimum tepi dalam graf terarah ringkas: n*(n-1) dengan n ialah bilangan nod.

Untuk mendapatkan bilangan maksimum tepi dalam graf tidak terarah ringkas: n*(n-1)/2 dengan n ialah bilangan nod.

Melaksanakan graf dalam JavaScript

Untuk melaksanakan graf, kita boleh mulakan dengan menyatakan bucu dan tepi graf, di bawah ialah contoh cara melakukan ini memandangkan graf berikut:

const vertices = ["A", "B", "C", "D", "E"];

const edges = [
  ["A", "B"],
  ["A", "D"],
  ["B", "D"],
  ["B", "E"],
  ["C", "D"],
  ["D", "E"],
];

Kemudian kita boleh mencipta fungsi untuk mencari perkara yang bersebelahan dengan bucu yang diberikan:

const findAdjacentNodes = function (node) {
  const adjacentNodes = [];
  for (let edge of edges) {
    const nodeIndex = edge.indexOf(node);
    if (nodeIndex > -1) {
      let adjacentNode = nodeIndex === 0 ? edge[1] : edge[0];
      adjacentNodes.push(adjacentNode);
    }
  }
  return adjacentNodes;
};

Dan satu lagi fungsi untuk menyemak sama ada dua bucu disambungkan:

const isConnected = function (node1, node2) {
  const adjacentNodes = new Set(findAdjacentNodes(node1));
  return adjacentNodes.has(node2);
};

Senarai Bersebelahan

Senarai bersebelahan ialah perwakilan graf di mana semua bucu yang disambungkan ke nod disimpan sebagai senarai. Di bawah ialah graf dan perwakilan visual senarai bersebelahan yang sepadan.

Senarai bersebelahan boleh dilaksanakan dalam JavaScript dengan mencipta dua kelas, kelas Node dan kelas Graf. Kelas Node akan terdiri daripada pembina dan kaedah connect() untuk menyertai dua bucu. Ia juga akan mempunyai kaedah isConnected() dan getAdjacentNodes() yang berfungsi dengan cara yang sama seperti yang ditunjukkan di atas.

class Node {
  constructor(value) {
    this.value = value;
    this.edgesList = [];
  }
  connect(node) {
    this.edgesList.push(node);
    node.edgesList.push(this);
  }
  getAdjNodes() {
    return this.edgesList.map((edge) => edge.value);
  }
  isConnected(node) {
    return this.edgesList.map((edge) => 
    edge.value).indexOf(node.value) > -1;
  }
}

Kelas Graf terdiri daripada pembina dan kaedah addToGraph() yang menambah bucu baharu pada graf.

class Graph {
  constructor(nodes) {
    this.nodes = [...nodes];
  }
  addToGraph(node) {
    this.nodes.push(node);
  }
}

Adjacency Matrix

A 2-D array where each array represents a vertex and each index represents a possible connection between vertices. An adjacency matrix is filled with 0s and 1s, with 1 representing a connection. The value at adjacencyMatrix[node1][node2] will show whether or not there is a connection between the two specified vertices. Below is is a graph and its visual representation as an adjacency matrix.

To implement this adjacency matrix in JavaScript, we start by creating two classes, the first being the Node class:

class Node {
  constructor(value) {
    this.value = value;
  }
}

We then create the Graph class which will contain the constructor for creating the 2-D array initialized with zeros.

class Graph {
  constructor(nodes) {
    this.nodes = [...nodes];
    this.adjacencyMatrix = Array.from({ length: nodes.length },   
    () => Array(nodes.length).fill(0));
   }
}

We will then add the addNode() method which will be used to add new vertices to the graph.

  addNode(node) {
    this.nodes.push(node);
    this.adjacencyMatrix.forEach((row) => row.push(0));
    this.adjacencyMatrix.push(new Array(this.nodes.length).fill(0));
  }

Next is the connect() method which will add an edge between two vertices.

  connect(node1, node2) {
    const index1 = this.nodes.indexOf(node1);
    const index2 = this.nodes.indexOf(node2);

    if (index1 > -1 && index2 > -1) {
      this.adjacencyMatrix[index1][index2] = 1;
      this.adjacencyMatrix[index2][index1] = 1; 
    }
  }

We will also create the isConnected() method which can be used to check if two vertices are connected.

  isConnected(node1, node2) {
    const index1 = this.nodes.indexOf(node1);
    const index2 = this.nodes.indexOf(node2);

    if (index1 > -1 && index2 > -1) {
      return this.adjacencyMatrix[index1][index2] === 1;
    }
    return false;
  }

Lastly we will add the printAdjacencyMatrix() method to the Graph class.

  printAdjacencyMatrix() {
    console.log(this.adjacencyMatrix);
  }

Breadth First Search

Similar to a Breadth First Search in a tree, the vertices adjacent to the current vertex are visited before visiting any subsequent children. A queue is the data structure of choice when performing a Breadth First Search on a graph.

Below is a graph of international airports and their connections and we will use a Breadth First Search to find the shortest route(path) between two airports(vertices).

In order to implement this search algorithm in JavaScript, we will use the same Node and Graph classes we implemented the adjacency list above. We will create a breadthFirstTraversal() method and add it to the Graph class in order to traverse between two given vertices. This method will have the visitedNodes object, which will be used to store the visited vertices and their predecessors. It is initiated as null to show that the first vertex in our search has no predecessors.

breathFirstTraversal(start, end) {
    const queue = [start];
    const visitedNodes = {};
    visitedNodes[start.value] = null;

    while (queue.length > 0) {
      const node = queue.shift();

      if (node.value === end.value) {
        return this.reconstructedPath(visitedNodes, end);
      }
      for (const adjacency of node.edgesList) {
        if (!visitedNodes.hasOwnProperty(adjacency.value)) {
          visitedNodes[adjacency.value] = node;
          queue.push(adjacency);
        }
      }
    }
  }

Once the end vertex is found, we will use the reconstructedPath() method in the Graph class in order to return the shortest path between two vertices. Each vertex is added iteratively to the shortestPath array, which in turn must be reversed in order to come up with the correct order for the shortest path.

reconstructedPath(visitedNodes, endNode) {
    let currNode = endNode;

    const shortestPath = [];

    while (currNode !== null) {
      shortestPath.push(currNode.value);
      currNode = visitedNodes[currNode.value];
    }
    return shortestPath.reverse();
  }

In the case of the graph of international airports, breathFirstTraversal(JHB, LOS) will return JHB -> LUA -> LOS as the shortest path. In the case of a weighted graph, we would use Dijkstra's algorithm to find the shortest path.

Depth First Search

Similar to a depth first search in a tree, this algorithm will fully explore every descendant of a vertex, before backtracking to the root. A stack is the data structure of choice for depth first traversals in a graph.

A depth first search can be used to detect a cycle in a graph. We will use the same graph of international airports to illustrate this in JavaScript.

Similar to the Breadth First Search algorithm above, this implementation of a Depth First Search algorithm in JavaScript will use the previously created Node and Graph classes. We will create a helper function called depthFirstTraversal() and add it to the Graph class.

  depthFirstTraversal(start, visitedNodes = {}, parent = null) {
    visitedNodes[start.value] = true;

    for (const adjacency of start.edgesList) {
      if (!visitedNodes[adjacency.value]) {
        if (this.depthFirstTraversal(adjacency, visitedNodes, start)) {
          return true;
        }
      } else if (adjacency !== parent) {
        return true;
      }
    }

    return false;
  }

This will perform the Depth First Traversal of the graph, using the parent parameter to keep track of the previous vertex and prevent the detection of a cycle when revisiting the parent vertex. Visited vertices will be marked as true in the visitedNodes object. This method will then use recursion to visit previously unvisited vertices. If the vertex has already been visited, we check it against the parent parameter. A cycle has been found if the vertex has already been visited and it is not the parent.

We will also create the wrapper function hasCycle() in the Graph class. This function is used to detect a cycle in a disconnected graph. It will initialize the visitedNodes object and loop through all of the vertices in the graph.

hasCycle() {
    const visitedNodes = {};

    for (const node of this.nodes) {
      if (!visitedNodes[node.value]) {
        if (this.depthFirstTraversal(node, visitedNodes)) {
          return true;
        }
      }
    }
    return false;
  }

In the case of the graph of international airports, the code will return true.

Depth First Traversal of a graph is also useful for pathfinding(not necessarily shortest path) and for solving mazes.

Conclusion

Une solide compréhension des graphiques en tant que structure de données et de leurs algorithmes associés est absolument nécessaire pour approfondir ses études sur les structures de données et les algorithmes. Bien qu'il ne soit pas aussi convivial pour les débutants que les articles précédents de cette série, ce guide devrait s'avérer utile pour approfondir votre compréhension des structures de données et des algorithmes.

Atas ialah kandungan terperinci Struktur dan Algoritma Data: Graf. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!