원글 페이지 : 바로가기
그래프 그래프는 원소를 정점과 간선으로 표현한 것이다. 두 정점이 간선으로 연결되어 있으면 인접하다고 한다. 그래프는 크게 2가지로 표현할 수 있다. 1. 인접 행렬(Adjacency Matrix) 인접 행렬이란, 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식이다. adg[i][j] = 1 (노드 i에서 노드 j로 가는 간선이 존재할 경우) adg[i][j] = 0 (노드 i에서 노드 j로 가는 간선이 존재하지 않을 경우) 1. 무향그래프 만약 표현하고자 하는 그래프가 방향이 없는 무향 그래프일 경우, 노드 i에서 노드 j로 가는 길이 존재하면, 노드 j에서 노드 i로 가는 길 또한 존재한다. 이러한 특성으로 인해 인접 행렬을 구현하게 되면, 대각 성분을 기준으로 대칭인 성질을 가지게 된다. 가중치가 없는 무향 그래프 가중치가 있는 무향 그래프 2. 유향 그래프 만약 표현하고자 하는 그래프에 방향성이 존재한다면, 대각선을 기준으로 한 대칭성은 사라진다. 가중치가 있는 유향 그래프 🟩인접 행렬의 장점 구현이 쉽다 노드 i와 노드 j가 연결되어 있는지 확인하고 싶을 때, indexing으로 접근하기 떄문에 O(1)의 시간복잡도를 가진다 🟧인접 행렬의 단점 전체 노드의 개수를 v개, 간선의 개수를 E개라고 하면, 노드 i에 연결된 모든 노드들에 방문하고 싶은 경우 adj[i][1]부터 adj[i][V]를 모두 확인해봐야 하기 때문에 총 O(V)의 시간이 걸린다. 노드의 수에 비해 간선의 개수가 훨씬 적은 그래프면 적절하지 않다. 2. 인접 리스트 인접 리스트란, 각각의 노드에 인접한 노드들을 원소로 가지는 리스트이다. i번째 리스트는 정점 i에 인접한 정점들을 리스트로 연결해 놓는다. 가중치가 있는 그래프의 경우, 리스트는 가중치도 보관한다. Python에서는 하나의 노드가 키(key)가 되고, 그 노드에 인접한 노드가 값(value)이 되는 딕셔너리로 구현할 수 있다. 인접 리스트는 인접 행렬이 갖는 단점을 극복할 수 있다. 무향 그래프 예시 가중치가 있는 그래프의 예시 🟩인접 리스트의 장점 실제 연결된 노드에 대한 정보만 저장하기 때문에, 모든 원소의 개수의 합이 간선의 개수와 동일하다. 즉, 간선의 개수에 비례하는 메모리만 차지하여 구현이 가능하다. 각 노드에 연결된 모든 노드들을 방문해 보아야 하는 경우, 인접 리스트로 연결 관계를 저장하는 것이 시간상 큰 이점을 가진다. 🟧인접 리스트의 단점 노드 i와 j의 연결 여부를 알고 싶을 때, adj[i] 리스트를 순회하며 j 원소가 존재하는지 확인해야 한다 → 시간 복잡도 O(V) 인접 행렬은 adj[i][j]가 1인지 0인지만 확인하면 i와 v 노드의 연결 여부를 O(1)로 확인 가능하다. Reference https://velog.io/@eunchae2000/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EA%B7%B8%EB%9E%98%ED%94%84%EB%A5%BC-%EC%A0%80%EC%9E%A5%ED%95%98%EB%8A%94-%EB%B0%A9%EB%B2%95-3%EA%B0%80%EC%A7%80-%EC%9D%B8%EC%A0%91-%ED%96%89%EB%A0%AC-%EC%9D%B8%EC%A0%91-%EB%A6%AC%EC%8A%A4%ED%8A%B8-%EA%B0%84%EC%84%A0-%EB%A6%AC%EC%8A%A4%ED%8A%B8-with-Python [자료구조] 그래프를 저장하는 방법 3가지 : 인접 행렬, 인접 리스트, 간선 리스트 with Python 그래프는 연결되어 있는 원소간의 관계를 표현한 자료구조이다.그래프는 노드(N, node)와 그 노드를 연결하는 간선(E, edge)의 집합으로 구성된다.즉, 연결되어 있는 객체 간의 관계를 표현할 수 있 velog.io