Python의 인접 행렬
그래프 데이터 구조는 Python에서 네트워크 및 지도와 같은 다양한 실제 개체를 나타내는 데 사용됩니다. 인접 행렬을 사용하여 그래프를 나타낼 수 있습니다.
이 기사에서는 Python에서 인접 행렬을 구현하는 다양한 방법에 대해 설명합니다.
인접 행렬 만들기
다음 그래프를 고려하십시오.
그래프에는 1부터 6까지 번호가 매겨진 6개의 노드가 있습니다. 그래프에는 노드를 연결하는 7개의 에지가 있습니다. 에지 eij는 노드 i와 노드 j를 연결합니다.
그래프를 나타내기 위해 인접 행렬을 사용합니다.
- 인접 행렬은 2차원 그리드로 구성됩니다.
- 그리드의 각 행 또는 열은 노드를 나타냅니다.
- 무가중 그래프의 경우 위와 같이 그리드에서
(i,j)위치의 값이 1이면 노드i와 노드j가 연결되어 있음을 의미합니다. - 위치
(i,j)의 값이 0이면 노드i와 노드j가 연결되지 않습니다.
위 이미지의 그래프에 대한 인접 행렬을 만들려면 다음과 같이 표시됩니다.
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |
위의 표는 (i,j) 위치의 값이 (j,i) 위치에도 있음을 보여줍니다. 이는 에지 eij가 에지 eji와 동일하기 때문입니다.
이것은 또한 대각선을 따라 대칭인 인접 행렬을 생성합니다.
비가중 그래프에서 가장자리에는 가중치가 없습니다. 즉, 모든 모서리의 가중치가 동일합니다.
이로 인해 인접 행렬에는 값 0과 1만 포함됩니다.
이제 다음 가중 그래프를 고려하십시오.
가중 그래프의 경우 가장자리에 대한 가중치를 제외하고 모든 것이 동일하게 유지됩니다. 이미지에서 각 가장자리에 값이 할당된 것을 볼 수 있습니다.
따라서 인접 행렬에서 (i,j) 위치의 값은 그래프에서 eij 간선의 가중치입니다.
위 이미지의 인접 행렬은 다음과 같습니다.
| 0 | 5 | 0 | 0 | 0 | 0 |
| 5 | 0 | 1 | 12 | 0 | 0 |
| 0 | 1 | 0 | 8 | 0 | 4 |
| 0 | 12 | 8 | 0 | 7 | 0 |
| 0 | 0 | 0 | 7 | 0 | 2 |
| 0 | 0 | 4 | 0 | 2 | 0 |
다시 말하지만 행렬의 (i,j) 위치에 있는 값이 (j,i) 위치에도 있음을 관찰할 수 있습니다. 이는 에지 eij가 에지 eji와 동일하기 때문입니다.
다시 말하지만, 대각선을 따라 대칭 인접 행렬이 생성됩니다.
2D 목록을 사용하여 Python에서 인접 행렬 만들기
n 노드가 있는 비가중 그래프에 대한 인접 행렬을 만들기 위해 먼저 n 내부 목록을 포함하는 2차원 목록을 만듭니다. 또한 각 내부 목록에는 n개의 0이 포함됩니다.
0을 포함하는 2차원 목록을 생성한 후 그래프에서 가장자리 eij가 존재하는 위치 (i,j)에 1을 할당합니다. 이 작업을 위해 다음 단계를 사용합니다.
-
먼저
adjacency_matrix라는 빈 목록을 만듭니다. 그런 다음for루프와append()메서드를 사용하여 2차원 목록으로 변환합니다. -
for루프 내에서row라는 빈 목록을 만듭니다. 그런 다음 다른for루프를 사용하여 빈 목록을 0으로 채우고 마지막으로adjacency_matrix에row를 추가합니다. -
코드에서 튜플 목록을 사용하여 가장자리 집합을 표현했습니다. 각 튜플에는 그래프의 연결된 노드를 나타내는 2개의 값이 포함됩니다.
-
가장자리를 정의한 후
for루프를 사용하여 그래프에서 가장자리가 존재하는 위치에 값 1을 할당합니다.
암호:
import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
row = []
for j in range(col_num):
row.append(0)
adjacency_matrix.append(row)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
row = edge[0]
col = edge[1]
adjacency_matrix[row - 1][col - 1] = 1
adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
출력:
The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
[[0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]]
코드에서 0 기반 인덱싱이 있음을 알 수 있습니다. 이로 인해 각 노드 (i,j)는 인접 행렬에서 위치 (i-1,j-1)로 표시됩니다.
가중 그래프에 대한 인접 행렬을 만들려면 먼저 0이 있는 n x n 2차원 목록을 만듭니다. 그런 다음 행렬의 위치 (i,j)에서 가장자리 eij의 가중치를 할당합니다.
다음 예제에서 이를 관찰할 수 있습니다.
import pprint
row_num = 6
col_num = 6
adjacency_matrix = []
for i in range(row_num):
row = []
for j in range(col_num):
row.append(0)
adjacency_matrix.append(row)
weighted_edges = [
(1, 2, 5),
(2, 4, 12),
(2, 3, 1),
(3, 4, 8),
(4, 5, 7),
(3, 6, 4),
(5, 6, 2),
]
for edge in weighted_edges:
row = edge[0]
col = edge[1]
weight = edge[2]
adjacency_matrix[row - 1][col - 1] = weight
adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
출력:
The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
[[0, 5, 0, 0, 0, 0],
[5, 0, 1, 12, 0, 0],
[0, 1, 0, 8, 0, 4],
[0, 12, 8, 0, 7, 0],
[0, 0, 0, 7, 0, 2],
[0, 0, 4, 0, 2, 0]]
위의 코드에서 가장자리는 세 개의 숫자를 사용하여 표현되었습니다. 처음 2개의 숫자는 가장자리로 연결된 그래프의 노드를 나타냅니다.
세 번째 숫자는 가장자리의 가중치를 나타냅니다.
NumPy 모듈을 사용하여 Python에서 인접 행렬 만들기
NumPy 모듈을 사용하여 그래프에 대한 인접 행렬을 만들려면 np.zeros() 메서드를 사용할 수 있습니다.
np.zeros() 메서드는 (row_num,col_num) 형식의 튜플을 입력 인수로 사용하고 row_num x col_num 모양의 2차원 행렬을 반환합니다. 여기서 row_num 및 col_num은 행렬의 행 및 열 수입니다.
다음 단계를 사용하여 np.zeros() 메서드를 사용하여 인접 행렬을 만듭니다.
-
먼저 튜플
(n,n)을zeros()메서드에 전달하여 크기n x n행렬을 만듭니다. -
그런 다음 그래프의 모든 가장자리 eij에 대해
(i-1,j-1)위치에서 값을 1로 업데이트합니다. 여기서는 0 기반 인덱싱을 사용합니다. 이로 인해 노드(i,j)는 코드에서(i-1,j-1)위치로 표시됩니다.
위의 단계를 실행하면 다음 예제와 같이 인접 행렬을 얻을 수 있습니다.
import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
edges = [(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
for edge in edges:
row = edge[0]
col = edge[1]
adjacency_matrix[row - 1][col - 1] = 1
adjacency_matrix[col - 1][row - 1] = 1
print("The edges in the graph are:")
print(edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
출력:
The edges in the graph are:
[(1, 2), (2, 4), (2, 3), (3, 4), (4, 5), (3, 6), (5, 6)]
The adjacency matrix is:
array([[0, 1, 0, 0, 0, 0],
[1, 0, 1, 1, 0, 0],
[0, 1, 0, 1, 0, 1],
[0, 1, 1, 0, 1, 0],
[0, 0, 0, 1, 0, 1],
[0, 0, 1, 0, 1, 0]])
가중 그래프에 대한 인접 행렬을 만들기 위해 아래와 같이 (i,j) 위치의 값을 가장자리 eij의 가중치로 업데이트합니다.
import pprint
import numpy as np
row_num = 6
col_num = 6
adjacency_matrix = np.zeros((row_num, col_num), dtype=int)
weighted_edges = [
(1, 2, 5),
(2, 4, 12),
(2, 3, 1),
(3, 4, 8),
(4, 5, 7),
(3, 6, 4),
(5, 6, 2),
]
for edge in weighted_edges:
row = edge[0]
col = edge[1]
weight = edge[2]
adjacency_matrix[row - 1][col - 1] = weight
adjacency_matrix[col - 1][row - 1] = weight
print("The edges in the graph are:")
print(weighted_edges)
print("The adjacency matrix is:")
pprint.pprint(adjacency_matrix)
출력:
The edges in the graph are:
[(1, 2, 5), (2, 4, 12), (2, 3, 1), (3, 4, 8), (4, 5, 7), (3, 6, 4), (5, 6, 2)]
The adjacency matrix is:
array([[ 0, 5, 0, 0, 0, 0],
[ 5, 0, 1, 12, 0, 0],
[ 0, 1, 0, 8, 0, 4],
[ 0, 12, 8, 0, 7, 0],
[ 0, 0, 0, 7, 0, 2],
[ 0, 0, 4, 0, 2, 0]])
결론
이 기사에서는 Python에서 인접 행렬을 구현하는 두 가지 방법에 대해 설명합니다. NumPy 모듈로 인접 행렬을 구현하는 것이 저장소 요구 사항 측면에서 훨씬 더 효율적이므로 권장합니다.
또한 NumPy 어레이에서 다양한 작업을 수행하는 것이 시간 및 메모리 요구 사항과 관련하여 훨씬 더 효율적입니다.
Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.
GitHub