그래프(Graph)

그래프(Graph)란

• 그래프는 노드(정점, Vertex)와 간선(Edge)으로 구성된 자료구조입니다. 간선은 두 노드를 연결하며, 방향이 있을 수도 있고 없을 수도 있습니다. 
•  ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 선수 과목 등

 

그래프와 트리의 차이

	그래프	트리
정의	노드(node)와 그 노드를 연결하는 간선(edge)을 하나로 모아 놓은 자료 구조	그래프의 한 종류 DAG(Directed Acycli Graph, 방향성이 있는 비순환 그래프)의 한 종류
방향성	방향 그래프(Directed), 무방향 그래프(Undirected) 모두 존재	방향 그래프(Directed)
사이클	사이클(Cycle) 가능, 자체 간선(self-loop)도 가능, 순환 그래프(Cyclic), 비순환 그래프(Acyclic) 모두 존재	사이클(Cycle) 불가능, 자체 간선(self-loop)도 불가능, 비순환 그래프(Acyclic Graph)
루트 노드	루트 노드의 개념이 없음	한 개의 루트 노드만이 존재, 모든 자식 노드는 한 개의 부모 노드만을 가짐
부모-자식	부모-자식의 개념이 없음	부모-자식 관계 top-bottom 또는 bottom-top으로 이루어짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS안의 Pre-, In-, Post-Order
간선의 수	그래프에 따라 간선의 수가 다름, 간선이 없을 수도 있음	노드가 N인 트리는 항상 N-1의 간선을 가짐
예시 및 종류	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목	이진 트리, 이진 탐색 트리, 균현 트리(AVL 트리, red-black 트리), 이진 힙 (최대힙, 최소힙) 등

 

그래프(Graph)의 주요개념

• 정점(vertex): 위치라는 개념. (node라고도 부름)
• 간선(edge): 위치 간의 관계. 즉, 노드를 연결하는 선(link, branch 라고도 부름)
• 방향성
  
  • 유향 그래프(Directed Graph): 간선에 방향이 있음.
  • 무향 그래프(Undirected Graph): 간선에 방향이 없음.
• 가중치: 간선에 값이 부여된 경우, 각 간선은 가중치를 가짐.

 

그래프의 표현 방법

• 인접 행렬(Adjacency Matrix):
  • 2D 배열을 이용하여 그래프를 표현합니다.
  • 배열의 각 원소는 두 노드가 연결되어 있으면 1, 연결되지 않으면 0으로 표시됩니다.
  • 장점: 간선의 존재 여부를 빠르게 확인할 수 있습니다.
  • 단점: 공간이 많이 필요하며, 간선이 적은 희소 그래프에서는 비효율적입니다.
• 인접 리스트(Adjacency List):
  • 각 노드에 연결된 노드들의 목록을 저장하는 방식입니다.
  • 보통 배열 또는 연결 리스트로 각 노드의 인접 노드를 표현합니다.
  • 장점: 공간 효율적이며, 간선이 적을 경우 매우 유용합니다.
  • 단점: 특정 간선의 존재 여부를 확인하는 데 시간이 더 걸릴 수 있습니다.

 

그래프의 주요연산

 

• 탐색(Traversal): 그래프를 순차적으로 탐색하는 방법
  1. 깊이 우선 탐색(DFS, Depth First Search):
     • 한 노드를 시작으로 가능한 깊게 탐색합니다.
     • 재귀적으로 구현됩니다.
  2. 너비 우선 탐색(BFS, Breadth First Search):
     • 한 노드를 시작으로 인접한 노드를 먼저 탐색하고, 그 다음으로 인접한 노드를 탐색합니다.
     • 큐(Queue)를 사용하여 구현됩니다.
• 최단 경로 탐색:
  • 다익스트라 알고리즘: 가중치가 있는 그래프에서 출발 노드로부터 다른 모든 노드까지의 최단 경로를 찾는 알고리즘입니다.
  • 벨만-포드 알고리즘: 음수 간선 가중치가 있을 경우 사용됩니다.

 

그래프를 이용한 코딩 테스트 예제

1. 최단 경로 (Shortest Path)

문제 설명: 주어진 그래프에서 특정 노드에서 다른 노드까지의 최단 경로를 구하시오. (다익스트라 알고리즘 사용)

function dijkstra(graph, start) {
    const distances = {};
    const visited = new Set();
    for (let node in graph) {
        distances[node] = Infinity;
    }
    distances[start] = 0;
    
    while (visited.size !== Object.keys(graph).length) {
        let currentNode = null;
        let smallestDistance = Infinity;
        
        for (let node in graph) {
            if (!visited.has(node) && distances[node] < smallestDistance) {
                smallestDistance = distances[node];
                currentNode = node;
            }
        }
        
        for (let neighbor in graph[currentNode]) {
            const distance = graph[currentNode][neighbor];
            const newDistance = distances[currentNode] + distance;
            if (newDistance < distances[neighbor]) {
                distances[neighbor] = newDistance;
            }
        }
        
        visited.add(currentNode);
    }
    
    return distances;
}

 

     

 

2. 섬의 개수 (Number of Islands)

문제 설명: 2D 배열에서 "1"은 육지, "0"은 물로 주어집니다. 육지들로 이루어진 섬의 개수를 구하세요. (BFS 또는 DFS 사용)

function numIslands(grid) {
    if (!grid.length) return 0;
    
    let count = 0;
    
    function dfs(i, j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] === '0') return;
        grid[i][j] = '0';  // mark as visited
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
    
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                dfs(i, j);
                count++;
            }
        }
    }
    
    return count;
}

 

 

참고자료

https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html