그래프

그래프란?

• 그래프는 트리(Tree)를 포괄한 개념
• 구조가 복잡한 자료 구조는 선형 구조나 트리로 표현 불가
• 연결되어 있는 원소 간의 관계를 표현하는 자료 구조

그래프 구성

• 정점(Vertex)와 객체를 연결하는 간선(Edge)로 구성
• 그래프 G를 G = (V, E)로 정의한다.

그래프 종류

1. 무방향 그래프

• 간선에 방향이 없는 그래프
• 양쪽으로 다 갈 수 있음

[[1, 2], [1, 3]...] 이런 식으로 정점이 연결되었다고 표현한다. 이를 2차원 배열로 표현하면

[1, 2]가 연결되어있으니까 2차원배열 graph에 graph[a][b] = 1, graph[b][a] = 1로 표현해준다.

주어진 간선 정보를 2차원배열로 다 나타내면 위 그림처럼 나온다. 이를 인접행렬이라고 부르고, 2차원배열로 문제를 풀면 된다.

2. 방향 그래프

• 간선에 방향이 있는 그래프

• 한쪽으로만 갈 수 있음

  

  아래와 같이 간선 정보가 들어온다.

  

  

방향이 있는 그래프니까 graph[a][b] = 1로만 표현해준다. 노드가 갈 수 있는 정점을 찾을 때는, 행을 중심으로 열이 1인 정점을 찾으면 된다.

3. 가중치 그래프

• 간선에 가중치를 할당한 그래프

• 네트워크라고도 부름

• 노드에서 노드로 이동할 때의 비용을 표현

  

각각 정점을 a, b로 표현하고 가중치를 c로 표현한다. 가령 1에서 2로 이동할 때 가중치가 2다. 그러면 graph[a][b] = c

참고 : 인프런
참고 : https://taesung1993.tistory.com/35