연결 리스트 그래프1 그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프를 구현해보도록 하겠습니다. 1. 인접 리스트 인접 리스트 방식은 한 정점에 대해서 인접한 리스트를 연결 리스트로 연결한 것입니다. 다음과 같은 그래프를 인접 리스트로 표현해보면 다음과 같습니다. 그림을 보고나면 대충 감이 잡히실겁니다. 각 정점에 대해서 노드는 간선의 갯수만큼 연결되어있습니다. 맨 처음의 A, B, C, D 노드를 헤드 포인터라고 하며, 이 헤드 포인터는 그래프의 정점의 갯수만큼을 필요로합니다. 즉, 무방향 그래프의 노드의 수 만큼의 연결 리스트가 만들어지고 각 연결 리스트는 정점이 가진 간선의 갯수(차수, degree)만큼의 길이를 가지게 됩니다. 만약 방향 그.. 2021. 10. 5. 이전 1 다음 300x250
