그래프 데이터에 대한 고찰

파이썬에서 그래프를 표현하는 방법

라이브러리는 사용하지 않음

방법

• 인접행룔
• 인접리스트
• 인정다중리스트
• 결합행렬
• 딕셔너리

아래는 대표적으로 그래프를 표현하는 방법(인접행렬, 인접리스트, 결합행렬)

아래에 의하면 인접리스트가 가장 선호하는 방법임

Graph (abstract data type) - Wikipedia

아래는 인접행렬과 인접리스트 인접다중리스트를 소개하는 글로 인접다중리스트는 리스트를 공유하는 형태이다.

6-2. 그래프의 표현(인접 행렬, 인접 리스트, 인접 다중 리스트)

아래는 파이썬 공식 문서와 외부문서로 딕셔너리를 이용해 생성함.

Python Patterns - Implementing Graphs

Generate a graph using Dictionary in Python - GeeksforGeeks

아래는 numpy와dictionary를 비교하는 글임.

특정 key를 필요로한다면 dict가 맞음

Dictionary or Numpy Array?

아래 글은 선택하는 순서이다.

When to use pandas series, numpy ndarrays or simply python dictionaries?

윗 글에 의하면 딕셔너리보다는 넘파이고 (고차원이며 행렬의 연결 값에 따라 수학적 계산_평균같은_을 할 것이기때문에)

시리즈까지는 가지 않아도됨(merge or export 필요없음)

 

 

그.러.나.

로그 순서를 살펴봐야하므로 인접리스트를 써야하는게 맞다. 단순 행렬을 이용하면 흐름을 관찰할 순 없음.

인접리스트의 단점이 i부터 j의 연결도를 알려면 그 연결을 쭉 가야한다는 것인데 이를 역으로 생각하면 i부터 j까지의 흐름을 알 수 있다는 것 아닌가?

 

만일 노드 i와 노드 j의 연결 여부를 알고 싶을 경우에는 어떻게 해야 할까?

adj[i] 의 리스트를 순회하며 j 원소가 존재하는지 확인해야 한다. 이러한 경우 O(V)의 시간 복잡도를 갖게 된다. 인접 행렬은 adj[i][j]가 1인지 0인지만 확인하면 i와 v 노드의 연결 여부를 O(1) 시간복잡도를 통해 확인이 가능했었다.

[Python] 인접 행렬과 인접 리스트

 

이해를 잘못했다. 흐름은 알 수 없다 단지 연결의 유무만 알 수 있음..! 그냥 인접 리스트를 이용해서 흐름을 알아내는게 나을 것 같음 그게 더 편하고

 

아래는 구현 방법

Representing a Graph

그리고 위에 파이썬 문서에 path찾는 코드도 구현되어있다.