데이터 구조 및 알고리즘: 그래프

소개

그래프는 다수의 꼭짓점(노드)과 그 사이에 있는 모서리(연결)로 이루어진 데이터 구조입니다.

트리는 그래프의 예입니다. 모든 트리는 그래프이지만 모든 그래프가 트리는 아닙니다. 예를 들어 주기가 있는 그래프는 트리가 아닙니다. 트리에는 두 노드 사이에 하나의 루트와 하나의 고유 경로가 있는 반면, 그래프에는 정점 사이에 많은 루트와 여러 경로가 있을 수 있습니다.

기본 용어

정점: 그래프의 노드입니다.

Edge: 두 정점 사이의 연결입니다.

방향: 두 정점 사이의 연결에 방향이 있는 경우. 이는 한 꼭지점에서 다른 꼭지점으로 이동하는 방법이 한 가지뿐임을 의미합니다. 도시(정점)와 도시 사이의 경로(가장자리)를 보여주는 그래프를 예로 들 수 있습니다.

무방향: 그래프의 두 꼭지점 사이의 연결이 양방향으로 가는 경우. 우정으로 연결된 사람(정점)을 보여주는 그래프를 예로 들 수 있습니다.

차수: 정점에 연결된 가장자리의 수입니다. 유향 그래프의 정점은 내각 또는 외차를 가질 수 있습니다. 이는 각각 정점을 향하는 모서리와 정점에서 멀어지는 모서리의 수입니다.

가중치: 간선에 가중치 값이 있는 그래프입니다. 노드 간 거리가 가중치로 표시되는 로드맵을 예로 들 수 있습니다.

순환: 하나 이상의 꼭지점에서 자신에게로 돌아가는 경로가 있는 그래프.

비순환: 주기가 없는 그래프, 즉 어떤 노드도 자신에게 돌아갈 경로가 없습니다. 방향성 비순환 그래프는 데이터 처리 흐름을 표시하는 데 사용할 수 있는 그래프 유형입니다.

밀도: 그래프의 가장자리 수가 최대 가능한 가장자리 수에 가까울 때

희소: 그래프에 가능한 최소 모서리 수에 가까운 경우.

자체 루프: 가장자리에 자신과 연결된 정점이 하나 있는 경우.

다중 간선: 그래프의 두 꼭짓점 사이에 여러 간선이 있는 경우.

단순: 그래프에 자체 루프나 다중 간선이 없는 경우

간단한 유향 그래프에서 최대 간선 수를 얻으려면: n*(n-1) 여기서 n은 노드 수입니다.

간단한 무방향 그래프에서 최대 간선 수를 얻으려면: n*(n-1)/2 여기서 n은 노드 수입니다.

JavaScript로 그래프 구현

그래프를 구현하려면 그래프의 정점과 가장자리를 지정하는 것부터 시작할 수 있습니다. 아래는 다음 그래프에서 이를 수행하는 방법에 대한 예입니다.

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

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

그런 다음 주어진 꼭짓점에 인접한 것을 찾는 함수를 만들 수 있습니다.

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

그리고 두 정점이 연결되어 있는지 확인하는 또 다른 기능:

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

인접 목록

인접 리스트는 노드에 연결된 모든 꼭지점을 리스트로 저장한 그래프를 표현한 것입니다. 아래는 해당 인접 목록의 그래프와 시각적 표현입니다.

인접 목록은 Node 클래스와 Graph 클래스라는 두 개의 클래스를 생성하여 JavaScript로 구현할 수 있습니다. Node 클래스는 생성자와 두 정점을 결합하는 connect() 메서드로 구성됩니다. 또한 위에 표시된 것과 정확히 동일한 방식으로 작동하는 isConnected() 및 getAdjacentNodes() 메서드도 있습니다.

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

그래프 클래스는 생성자와 그래프에 새 정점을 추가하는 addToGraph() 메서드로 구성됩니다.

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.

Kesimpulan

Pemahaman yang kukuh tentang graf sebagai struktur data dan algoritma yang berkaitan dengannya amat diperlukan apabila melanjutkan kajian tentang struktur dan algoritma data. Walaupun tidak mesra pemula seperti siaran sebelumnya dalam siri ini, panduan ini sepatutnya berguna untuk memperdalam pemahaman anda tentang struktur data dan algoritma.

위 내용은 데이터 구조 및 알고리즘: 그래프의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!