📖Graph

여러 개의 정점과 이를 연결하는 간선으로 이루어진 자료구조

• G = (V, E) : V는 정점의 집합, E는 간선들의 집합

📖용어

• 정점(Vertex) : 그래프를 연결할 객체
• 간선(Edge) : 두 개의 정점을 연결하는 선
• 인접(Adjacent) : 그래프에서 (Vᵢ, Vⱼ)가 있을 때, 두 정점 Vᵢ와 Vⱼ를 인접한다고 함
• 차수(Degree) : 정점에 부속되어 있는 간선의 수
• 진입차수(In-Degree) : 방향 그래프에서 외부에서 들어오는 간선의 수
• 진출차수(Out-Degree) : 방향 그래프에서 외부로 향하는 간선의 수
• 경로(Path : 정점 Vᵢ에서 Vⱼ까지 간선으로 연결된 정점을 순서대로 나열한 리스트
• 단순 경로(Simple Path) : 모두 다른 정점으로 구성된 경로(한붓 그리기)
• 경로 길이(Path Length : 경로를 구성하는 간선의 수
• 사이클(Cycle) : 단순 경로 중에서 경로의 시작 정점과 마지막 정점이 같은 경로 → 사이클이 없는 그래프를 Tree라고 함

📖구현

📎인접 행렬

그래프를 2차원 배열로 구현하는 방식 정점 간에 직접 연결되어 있다면, 2치원 배열의 해당 정점 인덱스에 1(가중치 그래프라면 해당 가중치 값), 아니라면 0을 저장

• 모든 정점에 대해 간선 정보를 입력해야 하므로 인접 행렬을 생성할 때는 O(n²) 의 시간 복잡도를 가짐 → 즉, 모든 간선의 수를 알아내려면 인접 행렬 전체를 탐색해야하므로 역시 O(n²) 의 시간 복잡도를 가짐
• 두 정점에 대한 연결을 조회할 때는 **O(1)**의 시간 복잡도를 가짐
• 항상 2차원 배열이 필요하므로 필요 이상의 공간이 낭비됨
• 인접 리스트에 비해 구현이 쉬움
• 간선이 많이 존재하는 그래프를 구현할 때 적합

📎인접 리스트

그래프를 리스트로 구현하는 방식 정점의 리스트 배열로 관계를 설정해, 정점들 간에 직접 연결이 되어있으면 해당 정점의 인덱스에 리스트 형식으로 그 정점을 삽입

• 모든 간선의 수를 알아내려면 헤더 노드를 포함하여 모든 인접 리스트를 탐색해야하므로 O(n + e) 의 시간 복잡도를 가짐
• 두 정점에 대한 연결을 조회할 때 **O(e)의 시간 복잡도를 가짐
• 필요한 만큼 공간을 사용하기 때문에 공간의 낭비가 적음
• 인접 행렬에 비해 구현이 어려움
• 간선이 적게 존재하는 그래프를 구현할 때 적합

📖종류

• 이 외에도 부분 그래프, 유향 비순환 그래프(DAG), 연결 그래프, 단절 그래프 등이 있음

📎무방향 그래프

두 정점을 연결하는 간선에 방향이 없는 그래프

• 정점 사이의 관계는 양방향
• (Vᵢ, Vⱼ) == (Vⱼ, Vᵢ)

📎방향 그래프

두 정점을 연결하는 간선에 방향이 있는 그래프

• 정점 사이의 관계는 일방향
• (Vᵢ, Vⱼ) != (Vⱼ, Vᵢ)

📎가중치 그래프

두 정점을 연결하는 간선에 가중치가 있는 그래프

📎완전 그래프

모든 정점 사이에 간선이 존재하는 그래프

• 각 정점이 다른 모든 정점과 연결되어 있기 때문에 최대 간선 수를 가짐

그래프의 최대 간선 수

🔖무방향 그래프 : $n(n-1)/2$ 🔖방향 그래프 : $n(n-1)$

📖탐색

📎BFS(Breadth-First Search)

📎DFS(Depth-First Search)