자료구조와 알고리즘, graph, dfs, bfs

 

 

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조로, 정점 간의 관계를 나타내는 데 사용됩니다. 그래프는 다양한 형태로 존재하며, 여러 가지 문제를 해결하는 데 유용합니다.

그래프의 기본 용어

1. 정점(Vertex): 그래프의 노드를 의미합니다. 정점은 데이터를 저장할 수 있습니다.
2. 간선(Edge): 정점 간의 연결을 나타냅니다. 간선은 방향이 있을 수도(유향 그래프) 없을 수도(무향 그래프) 있습니다.
3. 인접 정점(Adjacent Vertex): 간선으로 직접 연결된 정점들입니다.
4. 경로(Path): 한 정점에서 시작하여 다른 정점으로 가는 일련의 간선들입니다.
5. 가중치(Weight): 간선에 부여된 값으로, 두 정점 간의 비용이나 거리를 나타냅니다. 가중치가 있는 그래프를 가중치 그래프(Weighted Graph)라고 합니다.

그래프의 종류

1. 무향 그래프(Undirected Graph): 간선에 방향이 없는 그래프입니다.
2. 유향 그래프(Directed Graph): 간선에 방향이 있는 그래프입니다.
3. 가중치 그래프(Weighted Graph): 간선에 가중치가 있는 그래프입니다.
4. 비가중치 그래프(Unweighted Graph): 간선에 가중치가 없는 그래프입니다.

그래프의 표현 방법

1. 인접 행렬(Adjacency Matrix): 정점을 행과 열로 표현하고, 정점 간의 연결을 행렬의 값으로 나타냅니다. 연결되어 있으면 1, 연결되어 있지 않으면 0으로 표시합니다. 가중치가 있는 그래프에서는 가중치를 행렬의 값으로 표시합니다.
2. 인접 리스트(Adjacency List): 각 정점에 대해 인접한 정점들의 리스트를 저장합니다. 인접 리스트는 공간 효율성이 좋고, 그래프의 정점과 간선이 많을 때 유리합니다.

1. 인접 행렬(Adjacency Matrix)

