[알고리즘] 그래프란?

그래프(Graph)란? :

• 노드(Node)= (정점 Vertex)과 간선(Edge)으로 구성되어 있다.
• 그래프를 탐색한다라는 의미는 하나의 노드를 시작으로 다른 다수의 노드를 방문하는 것을 의미한다.
• 트리와 그래프는 비슷하지만 그래프는 위 B->C->E->D->B처럼 루프 형성이 가능하다.
• 두 노드가 간선으로 연결되어있다는 의미는 두 노드가 인접하다는 의미와 동일하다. 
• 프로그래밍에서는 그래프는 *두가지 방식(행렬(Matrix), 리스트(List))으로 표현이 가능한데 

*인접 행렬(Adjacency Matrix) 방식 : graph =[[]]

*인접 리스트(Adjacency List) 방식 : graph=[ [] for _ in range(n)] 

 

이 두 방식의 차이점은 아래와 같다

• 행렬 방식에서는 모든 관계를 저장하기에 노드 개수가 많아질 수록 메모리가 낭비되어진다.
• 인접 리스트 방식은 연결되어진 정보만을 저장하기 때문에 메모리를 효율적으로 사용한다.
  하지만 두 노드가 연결되어 있는지에 대한 정보를 얻어야 하는 시간이 필요하다.