////////
Search
Duplicate

Graph

Created
2021/03/20 18:22
Tags

Summary

Graph(그래프) - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.
무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다.
유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.

그래프 탐색

하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.

인접 행렬

그래프의 연결 관계를 이차원 배열로 나타내는 방식.
ex) 인접 행렬 adj[][]라 한다면,
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0

인접 리스트

그래프의 연결 관계를 인덱스 + 배열로 나타내는 방식. 노드 번호가 직접적으로 저장됨.
ex) 인접 리스트 adj[]라 한다면,
adj[1] = {2, 3, 4} : 노드 1에서 갈 수 있는 노드는 2, 3, 4 이다.
(인접 행렬과 인접 리스트의 장단점 적기 ㅎ )