그래프와 행렬

용어 정리

 

정점 : Node, Vertex

간선 : Edge

G = (V,E)

---

1. 인접행렬

• 정점의 개수를 V라고 했을 때 V*V 크기의 이차원 배열을 이용
• A[i][j] = w (i->j의 간선이 있을때, 그 가중치), 0(없을때)
• 알고리즘 테스트에서 거의 사용되지 않는데, 비효율적이어서 그렇다. 예를들어 간선이 정점이 10만개이고 간선이 100만개 이면 행렬은 100억개의 공간을 가지게 되는데, 쓰지 않을 공간까지 자리를 할당해주니 비효율적일 수 밖에 없다.
• 정 사용할거면 연결이 되어 있느냐 없느냐 정도만 활용하기 위해 bool문으로 선언할 것을 권장한다.

---

2. 인접 리스트

• 리스트를 이용해서 구현
• A[i] = i와 연결된 정점을 리스트로 포함하고 있음
• 효율성 : O(V의 차수). 정점 V에 연결된 정점들 갯수만큼 탐색해서 원하는 요소를 찾기 때문이다.
• 시간 복잡도 : O(E)

가중치까지 포함해서 저장하면 이렇게 된다.

 

 

---

3. 간선 리스트

 

• 위 표와 같이 간선과 간선을 저장하고 간선의 가중치들을 따로 저장한다.
• i번 정점과 연결된 간선은 배열에서 cnt[i-1]부터 cnt[i]-1까지이다.
  ex) 3번 정점 : cnt[2] ~ cnt[3]-1

 

+ 모든 이미지 자료는 백준 알고리즘 강의에서 발췌했으며, 무단 배포 및 무단 사용 X