graph(map) 구현(python)

■ 그래프

1) 기본 구조

• 노드
  - '정점' 이라고도 함
  
  
• 간선
  - 노드 사이의 도로

■ 예시 그래프

 

■ 그래프 표현법

• 인접 행렬
  2차원 배열에 각 노드가 연결된 형태를 기록하는 방식
  > 이름이 "행렬"이기 때문에 모든 노드에 대응하는 정보를 가짐
  >  모든 노드의 연결 상태를 기록
  > 구현이 간단
  > 간선 값 종류
      ① 0 / 1 로 비연결 / 연결
      ② inf / integer 로 비연결 / 연결(w 가중치)

graph = [
            [0, 7, 5],
            [7, 0, float('inf')],
            [5, float('inf'), 0]
]

노드 V개, 간선 E개의 경우 시간복잡도

① 특정 노드(i, j) 연결 여부

 0 / 1  OR  inf / integer 확인하여 O(1)

 

②특정 노드에 연결된 노드 탐색

한 노드 전체를 iteration하며 연결을 확인해야 하므로 O(V) 의 시간복잡도
→ 노드 V가 간선 E 보다 많으면 손해

 

• 인접 리스트 (set 사용해도 무방)
  연결 리스트 자료구조 활용
  > 실제 연결된 노드/간선만 데이터에 사용
  > 따라서 모든 원소의 개수의 합이 간선의 개수와 동일
      메모리가 절약됨
  ※ 파이썬 list는 연결 리스트 대용 가능
     - 연결리스트 : 삽입 삭제 빠르나 탐색이 O(N)
     -  array : 삽입.삭제 느리나, index 사용 탐색이 빠름 (원래 지정 사이즈 메모리 사용으로 공간낭비 있음)
   참조 : Link 
  
  

 

 

graph = [[] for _ in range(3)]

# 노드 0 연결정보 저장  (노드, 거리)
graph[0].append((1,7))
graph[0].append((2,5))
...

>>> [
       [(1,7), (2,5)],
       ..., [], 
       ...
    ]

노드 V개, 간선 E개의 경우 시간복잡도

① 특정 노드(i, j) 연결 여부

노드에 대응하는 list안의 값은 간선으로 연결된 노드 정보를 담고 있으므로, 최대 O(V)

→ 인접행렬의 O(1)에 비해 많이 걸림

② 특정 노드에 연결된 노드 탐색
가지고 있는 간선의 개수에 비례하여 탐색하므로, 인접행렬에 비해 효율적

 

 

 

 

■ 내 생각

dictionary 2d로 연결 거리까지 표현하면 좋을 것 같다

# 비용 탐색을 위해 연결 상태까지 모드 확인해야할 때
map = {
	
    0 : {
    	1 : 7,
        2 : 5
    },
    1 : {
    	0 : 7,
        2 : float('inf')
    },
    2 : {
    	0 : 5,
        1 : float('inf')
    }
	
}

# 연결 상태 빠르게 확인할 필요 없으면
map = {
	0 : set([(1,7), (2, 5)]),
    1 : set([(0,7)]),
    2 : set([(0,5)])
}

 

 

---

참조 :

나동빈 <이것이 코딩 테스트다>

 

duwjdtn11.tistory.com/515

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