자료구조 - 그래프

오늘은 많은 자료구조 중 그래프(Graph)에 대해 자세히 알아보도록 하겠습니다.

그래프

그래프는 단순히 노드(Node)와 그 노드를 연결하는 간선(Edge)을 하나로 모아놓은 자료구조이다. 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조

그래프의 주요 용어

• 정점(Vertex, Node) : 데이터의 위치를 나타내는 개념이다.
• 간선(Edge, Branch) : 노드를 연결하는 선이다.
• 인접 정점(Adjacent Vertex) : 간선에 의해 직접 연결된 정점이다.
• 노드의 차수(Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수이다.
• 진입 차수(in-Degree) : 방향 그래프에서 외부에서 오는 간선의 수이다.
• 진출 차수(out-degree) : 방향 그래프에서 외부로 향하는 간선의 수이다.
• 경로의 길이 : 경로를 구성하는데 사용된 간선의 수이다.
• 단순 경로 : 경로 중에서 반복되는 정점이 없는 경우를 의미한다.

그래프의 종류 (Types of Graphs)

• 무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프. A와 B를 연결하는 간선은 양방향으로 이동 가능하다.
• 방향 그래프 (Directed Graph): 간선에 방향이 있는 그래프. A에서 B로 가는 간선은 B에서 A로는 갈 수 없다.
• 가중치 그래프 (Weighted Graph): 간선에 가중치(비용, 거리 등)가 할당된 그래프. 최단 경로 문제 등에 활용된다.
• 부분 그래프 (Subgraph): 원래 그래프의 일부 정점과 간선으로 이루어진 그래프.

그래프 탐색

• 너비 우선 탐색 (BFS: Breadth-First Search): 시작 정점으로부터 가까운 정점부터 차례대로 방문합니다. 큐(Queue) 자료구조를 사용한다. 최단 경로를 찾는 데 유용하다.
• 깊이 우선 탐색 (DFS: Depth-First Search): 시작 정점에서 한 방향으로 최대한 깊숙이 탐색한 후, 더 이상 갈 곳이 없으면 다른 방향으로 탐색합니다. 스택(Stack) 또는 재귀 함수를 사용한다. 경로 존재 여부 확인, 사이클 감지 등에 유용하다.

코드

fun dfs(graph: Graph, startVertex: Int) {
    val visited = BooleanArray(graph.vertices) { false } // 방문 여부 저장
    dfsRecursive(graph, startVertex, visited)
}

private fun dfsRecursive(graph: Graph, vertex: Int, visited: BooleanArray) {
    visited[vertex] = true
    print("$vertex ")

    for (neighbor in graph.adjList[vertex]) {
        if (!visited[neighbor]) {
            dfsRecursive(graph, neighbor, visited)
        }
    }
}

• dfs(graph: Graph, startVertex: Int): 주어진 그래프와 시작 정점에서 깊이 우선 탐색을 시작한다.

• visited: BooleanArray: 각 정점의 방문 여부를 저장하는 배열.

• dfsRecursive(graph: Graph, vertex: Int, visited: BooleanArray): 재귀적으로 DFS를 수행합니다. 현재 정점을 방문하고, 인접한 방문하지 않은 정점들을 재귀적으로 방문힌다.