그래프(Graph)

---

그래프(Graph)?

정점 : 노드
간선 : 노드와 노드 사이의 연결하는 줄

그래프는 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조다. 정점 집합과 간선 집합으로 표현할 수 있다.

그래프 구현은 인접 행렬(adjacency Matrix), 인접 리스트(Adjacency List)로 구현할 수 있다.

특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 크게 방향 그래프와 무방향 그래프로 나뉜다.
• 간선은 가중치(값)을 가질 수 있다.
• 사이클이 발생할 수 있다.

무방향, 방향 그래프

무방향 그래프는 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.

연결 그래프

연결 그래프는 모든 정점이 서로 이동 가능한 상태인 그래프다.

비연결 그래프

비연결 그래프는 특정 점점쌍 사이에 간선이 존재하지 않는 그래프다.

완전 그래프

완전 그래프는 모든 정점끼리 서로 연결된 상태인 그래프다.

사이클

사이클은 그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분을 말한다.

인접 행렬(adjacency Matrix)

2차원 배열을 통해서 [시작 노드][도착 노드] 인덱스를 통해 요소는 가중치를 넣는다.

만약 무방향 그래프라면 [도착 노드][시작 노드]의 인덱스에서 똑같이 가중치를 넣어줘야한다.

const matrix = [
    [0, 5, 3],
    [5, 0, 0],
    [3, 0, 0],
]

인접 리스트(Adjacency List)

객체를 이용하여 key는 각 노드를 가르키고 value는 key의 각 노드를 출발해서 도착하는 노드와 가중치를 저장하는 배열을 통해 구현한다.

const graph = {
    1 : [ {arrive : 5, cost : 10}, ],
    3 : [ {arrive : 1, cost : 8} ], ],
}