Data Structures and Algorithms: Graphs

Introduction

A graph is a data structure with a number of vertices(nodes) and edges(connections) between them.

A tree is an example of a graph. Every tree is a graph but not every graph is a tree, for example, graphs that have cycles are not trees. A tree will have one root and one unique path between two nodes whilst a graph can have many roots and multiple paths between vertices.

Basic Terminology

Vertex: A node in a graph.

Edge: The connection between two vertices.

Directed: When the connection between two vertices has a direction. This implies that there is only one way to get from one vertex to another. An example could be graph showing the cities(vertices) and the routes(edges) between them.

Undirected: When the connection between two vertices on a graph goes both ways. An example could be a graph showing people(vertices) connected by their friendships.

Degree: The number of edges connected to a vertex. The vertices of a directed graph can have an indegree or an outdegree, which is the number of edges pointing towards and away from the vertex respectively.

Weighted: A graph in which the edges have values as weights. An example could be a road map, where the distances between nodes are represented as weights.

Cyclic: A graph that has a path from at least one vertex back to itself.

Acyclic: A graph that has no cycles, that is to say, no node has a path back to itself. A Directed Acyclic Graph is a type of graph that can be used to show data processing flows.

Dense: When a graph has close to the maximum possible number of edges

Sparse: When a graph has close to the minimum possible number of edges.

Self-loop: When an edge has one vertex linking to itself.

Multi-edge: When a graph has multiple edges between two vertices.

Simple: When a graph has no self-loops nor multi-edges.

To get the maximum number of edges in a simple directed graph: n*(n-1) where n is the number of nodes.

To get the maximum number of edges in a simple undirected graph: n*(n-1)/2 where n is the number of nodes.

Implementing graphs in JavaScript

To implement a graph, we can start by specifying the vertices and edges of a graph, below is an example of how to do this given the following graph:

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

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

Then we can create a function to find what is adjacent to a given vertex:

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;
};

And another function to check if two vertices are connected:

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

Adjacency List

An adjacency list is a representation of a graph where all of the vertices that are connected to a node are stored as a list. Below is a graph and a visual representation of its corresponding adjacency list.

An adjacency list can be implemented in JavaScript by creating two classes, a Node class and a Graph class. The Node class will consist of a constructor and a connect() method to join two vertices. It will also have the isConnected() and getAdjacentNodes() methods which work in exactly the same manner as shown above.

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;
  }
}

The Graph class consists of a constructor and the addToGraph() method which adds a new vertex to the graph.

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.

결론

데이터 구조와 알고리즘에 대한 연구를 진행하려면 데이터 구조로서의 그래프와 관련 알고리즘에 대한 확고한 이해가 절대적으로 필요합니다. 이 시리즈의 이전 게시물만큼 초보자에게 친숙하지는 않지만 이 가이드는 데이터 구조와 알고리즘에 대한 이해를 심화하는 데 유용할 것입니다.

The above is the detailed content of Data Structures and Algorithms: Graphs. For more information, please follow other related articles on the PHP Chinese website!