그래프(무방향, 유방향) 예문

무방향 그래프

'''
input = 
6 5
1 2
2 5
5 1
3 4
4 6


n = 정점 개수
m = 간선 개수
'''
import pprint

n, m = map(int, input().split())
adjacent = []

graph = [[0] * (n+1) for _ in range(n+1)]
graph_list =  [[] for _ in range(n+1)]

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1][v2] = 1
    graph[v2][v1] = 1
    graph_list[v1].append(v2)
    graph_list[v2].append(v1)

pprint.pprint(graph)
print(graph_list)

행렬의 개념으로 그래프를 생성해주도록 한다. 

즉, 리스트 안의 리스트 형식으로 그래프를 만들어준다. 

 

 

graph = [[0] * (n + 1) for _ in range(n + 1)]

이 구문은 행렬의 형태로 그래프를 생성하고 (인접 행렬, 간선이 없으면 0, 있으면 1)

graph_list =  [[] for _ in range(n+1)]

이 구문은 리스트 형태로 인접한 노드를 나타낸다. (인접 리스트, 인접 노드들을 순차적으로 표현)

 

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1][v2] = 1
    graph[v2][v1] = 1

인접 행렬의 노드 값들을 입력받을 때 좌표 형태로 입력받아 해당되는 위치에 1을 넣어준다. 

 

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph_list[v1].append(v2)
    graph_list[v2].append(v1)

인접 리스트의 노드 값들을 입력받을 때 리스트에 값을 넣어주는 방식으로 입력값을 받는다. 

입력받은 v1, v2의 값은 서로 인접한 노드임으로 인덱스 v1의 위치에 v2 값을 넣어주고, 또 반대로 인덱스 v2의 위치에 v1 값을 넣어준다. 

 

# 인접 행렬
output = [
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 1, 0],
 [0, 1, 0, 0, 0, 1, 0],
 [0, 0, 0, 0, 1, 0, 0],
 [0, 0, 0, 1, 0, 0, 1],
 [0, 1, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 1, 0, 0]]
 
# 인접 리스트
[[], [2, 5], [1, 5], [4], [3, 6], [2, 1], [4]]

위 구문을 통해 이러한 출력값을 얻는다.

 

유방향 그래프

'''
input =
6 5
1 2
2 5
5 1
3 4
4 6

'''

import pprint

n, m = map(int, input().split())
adjacent = []

graph = [[0] * (n+1) for _ in range(n+1)]
graph_list =  [[] for _ in range(n+1)]

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1][v2] = 1
    
    graph_list[v1].append(v2)
    

pprint.pprint(graph)
print(graph_list)

 

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph[v1][v2] = 1

for _ in range(m):
    v1, v2 = map(int, input().split())
    graph_list[v1].append(v2)

유방향 그래프는 무방향 그래프와 다르게 인접한 노드에 대해 방향이 정해져 있기 때문에 표현 시 제한이 있다.

입력값이 주어졌을 때 인접한 노드임을 나타내기 위해 v1의 위치와 v2의 위치에 서로 값을 넣어줬다면

유방향 그래프는 v1의 위치에 v2의 값을 넣어준다. 

 

# 인접 행렬
output = [
    [0, 0, 0, 0, 0, 0, 0],
    [0, 0, 1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 0],
    [0, 0, 0, 0, 1, 0, 0],
    [0, 0, 0, 0, 0, 0, 1],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0]]

# 인접 리스트
    [[], [2], [5], [4], [6], [1], []
]