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

그래프

• 그래프는 정점과 간선으로 이루어진 자료구조입니다.

 

그래프

용어

• 정점 : 노드(node)라고도 하며 정점에는 데이터가 저장됩니다. (0, 1, 2, 3)
• 간선 : 링크(arcs)라고도 하며 노드간의 관계를 나타냅니다.
• 인접 정점 : 간선에 의해 연결된 정점으로 위에서 (정점0과 정점 1은 인접 정점)
• 단순 경로 : 경로 중 반복되는 정점이 없는 것, 같은 간선을 지나가지 않는 경로
• 차수 : 무방향 그래프에서 하나의 정점에 인접한 정점의 수 (정점 0의 차수는 3)
• 진출 차수 : 방향 그래프에서 한 노드에서 외부로 향하는 간선의 수
• 진입 차수 : 방향 그래프에서 외부 노드에서 들어오는 간선의 수

 

그래프 구현 방법

• 그래프를 구현하는 방법에는 인접행렬와 인접리스트 방식이 있습니다.

 

인접행렬 방식

• 인접 행렬은 그래프의 노드를 2차원 배열로 만든 것입니다.
• 각 노드의 인접 정점이라면 1, 아니면 0을 넣어줍니다.

장점	2차원 배열 안에 모든 정점들의 간선 정보를 담기 때문에 배열의 위치를 확인하면 두 점에 대한 연결 정보를 조회할 때 O(1)의 시간 복잡도가 나옵니다. 구현이 비교적 간단합니다.
단점	모든 정점에 대해 간선 정보를 대입해야 하므로 O(n²)의 시간복잡도가 소요됩니다. 무조건 2차원 배열이 필요하기에 필요 이상의 공간이 낭비됩니다.

 

 

인접리스트 방식

• 그래프의 노드들을 리스트로 표현
• 정점의 리스트 배열을 만들어 관계를 설정해 구현

장점	정점들의 연결 정보를 탐색할 때 O(n)의 시간이 소요됩니다. (n : 간선의 개수) 구현이 비교적 간단합니다.
단점	특정 두 점이 연결되었는지 확인하려면 인접행렬에 비해 시간이 오래 걸립니다. 구현이 비교적 어렵습니다.

 

다양한 그래프의 종류

• 그래프는 구현되어진 특성에 따라 여러가지 종류로 나눠집니다.

 

무방향 그래프

• 무방향 그래프는 두 정점을 연결하는 간선에 방향이 없는 그래프입니다.

 

방향 그래프

• 방향 그래프는 두 정점을 연결하는 간선에 방향이 존재하는 그래프입니다.
• 간선의 방향으로만 이동할 수 있습니다.

 

가중치 그래프

• 가중치 그래프는 두 정점을 이동할 때 비용이 드는 그래프입니다.

 

완전 그래프

• 완전 그래프는 모든 정점이 간선으로 연결되어 있는 그래프입니다.

 

참고

[Algorithm] 자료구조 그래프(Graph)란 무엇인가? https://coding-factory.tistory.com/610