[Graph] 그래프 표현법(인접행렬 & 인접리스트)

인접행렬

Graph: 정점과 정점을 연결하는 간선의 집합(정점과 간선의 집합)

 

a와 b가 연결되어 있을 때 아래와 같이 표시

graph[a][b]=1

graph[b][a]=1

 

정점의 개수가 n개면 n*n 배열을 선언해야 함

노드는 100개 밖에 안되는데 100*100 = 10,000을 접근해야 함

인접 행렬은 정점의 개수가 많아질수록 저장 공간이 낭비가 됨

인접 리스트

인접 행렬이 너무 많은 저장 공간을 낭비하기 때문에 인접 리스트 방식을 생각함 > 시간 복잡도, 공간 복잡도가 확 줄어듬

---

인접 리스트 구현

graph = [[] for _ in range(6)] # [] [] [] [] [] []

for a, b in edges:
	graph[a].append(b)
    graph[b].append(a)

 

3번 정점과 연결된 것을 찾기 위해서 아래와 같이 for문을 돌리면 됨 > 시간복잡도와 공간복잡도가 굉장히 줄어듬

for v in graph[3]:

   print(v)