그래프는 정점과 간선의 집합으로 이루어진 자료 구조이다.
www.geeksforgeeks.org
각 정점(Node/Vertice)은 개별적인 항목이나 객체를 나타내고 간선(Edge)은 정점들 간의 관계를 나타낸다.
그래프의 간선에는 방향이 있을 수 있다. 방향이 있다면 방향 그래프, 없다면 무방향 그래프라 칭한다.
www.geeksforgeeks.org
그래프는 인접 행렬과 인접 리스트로 표현될 수 있다.
인접 행렬
무방향 그래프를 인접 행렬로 표현한다면, 단순히 그래프의 두 정점이 연결되어 있다면 두 정점에는 1, 연결되지 않았다면 0을 입력하면 그래프로 표현할 수 있다.
www.geeksforgeeks.org
방향 그래프는 무방향 그래프와 같지만, 방향이 존재하니 해당 노드를 행, 도착 노드를 열로 표현해 밑의 그림처럼 1,0 방향은 연결되어 있으니 1이지만 0,1은 0인 것을 확인할 수 있다.
www.geeksforgeeks.org
인접 리스트
두 번째 방법은 인접 리스트로 표현하는 방법이다.
먼저 무방향 그래프를 인접 리스트로 표현한다면 각 리스트에 자신과 연결된 정점을 넣으면 된다.
www.geeksforgeeks.org
방향 그래프도 무방향 그래프와 크게 다르지 않다.
인접 행렬과 마찬가지로 방향을 고려해서 리스트에 넣어주면 된다.
www.geeksforgeeks.org
그래프는 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)과 같은 알고리즘을 사용하여 탐색하거나, 최단 경로 문제 등의 문제를 해결하는 데 활용되는 중요한 자료 구조이다.
다음엔 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS)을 다루고자 한다.
항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
