그래프란?
그래프는 무엇일까..? 우선 트리를 생각해보자. 트리는 Root 가 있고 Root부터 시작해서 아래로 내려가는 구조로 되어있다. 트리도 그래프의 일종이라고 한다.
그렇다면 그래프는? 방향이 있을 수도 있고 없을 수도 있으며 원형일 수도 있고... 으악 복잡해!
우선 하나 하나 알아보자.
알아보기 전에! 그래프는 정점과 간선으로 이루어져있다는 것을 알고 가자.
여기서 정점은 Tree에서 Node 와 같고 간선은 Tree와 똑같다. 연결하는 선을 뜻한다.
방향 Directed / 무방향 Undirected
정점을 연결하는 간선에 방향이 있고 없고의 차이이다.
싸이클 / 어싸이클
그래프 중 하나 이상의 써클이 있으면 싸이클릭 그래프 없으면 어싸이클릭 그래프라고 한다.
싸이클을 표현하는 방법
1. 2차원 배열에 표현하는 Adjacency Matrix
서로 연결된 노드들은 1, 연결이 없으면 0이라고 표현한다. 자기 자신과 연결이 없다면 0이라고 표현
2. LinkedList 로 표현하는 Adjacency List
노드 1,2,3,4 를 배열로 표현하고 각 노드와 인접한 노드들을 링크드리스트로 표현한다.
