2022. 12. 6. 22:51ㆍ자료구조
노드와 그 노드를 연결하는 엣지들로 이루어진 비선형 자료구조
<용어 정리>
undirected graph: 두 노드를 연결하는 엣지의 방향이 없는 그래프
directed graph: 두 노드를 연결하는 엣지의 방향이 있는 그래프
complete graph: 모든 노드들 사이에 1:1로 연결된 엣지를 갖는 그래프
subgraph: 원래의 그래프에서 일부의 노드나 엣지를 제외하여 만든 그래프
weigth graph: 노드를 연결하는 엣지에 가중치를 할당한 그래프
loop: 엣지가 자기 자신에게 연결되어 있을 때
Path: 출발 노드에서 시작에서 도착 노드에 도착할 때까지의 경로
경로의 길이: 엣지의 가중치가 없는 그래프의 경우- 지나온 엣지의 수
있는 그래프의 경우- 지나온 엣지들의 가중치의 합
simple path: 모두 다른 엣지로 구성된 경로
Multiple Edges: 두 노드 사이 엣지가 둘 또는 그 이상 있는 경우
Simple Graph: 루프도 없고 멀티플 엣지도 없는 그래프
cycle: 경로 중 시작 노드와 마지막 노드가 같은 경로
Adjacency Matrix: 그래프의 노드 간의 연결 관계를 2차원 배열로 표현하는 방법
n개의 노드를 가진 그래프는 n*n 행렬로 표현됨
두 노드가 연결되어 있으면 true 아니면 false로 표현
가중 그래프의 경우엔 참거짓 대신 가중치 값으로 표현
장점: 구현이 쉽고, 특정 노드 사이의 인접 여부 확인이 빠름
단점: 모든 엣지들을 표현해야 하므로 메모리 낭비가 심하다
Adjacency List: 연결 관계를 연결 리스트를 이용하여 표현하는 방법
특정 노드와 연결된 노드를 연결 리스트에 저장(향하고 있는 노드들을 다 저장)
장점: 인접한 노드들만 저장하므로 메모리 효율적 사용
단점: 특정 노드들이 연결되어 있는지 확인해야 할 때, 연결 리스트를 순차적으로 다 확인해야 함.