Algorithm & Data Structure/DataStructure

자료구조: 그래프(Graph)

슝슝이입니다 2024. 11. 17. 21:24
반응형

1. 그래프란 무엇인가?

그래프는 정점(Vertex)과 간선(Edge)으로 구성된 데이터 구조입니다. 각 정점은 데이터를 나타내며, 간선은 정점 간의 관계 또는 연결을 나타냅니다. 그래프는 네트워크 구조를 표현하는 데 매우 적합합니다. 예를 들어, 소셜 네트워크, 도로 지도, 인터넷의 링크 구조 등이 있습니다.

그래프의 구성 요소

  • 정점(Vertex):
    • 데이터를 저장하는 노드입니다.
    • 예: 도시, 사람, 웹 페이지 등.
  • 간선(Edge):
    • 정점 간의 관계를 나타냅니다.
    • 방향이 있는 경우 유방향(Directed), 없는 경우 무방향(Undirected)입니다.
  • 가중치(Weight):
    • 간선에 추가 정보(예: 거리, 비용)를 저장하는 값입니다.

2. 그래프의 종류

  1. 무방향 그래프(Undirected Graph):
    • 간선에 방향이 없습니다.
    • 예: Facebook 친구 관계.
      • A와 B가 친구라면, A → B, B → A 모두 가능합니다.
  2. 유방향 그래프(Directed Graph):
    • 간선에 방향이 있습니다.
    • 예: Twitter 팔로우 관계.
      • A가 B를 팔로우한다고 해서, B가 A를 팔로우하는 것은 아닙니다.
  3. 가중치 그래프(Weighted Graph):
    • 간선에 가중치가 포함된 그래프입니다.
    • 예: Google 지도에서 도시 간의 거리.
  4. 비가중치 그래프(Unweighted Graph):
    • 간선에 가중치가 없는 그래프입니다.
  5. 사이클 그래프(Cyclic Graph):
    • 경로가 원형으로 돌아올 수 있는 그래프입니다.
    • 예: 전력망의 순환 구조.
  6. 비사이클 그래프(Acyclic Graph):
    • 경로가 원형으로 돌아오지 않는 그래프입니다.
    • 예: 프로젝트 작업 흐름을 나타내는 DAG(Directed Acyclic Graph).

3. 그래프 표현 방식

그래프는 데이터를 저장하는 방식에 따라 다음 두 가지로 표현할 수 있습니다.

3.1. 인접 리스트(Adjacency List)

  • 정점별로 연결된 정점 목록을 저장합니다.
  • 메모리 효율적이며 대부분의 경우 적합합니다.
  • 시간 복잡도:
    • 특정 간선 존재 확인: O(V)
    • 정점에 연결된 모든 간선 확인: O(E)
  • 장점:
    • 공간 효율적, 간선이 적은 그래프에 적합.
  • 단점:
    • 특정 정점 간의 연결 여부를 확인하기 어려움.

Golang 예제:

graph := map[string][]string{
    "A": {"B", "C"},
    "B": {"A", "D"},
    "C": {"A", "D"},
    "D": {"B", "C"},
}

Java 예제:

Map<String, List<String>> graph = new HashMap<>();
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
graph.put("C", Arrays.asList("A", "D"));
graph.put("D", Arrays.asList("B", "C"));

3.2. 인접 행렬(Adjacency Matrix)

  • NxN 2차원 배열로 연결 여부와 가중치를 저장합니다.
  • 시간 복잡도:
    • 특정 간선 존재 확인: O(1)
    • 정점에 연결된 모든 간선 확인: O(V)
  • 장점:
    • 특정 간선 확인 속도가 빠름.
    • 밀집 그래프(Dense Graph)에 적합.
  • 단점:
    • 공간 비효율적, 희소 그래프(Sparse Graph)에 부적합.

Golang 예제:

graph := [][]int{
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0},
}

Java 예제:

int[][] graph = {
    {0, 1, 1, 0},
    {1, 0, 0, 1},
    {1, 0, 0, 1},
    {0, 1, 1, 0},
};

4. 그래프 탐색

그래프 탐색은 정점과 간선을 따라 이동하며 데이터를 검색하거나 작업을 수행하는 과정입니다. 주요 탐색 방법은 다음과 같습니다.

4.1. 깊이 우선 탐색(DFS)

  • 특정 정점에서 출발하여 한 경로를 끝까지 탐색한 후, 다른 경로를 탐색.
  • 스택(Stack)이나 재귀(Recursion)를 사용.

시간 복잡도: O(V + E)

Golang DFS 예제:

func dfs(graph map[string][]string, start string, visited map[string]bool) {
    visited[start] = true
    fmt.Println(start)

    for _, neighbor := range graph[start] {
        if !visited[neighbor] {
            dfs(graph, neighbor, visited)
        }
    }
}

Java DFS 예제:

public static void dfs(Map<String, List<String>> graph, String start, Set<String> visited) {
    visited.add(start);
    System.out.println(start);

    for (String neighbor : graph.get(start)) {
        if (!visited.contains(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
}

4.2. 너비 우선 탐색(BFS)

  • 특정 정점에서 가까운 정점부터 탐색.
  • 큐(Queue)를 사용.

시간 복잡도: O(V + E)

Golang BFS 예제:

func bfs(graph map[string][]string, start string) {
    queue := []string{start}
    visited := make(map[string]bool)

    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        if visited[current] {
            continue
        }
        visited[current] = true
        fmt.Println(current)

        queue = append(queue, graph[current]...)
    }
}

Java BFS 예제:

public static void bfs(Map<String, List<String>> graph, String start) {
    Queue<String> queue = new LinkedList<>();
    Set<String> visited = new HashSet<>();

    queue.add(start);

    while (!queue.isEmpty()) {
        String current = queue.poll();
        if (visited.contains(current)) {
            continue;
        }
        visited.add(current);
        System.out.println(current);

        queue.addAll(graph.get(current));
    }
}

5. 그래프의 주요 알고리즘

  1. 최단 경로 탐색:
    • Dijkstra, Bellman-Ford, Floyd-Warshall 알고리즘.
    • 예: Google 지도에서 가장 빠른 경로 찾기.
  2. 최소 신장 트리(MST):
    • Kruskal, Prim 알고리즘.
    • 예: 통신 네트워크 구축 비용 최적화.
  3. 강한 연결 요소(SCC):
    • Kosaraju, Tarjan 알고리즘.
    • 예: 소셜 네트워크 내 그룹 찾기.
  4. 위상 정렬(Topological Sort):
    • DAG에서 작업의 순서를 정렬.
    • 예: 프로젝트 일정 관리.

6. 그래프의 응용 사례

  1. 네트워크 라우팅:
    • 최단 경로 탐색을 활용하여 데이터 전송 최적화.
  2. 웹 크롤러:
    • 인터넷의 링크 구조를 분석하여 검색 엔진에 활용.
  3. 소셜 네트워크 분석:
    • 친구 추천 알고리즘, 커뮤니티 탐지.
  4. AI 및 머신러닝:
    • 그래프 뉴럴 네트워크(GNN)를 활용한 데이터 학습.
  5. 추천 시스템:
    • 그래프에서 연결 강도를 분석하여 사용자 맞춤 추천.

 

반응형