Summary
•
Graph(그래프) - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.
무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다.
유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
그래프 탐색
•
하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것.
인접 행렬
•
그래프의 연결 관계를 이차원 배열로 나타내는 방식.
ex) 인접 행렬 adj[][]라 한다면,
adj[i][j] : 노드 i에서 노드 j로 가는 간선이 있으면 1, 아니면 0
인접 리스트
•
그래프의 연결 관계를 인덱스 + 배열로 나타내는 방식. 노드 번호가 직접적으로 저장됨.
ex) 인접 리스트 adj[]라 한다면,
adj[1] = {2, 3, 4} : 노드 1에서 갈 수 있는 노드는 2, 3, 4 이다.
(인접 행렬과 인접 리스트의 장단점 적기 ㅎ )