인접행렬

[파이썬으로 배우는 자료구조] 그래프(Graph)

그래프(Graph)란? 그래프는 노드(정점)와 간선으로 이루어진 집합으로 표현되는 자료구조입니다. 위 그래프에서 A, B, C는 노드이고, 이 노드를 연결한 선이 간선입니다. 두 노드가 연결되어 있으면 두 노드는 인접하다고 표현됩니다. 따라서 위의 그래프에서는 A, B가 서로 인접하고, A, C가 서로 인접합니다. 또한 그래프는 위 그림과 같이 간선이 방향을 갖고 있지 않는 무방향 그래프, 간선이 방향을 갖고 있는 방향 그래프, 그리고 간선이 가중치를 갖고 있는 가중치 그래프로 나뉩니다. 위의 그래프는 간선이 방향을 갖고 있으므로 방향 그래프입니다. 무방향 그래프처럼 A, B가 모두 연결되어 있는 것이 아니라 A, B를 잇는 간선이 A에서 B 쪽으로 방향을 갖고 있어서 A가 B로는 인접하고, B에서 A로..