[Algorithm] 그래프 자료구조(Graph)

✨그래프(Graph)

그래프(graph)는 vertex와 edge로 구성된 한정된 자료구조를 의미한다.
vertex: 정점
edge:   정점과 정점을 연결하는 간선

 

 

✨그래프(Graph)종류

 

무방향그래프

그래프를 연결하는 간선에 방향이없다.

 

 

 

방향그래프

그래프를 연결하는 간선에 방향이있다.

 

 

 

가중치 그래프

그래프를 연결하는 간선에 코스트가있다.

 

 

 

완전그래프

그래프의 모든 정점이 간선으로 연결되있다.

 

 

 

 

 

✨그래프(Graph)구현

인접행렬

그래프의 정점을 2차원 배열로 표현
연결됨:1    (가중치 그래프일 경우 가중치로 표현)
연결안됨:0
O(n^2) 시간 복잡도

 

https://www.cs.mtsu.edu/~xyang/3080/adjacencyMatrix.html

인접리스트

그래프의 노드를 리스트로 표현
각정점에 대한 인접정점을 순차적으로 표시  
O(n) 시간 복잡도

 

 

https://www.geeksforgeeks.org/adjacency-list-meaning-definition-in-dsa/

 

 

 

 

 

 

🎈참고자료

https://80000coding.oopy.io/125156cf-79bb-48da-82ae-1f2ee7896bb8

https://suyeon96.tistory.com/32