[코딩테스트 Python3(6)] Graph 그래프
그래프 G(V, E)는 어떤 자료나 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 집합 E로 구성된 자료구조 그래프 종류 방향 그래프 vs. 무향 그래프 다중 그래프 vs. 단순 그래프 가중치 그래프 → 다익스트라 인접 리스트(adjacency list) 대칭으로 구성되고, 가운데 대각선은 0으로 표현된다. 위와 같은 방식은 0을 명시해야 하다보니 메모리 낭비가 심하다. 따라서 아래와 같이 표현한다. graph = { 1: [3,5], 2: [4,5], 3: [1,5], 4: [2,5], 5: [1,2,3,4] } 암시적 그래프(Implicit graph) 암시적 그래프라는 용어의 의미는 암시적으로 연결이 모두 되어있다고 간주(연결에 대한 부분은 명시하기 않음)하기..
2023. 7. 7.
