소개글

면접 대비겸 여러 블로그들을 참고하면서 정리해본 CS 지식들을 포스팅하고 있습니다.
만약 틀린 내용이 있다면 피드백은 언제나 환영합니다.
제 나름대로 요약한 내용이기 때문에 자세한 내용은 제일 아래쪽 참고 사이트에서 확인하면 좋을 것 같습니다!
말투는 편한 말투로 작성하니 양해 부탁드립니다.

Graph

정점과 간선의 집합

in-degree - 들어오는 간선
out-degree - 나가는 간선

종류

• Directed Graph (방향 그래프) - 방향성 있는 그래프
• Undirected Graph (무방향 그래프) - 방향성 없는 그래프
• Weighted Graph (가중치 그래프) - 가중치가 존재하는 그래프
• Connected Graph (연결 그래프) - 정점들이 모두 연결되어있는 그래프
• Complete Graph (완전 그래프) - 모든 정점이 서로 연결되어있는 그래프
• Sub Graph - 기존 그래프의 일부 정점 및 간선으로 이루어진 그래프

구현 방법

Adjacent Matrix (인접 행렬)

• O(V^2)의 공간복잡도와 O(1)의 시간복잡도를 가짐

Adjacent List (인접 리스트)

• O(E+V)의 공간복잡도를 가지고 각 정점마다 연결된 간선의 개수만큼의 시간복잡도를 가짐

탐색

DFS, BFS

Minimum Spanning Tree (최소 신장 트리)

Spanning Tree - 모든 정점이 사이클 없이 연결된 형태
Minimum Spanning Tree - 가중치의 합이 최소인 Spanning Tree

참고 사이트

https://hongcoding.tistory.com/78