그래프(Graph)

두 노드 사이의 관계가 있는 경우 에지로 연결하여 표현하는 추상적이고 일반적인 자료구조

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조

• 즉, 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
• Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등
• 그래프는 여러 개의 고립된 부분 그래프(Isolated Subgraphs)로 구성될 수 있다.

 

기본 구성

노드(node), 정점(vertex): 그림에서 노란 동그라미

에지(edge), 링크(link): 그림에서 갈색 선

 

그래프의 종류

무방향 그래프

그림에서 왼쪽 그래프

방향이 없다

 

방향 그래프

그림에서 오른쪽 그래프

방향이 있다

 

그래프의 표현

1. 인접 행렬

인접성을 행렬(2차원 배열/리스트)로 표현

 

2. 인접 리스트

각 정점에 인접한 에지만을 연결 리스트로 표현

 

그래프의 특징

• 그래프는 네트워크 모델 이다.
• 2개 이상의 경로가 가능하다.
  • 즉, 노드들 사이에 무방향/방향에서 양방향 경로를 가질 수 있다.
• self-loop 뿐 아니라 loop/circuit 모두 가능하다.
• 루트 노드라는 개념이 없다.
• 부모-자식 관계라는 개념이 없다.
• 순회는 DFS나 BFS로 이루어진다.
• 그래프는 순환(Cyclic) 혹은 비순환(Acyclic)이다.
• 그래프는 크게 방향 그래프와 무방향 그래프가 있다.
• 간선의 유무는 그래프에 따라 다르다.

---

출처:
https://velog.io/@averycode/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EC%8A%A4%ED%83%9D%ED%81%90%EA%B7%B8%EB%9E%98%ED%94%84-feat.Python#-graph

https://www.youtube.com/playlist?list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK