[자료구조] 그래프

그래프

정점(Vertex, Node) : 데이터를 나타내는 값

간선(Edge) : 정점과 정점을 연결해주는 선 및 사이 관계

차수(Defree) : 하나의 정점에서 연결되어있는 간선의 갯수

 

그래프와 트리의 차이는 방향성의 차이이다.

그래프는 양방향과 단방향 그래프가 존재하지만 트리는 부모에서 노드로의 단방향만 존재한다.

---

 

 

 

다음과 같은 그래프를 인접행렬로 나타내는 방법

 

무방향 그래프 

# 1. 넓이 5*5 , 7개의 입력값이 주어진다고 했을때

graph = [[0]*5 for _ in range(5)]

for _ in range(7):
    x, y = map(int,input().split())

    graph[x-1][y-1] +=1  # 입력값을 1~5로 받았을때 index error 처리
    graph[y-1][x-1] +=1  # 방향이 없기 때문에 대칭으로 값 추가

print(graph)


###
[[0, 0, 1, 1, 0],
[0, 0, 1, 1, 1],
[1, 1, 0, 0, 1],
[1, 1, 0, 0, 1],
[0, 1, 1, 1, 0]]
###

---

방향 그래프

# 1. 넓이 5*5 , 7개의 입력값이 주어진다고 했을때

graph = [[0]*5 for _ in range(5)]

for _ in range(7):
    x, y = map(int,input().split())

    graph[x-1][y-1] +=1    # 입력값을 1~5로 받았을때 index error 처리

print(graph)

###
[[0, 0, 0, 0, 0],
[0, 0, 1, 1, 0],
[1, 0, 0, 0, 1],
[1, 0, 0, 0, 0],
[0, 1, 0, 1, 0]]
###

---

인접 리스트를 그래프로 나타내는 방법

 

인접 행렬에 비해 정점이 많고 간선이 상대적으로 적은 상황에서 사용 시 공간을 절약할 수 있다.

 

무방향 그래프

V, E = 5, 7

graph = [[] for _ in range(V+1)]

for _ in range(E):
    x, y = map(int,input().split())

    graph[x].append(y)
    graph[y].append(x)

print(graph)

###
[[], [3, 4], [3, 5, 4], [1, 2, 5], [1, 5, 2], [2, 4, 3]]
###

---

방향 그래프

V, E = 5, 7

graph = [[] for _ in range(V+1)]

for _ in range(E):
    x, y = map(int,input().split())

    graph[x].append(y)

print(graph)

###
[[], [], [3, 4], [1, 5], [1], [2, 4]]
###

 

---

인접 행렬 과 인접 리스트 비교

 

 

 

---

---

참고 

https://www.yes24.com/Product/Goods/91084402

파이썬 알고리즘 인터뷰 - YES24

 

바킹독 유튜브