[정글 WEEK03_알고리즘] 개발 일지 - 그래프 개요

정의

정점(Vertex)과 정점 사이에 연결된 간선(Edge) 정보를 가지고 있는 자료구조

 

구현 방식

- 인접 행렬: 그래프의 정점을 행과 열로 나타내고, 각 칸에 간선의 존재 여부(또는 가중치)를 저장하는 2차원 배열 구현 방식

- 인접 리스트: 각 정점(vertex)에 대해 해당 정점과 연결된 이웃 정점들의 목록을 리스트 안에 저장, 가중치가 있다면 (정점, 가중치) 튜플 형태로도 저장 가능

출처: https://velog.io/@orangehour/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-%EC%9D%B8%EC%A0%91-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EC%9D%B8%EC%A0%91-%ED%96%89%EB%A0%AC

	인접 행렬	인접 리스트
형태	N x N 2차원 배열 예: matrix[D][C] = 1 → D정점과 C정점이 연결 (0: 비연결, 1: 연결)	리스트 안에 연결된 정점 목록 예: graph[C] = [B, D] → C정점이 B, D 정점과 연결
간선 정보 저장 시 공간 복잡도	나쁨 (O(V^2)) 간선과 무관하게 V x V크기의 2차원 배열 필요	좋음 (O(V+E)) 정점 V개 + 간선 E개 만큼의 연결 정보 저장 필요
정점 간 연결 여부 확인 시  시간 복잡도	빠름 (O(1)) 인덱스로 상수시간에 접근	느림 (O(V)) 특정 정점의 인접리스트 안에서 특정 정점 탐색
모든 인접 정점 탐색 시간복잡도	느림 (O(V)) 모든 정점 개수만큼 확인	빠름 (O(d(V))) 특정 노드와 실제로 연결된 인접 노드만 확인
간선 추가/삭제 시간복잡도	O(1) 배열 접근	추가 시: O(1) 리스트에 추가 삭제 시: O(d(V)) 리스트에서 값을 찾아서 삭제
use case	정점 수가 작고 밀도가 높은 그래프 연결 여부를 빠르게 자주 확인해야 하는 상황	간선이 적은 희소 그래프 그래프가 매우 크고 메모리 제한이 있는 상황

* V: 그래프 전체 정점 개수, d(V): 특정 정점의 차수(특정 정점과 연결된 간선 수), E: 그래프 전체 간선 개수

 

📁 방향성 기준 분류

 - 무방향 그래프(Undirected Graph)

   : 간선에 방향이 없음

      BFS, DFS, MST (Prim, Kruskal), Union-Find 등에 사용

 - 방향 그래프(Directed Graph)

   : 간선에 방향이 있음

      위상정렬, SCC, 다익스트라, 벨만-포드, 플로우 네트워크 등에 사용 

 

 - 비순환 방향 그래프(DAG, Directed Acyclic Graph)

    : 간선에 방향은 있지만 사이클이 없어서 정점에서 출발해 자기 자신으로 돌아오는 경로가 없는 그래프

      위상 정렬, DP on DAG, 작업 스케쥴링 등에 사용

 

📁 가중치 여부 기준 분류

 - 가중치 그래프(Weighted Graph)

    : 간선마다 비용/가중치가 있음

       다익스트라, 벨만-포드, MST등에 사용

 - 비가중치 그래프(Unweighted Graph)

    : 간선에 비용 없음

      BFS (최단거리 탐색)

📁 연결 구조 기준 분류

 - 연결 그래프(Connected Graph)

    : 모든 정점이 연결됨

      MST, 트리 관련 알고리즘 등에 사용

 - 비연결 그래프(Disconnected Graph)

    : 일부 정점이 연결되지 않음 

      컴포넌트 탐색 (DFS, Union-Find) 등에 사용

 - 비순환 방향 연결 그래프(Connected DAG, Tree)

    = 트리 (n개의 정점, n-1개의 간선) 🖱️자세한 내용 링크

     순환구조가 없는 연결 그래프가 n개의 정점과 n-1개의 간선을 가지면 트리라고 할 수 있음

 - 루트 없는 트리(Unrooted Tree)

    : 트리지만 루트가 지정되지 않음

      누가 루트인지 정의되지 않았을 뿐, 아무 노드나 루트로 정할 수 있음 

 

🔗 네트워크 그래프

 - 플로우 네트워크(Flow Network)

    : 간선에 용량이 있고 흐름을 가짐 

      최대 유량(에드몬드-카프, Dinic), 최소컷에 사용

 - 잔여 그래프(Residual Graph)

   : 플로우 네트워크의 남은 용량을 표현

     최대 유량 알고리즘 내부 구조에 사용

 

---

📌 알고리즘별로 사용하는 그래프

BFS / DFS : 무방향 or 방향 그래프, 비가중치 그래프

다익스트라: 가중치 그래프(양수)

벨만-포드: 가중치 그래프(음수 허용)

위상 정렬: DAG

MST(Kruskal, Prim): 무방향 가중치 그래프

SCC, 강한 연결 요소: 방향 그래프

최대 유량: 플로우 네트워크

이분 매칭: 이분 그래프

트리 DP, LCA: 트리, 루트 없는 트리