Graph

트리는 root에서 자식방향으로만 edge가 흘러가고 사이클이 없는 그래프의 한 종류 이다

그럼 그래프는 무엇인가?

그래프의 구성 요소

• 정점(vertex)
• 간선(edge)

그래프는 정점과 간선으로 구성된 자료구조를 이야기한다 트리와 구조적으로 비슷하지만 그래프는 각 간선이 방향성을 가질 수 있다

그래프의 종류

Direct 는 한가지 방향을 가지는 그래프

Undriect 는 양방향을 가지는 그래프를 이야기한다

Graph

Graph의 구현

1. Adjacency Matrix : 그래프를 행렬에 표시하는 방식

   

   • 해당 노드와 연결된 노드는 1 연결안된 노드는 0으로 행렬을 만들어서 나타낸다

2. Adjacency List : 해당 노드와 연결되어 있는 노드를 리스트의 형태로 나타내는 것이다

   

   • 해당 노드와 연결된 노드들을 리스트 형식으로 각 배열 요소에 저장한다

DFS( 깊이 우선 탐색)

• 한 방향으로 갈 수 있을 때 까지 가다가 더 이상 갈 수 없게 되면 backtracking을 이용해서 방문하지 않은 정점이 있는 지 체크한다 모든 정점의 backtracking을 완료하면 종료한다

BFS( 너비 우선 탐색)

• 시작 정점으로 부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
• 큐를 이용해서 구현한다