자료구조 - 그래프

그래프

그래프는 정점과 간선으로 구성되는 자료구조. 정점은 하나의 객체를 의미하며 Vertex 노드라고 표현한다. 간선은 정점과 전점을 이어주는 선을 의미한다.

 

용어

정점 : Vertex라고 하며 하나의 점을 의미한다

간선 : edge라고 하며 정점과 정점 사이를 이어주는 선을 의미한다.

정점의 차수 : 정점의 연결되어있는 간선의 개수

가중치 : 간선의 가중치

 

가중치 그래프

간선에 가중치를 보유한 그래프

방향 그래프

간선이 방향을 가지고 있는 그래프. 간선의 방향으로만 이동이 가능하다.

그래프를 표현하는 방법

인접행렬

정점의 개수 N에 대해 N * N의 사이즈로 0과 1로 구성된 이차원 배열을 사용하여 구해주는 방법.

a라는 인접행렬을 만들었다면 a[i][j]의 값은 i번 정점에서 j로 가는 정점이 연결되어 있으면 1, 아니면 0이 된다.

 

 

인접 리스트

Linked List로 간선을 구성해주는 방법.

Linked List를 정점의 개수 N개만큼 만들어 주면 된다.

 

 

 

https://babbab2.tistory.com/

개발자 소들이