그래프(Graph)

1. Graph

- graph is simply a set of values that are related in a pair wise fashion.

- Node(=Vertex)와 Edges(간선)로 이루어짐.

- great data structure to model real world relationships.

- LinkedList는 Tree의 일종이고, Tree는 Graph의 일종이다. (Tree는 directed graph)

- self-edge라고 node가 자기 자신을 가리키는 경우가 있을 수 있다.

 

2. Graph의 종류들

(1) directed : 방향성이 있음. 일방통행

(2) undirected : 방향성이 없음. 양방향 통행

---

(1) weighted : 가중치 그래프

(2) unweighted : 가중치가 없는 그래프.

보통 최적의 경로 계산하기 위해서 사용

---

(1) cyclic : 순환 그래프. vertex들이 이어져 있으면 cycle이라 부름.

(2) acyclic : 비순환 그래프

 

3. programming에서 graph를 표현하는 방법

(1) edge list : i에서 j가 이어져 있다면 [ i, j ] 라는 리스트들을 만든다. 가중치 그래프라면 가중치를 추가할 수도 있다.

 

(2) adjacent list (인접 리스트) : HashMap<Integer, List<Integer>>로 만들거나 List<Integer,List<Integer>>로 만들기.

HashMap을 사용하면 key를 node 번호로 사용할 수 있지만, list를 사용하면 index를 node 번호로 일치 시켜야한다.

 

(3) adjacent matrix (인접 행렬) : NXN행렬을 사용하여 matrix[i][j]가 1이나 true라면 i에서 j로의 edge(간선)이 있다는 것이다. 무방향 그래프를 인접행렬로 표현하면 대칭행렬이 되고, 방향 그래프는 대칭행렬이 안될 수도 있다.

 

reference : 

 - 코딩인터뷰 완전분석 (인사이트)

- udemy - Master the Coding Interview: Data Structure + Algorithms (Zero To Mastery)

- 엔지니어 대한민국 유튜브 (https://www.youtube.com/watch?v=fVcKN42YXXI)