출처 [https://cs.slides.com/colt_steele/graphs#/59/0/3]

 

개념

인접 행렬은 정점을 행과 열로 표시하고, 두 정점 사이에 간선이 존재하면 해당 행렬 위치에 1(또는 가중치 값)을, 존재하지 않으면 0을 기록합니다.

시간 복잡도

• 공간 복잡도: (O(V^2)) - (V)는 정점의 수
• 간선 추가: (O(1))
• 간선 삭제: (O(1))
• 간선 존재 여부 확인: (O(1))
• 정점의 모든 인접 정점 탐색: (O(V))

장점

1. 간선 존재 여부 확인이 빠름: 특정 두 정점 사이의 간선 존재 여부를 (O(1)) 시간에 확인할 수 있습니다.
2. 간선 추가/삭제가 빠름: (O(1)) 시간에 간선을 추가하거나 삭제할 수 있습니다.

단점

1. 공간 비효율성: 정점의 수가 많고 간선의 수가 적은 경우(희소 그래프) 많은 공간이 낭비됩니다.
2. 정점의 인접 정점 탐색이 느림: 특정 정점의 모든 인접 정점을 찾으려면 행렬의 해당 행 전체를 확인해야 하므로 \(O(V)\) 시간이 걸립니다.

2. 인접 리스트(Adjacency List)

출처 [https://cs.slides.com/colt_steele/graphs#/59/0/3]

출처 [https://cs.slides.com/colt_steele/graphs#/59/0/3]

개념

인접 리스트는 각 정점에 대해 연결된 인접 정점의 리스트를 저장합니다. 배열이나 링크드 리스트를 사용해 구현할 수 있습니다.

시간 복잡도

• 공간 복잡도: (O(V + E)) - (E)는 간선의 수
• 간선 추가: (O(1))
• 간선 삭제: (O(E / V)) 평균적으로, 최악의 경우 (O(V))
• 간선 존재 여부 확인: (O(E / V)) 평균적으로, 최악의 경우 (O(V))
• 정점의 모든 인접 정점 탐색: (O(V)) 최악의 경우, 하지만 평균적으로 인접한 정점의 수에 비례

장점

1. 공간 효율성: 희소 그래프의 경우 공간을 절약할 수 있습니다.
2. 정점의 인접 정점 탐색이 빠름: 특정 정점의 모든 인접 정점을 빠르게 탐색할 수 있습니다. 평균적으로 인접한 정점의 수에 비례한 시간에 탐색이 가능합니다.

단점

1. 간선 존재 여부 확인이 느림: 특정 두 정점 사이의 간선 존재 여부를 확인하려면 인접 리스트를 순회해야 하므로 최악의 경우 (O(V)) 시간이 걸립니다.
2. 간선 삭제가 느림: 간선을 삭제하려면 인접 리스트에서 해당 간선을 찾아야 하므로 시간이 더 걸릴 수 있습니다.

선택 기준

1. 그래프의 밀도: 그래프가 밀집되어 있고 간선의 수가 정점의 수의 제곱에 비례한다면 인접 행렬이 적합합니다. 반대로, 희소 그래프에서는 인접 리스트가 공간 효율성이 높습니다.
2. 간선 존재 여부 확인: 두 정점 사이의 간선 존재 여부를 빈번하게 확인해야 한다면 인접 행렬이 더 효율적입니다.
3. 정점의 인접 정점 탐색: 특정 정점의 모든 인접 정점을 자주 탐색해야 한다면 인접 리스트가 더 효율적입니다.

이러한 비교와 장단점을 고려하여, 그래프의 특성과 요구사항에 따라 적합한 표현 방법을 선택하는 것이 중요합니다.

시간 복잡도

출처 [https://cs.slides.com/colt_steele/graphs#/59/0/3]

인접 리스트를 사용한 구현

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

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

  addEdge(vertex1, vertex2) {
    if (!this.adjacencyList[vertex1]) this.addVertex(vertex1);
    if (!this.adjacencyList[vertex2]) this.addVertex(vertex2);

    this.adjacencyList[vertex1].push(vertex2);
    this.adjacencyList[vertex2].push(vertex1);
  }

  removeEdge(vertex1, vertex2) {
    this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
      (v) => v !== vertex2
    );
    this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
      (v) => v !== vertex1
    );
  }

  removeVertex(vertex) {
    for (let key in this.adjacencyList) {
      if (this.adjacencyList[key].includes(vertex)) {
        this.adjacencyList[key] = this.adjacencyList[key].filter(
          (v) => v !== vertex
        );
      }
    }

    delete this.adjacencyList[vertex];

    console.log('after this.adjacencyList[key]:', this.adjacencyList);
  }
}

let basicGraph = new Graph();

basicGraph.addVertex('A');
basicGraph.addVertex('B');

basicGraph.addEdge('A', 'B');
basicGraph.addEdge('A', 'C');
basicGraph.addEdge('A', 'D');
basicGraph.addEdge('B', 'C');

basicGraph.removeVertex('A');

console.log(basicGraph);

그래프 탐색 알고리즘

1. 너비 우선 탐색(BFS, Breadth-First Search): 시작 정점에서 가까운 정점부터 탐색하는 알고리즘입니다. 주로 큐(Queue)를 사용하여 구현합니다.
2. 깊이 우선 탐색(DFS, Depth-First Search): 시작 정점에서 한 방향으로 깊이 탐색하다가 더 이상 갈 수 없으면 다른 경로로 탐색하는 알고리즘입니다. 주로 스택(Stack)을 사용하여 구현하거나 재귀 호출로 구현합니다.

너비 우선 탐색(BFS) 구현

 bfs(vertex) {
    // This function should accept a starting vertex
    // Create a queue (you can use an array) and place the starting vertex in it
    // Create an array to store the node visited
    // Create an object to store nodes visited
    // Mark the starting vertex as visited
    // Loop as long as there is anything in the queue
    // Remove the first vertex from the queue and push it into the array stores nodes visited
    // Loop over each vertex in the adjacency list for the vertex you are visiting
    // If it is not inside the object that stores nodes visited, mark it as visited and enqueue that vertex

    let queue = [];
    let results = [];
    let visited = {};
    let targetVertex;

    queue.push(vertex);
    visited[vertex] = true;

    while (queue.length) {
      console.log('queue:', queue);
      targetVertex = queue.shift();
      results.push(targetVertex);

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

    return results;
  }

깊이 우선 탐색(DFS) 구현 - 재귀

  dfRecursive(startVertex) {
    // The function should accept a starting node
    // Create a 'results' variable to store the end result, to be returned at the very end
    // Create an object 'visitied' to store visited vertices
    // Create a helper function which accepts a vertex
    // The helper function should return early if the vertex is empty
    // The helper function should place the vertex it accepts into the visited object and push that vertex into the result array
    // Loop over all of the values in the adjacencyList for that vertex
    // If any of those values have not been visited, recursively invoke the helper function with that vertext
    let results = [];
    let visited = {};
    let adjacencyList = this.adjacencyList;
    /**
     * { A : true, B: true, ... }
     */

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

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

    helper(startVertex);

    return results;
  }
  
  /**
const list = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B', 'E', 'F'],
  E: ['C', 'D', 'F'],
  F: ['D', 'E'],
};
 */

/**
 * basicGraph.dfRecursive('A')
 *
 * [ 'A', 'B', 'D', 'E', 'C', 'F' ]
 */

깊이 우선 탐색(DFS) 구현 - 순환

dfIterative(vertex) {
    // The function should accept a starting node
    // Create a stack to help use keep track of vertices (use a list/ array)
    // Create a list to store the end result, to be returned at the very end
    // Create an object to store visited vertices
    // Add the starting vertex to the stack, and mark it visited
    // While the stack has something in it:
    // Pop the next vertext from the stack
    // If that vertext hasn't been visited yet:
    // Mark it as visited
    // Add it to the result list
    // Push all of its neighbors into the stack

    let stack = [];
    let results = [];
    let visited = {};
    let targetVertex;

    stack.push(vertex);
    visited[vertex] = true;

    while (stack.length) {
      console.log('stack:', stack);
      targetVertex = stack.pop();
      results.push(targetVertex);

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

    return results;
  }
  
  /**
const list = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'E'],
  D: ['B', 'E', 'F'],
  E: ['C', 'D', 'F'],
  F: ['D', 'E'],
};
 */

/**
 *basicGraph.dfIterative('A')
 *
 *  stack: [ 'A' ]
 *  stack: [ 'B', 'C' ]
 *  stack: [ 'B', 'E' ]
 *  stack: [ 'B', 'D', 'F' ]
 *  stack: [ 'B', 'D' ]
 *  stack: [ 'B' ]
 *
 *  [ 'A', 'C', 'E', 'F', 'D', 'B' ]
 */

그래프의 응용

1. 네트워크: 컴퓨터 네트워크, 소셜 네트워크 등에서 노드 간의 연결을 나타내기 위해 사용됩니다.
2. 경로 찾기: 지도나 길 찾기 애플리케이션에서 최단 경로를 찾기 위해 사용됩니다.
3. 일정 관리: 프로젝트 관리에서 작업 간의 의존성을 나타내기 위해 사용됩니다.
4. 순위 계산: 페이지 랭크 알고리즘과 같은 검색 엔진에서 페이지의 중요도를 계산하기 위해 사용됩니다.

그래프는 데이터 간의 관계를 나타내는 데 매우 유용한 자료 구조로, 다양한 분야에서 중요한 역할을 합니다.