https://visualgo.net/en

그래프 기본 컨셉

• 트리와 비슷해 루프를 형성할 수 있음
• 트리는 노드 탐색시 제한이 있지만 그래프는 루프형성이 가능
• 그래프는 object간 관계를 표현할때 유용하다
  (예시. SNS, 도로상 차량검색, 운송시스템)

그래프, 트리의 특징

• 그래프는 노드간 관계, 트리는 노드간 계층
• 그래프(순환-사이클, 가중치)
• 트리(루트, 부모, 자식, 서브, 계층)

그래프의 유형

• directed(방향성)
  - 한쪽 방향이 있고 순서가 있어서 마지막 노드가 있음
• undirected(무방향성)
  - 상호교환(화살표로 연결된 노드들이 서로 노드정보를 공유)
• 무방향성은 방향(화살표)이 따로 지정되지 않음
• 간선으로 연결된 노드들끼리는 서로 인접해 있으며 이웃이라고 칭함
• 순환 그래프

가중 그래프

• 가중그래프에는 edge와 관련된 값이 있음
• 각 edge의 가중치에 할당된 특정 값을 호출
• 가중치는 서로 다른 그래프에서서로 다른 데이터를 나타냄
  (ex. 도로 구간을 나타내는 그래프에서 가중치는 도로의 길이를 나타낼수 있음)
• 그래프에서 경로의총 가중치가 높을수록 경로 이동시간(비용)이 길어짐

순회

• 순회는 그래프에 연결된 노드를 탐색
• 아직 방문하지 않은 노드의 순회 순서

Directed Acyclic Graphs(DAGS)

• 방향성 비순환 그래프는 순환되지 않고 특정한 단방향 그래프
• 즉, 아래 그림처럼 edge가 순서대로 향하도록 DAG의 노드를 선형(단방향)으로 정렬

인접행렬

• 간선에 가중치가 있는 그래프면 1 대신에 가중치의 값을 직접 넣어주는 방식으로 구현

  장점

• 구현이 쉬움
  단점
• 연결된 모든 노드를 방문하고 확인해야해서 시간이 걸림