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

그래프?

• 그래프는 정점(Vertext)의 집합과 간선(Edge)의 집합으로 이루어진 자료구조
• 정점의 집합을 V, 간선의 집합을 E, 그래프를 G 라고 했을 때 G = (V,E)이다
• 정점은 위치를 의미, 간선은 정점과 정점을 연결하는 선을 의미

그래프 트리

	그래프	트리
방향성	방향 그래프 or 무방향 그래프	방향 그래프
순환성	순환 및 비순환	비순환
루트 노드 존재 여부	루트 노드가 없음	루트 노드가 존재
노드간 관계성	부모와 자식 관계 없음	부모와 자식 관계
모델의 종류	네트워크 모델	계층 모델

그래프 용어 

그래프에만 쓰이는 몇 가지 기술 용어가 있다

• 각 노드를 정점(Vertext)
• 정점을 잇는 선도 그래프 용어로 간선이라 부른다
• 간선으로 연결된 정점은 서로 인접하다(Adjacent)
• 인접한 정점을 이웃 = neighbor
• 모든 정점이 서로 연결된 그래프를 따로 연결 그래프(Connected Graph)
• 노드에 연결된 간선의 수를 차수(Degree)
• 그래프에서 노드들을 연결하는 간선의 순서를 나타내는 순서쌍인 경로(Path)
• 동일한 노드로 되돌아오는 경로를 사이클(Cycle) 즉, 경로의 시작 노드와 끝 노드가 동일한 경우를 말한다
• 간선에 할당된 값 또는 비용을 나타내는 가중치(Weight)

구현 방법

노드 개수 V, 간선 개수 E 일때

• 인접 행렬(Adjacency Matrix) : 2차원 배열을 사용하는 방식

O(V^2)만큼의 메모리 공간 필요
간선의 비용을 아는데 O(1)의 시간 소요

• 인접 리스트(Adjacency List) : 리스트를 사용하는 방식

O(E)만큼의 메모리 공간 필요
간선의 비용을 아는데 O(V)만큼의 시간 소요

그래프 종류

무방향 그래프 / 방향 그래프

https://coding-factory.tistory.com/610

https://coding-factory.tistory.com/610

• 간선이 방향성을 가지고 있으면 방향성 그래프(Directed Graph)
• 방향성이 없으면 부방향성 그래프(Undirected Graph)

가중치 그래프

https://coding-factory.tistory.com/610

• 그래프에 가중치 또는 비용이 할당된 그래프(네트워크 이론이나 신경망 이론에 활용되는 개념)

연결 그래프 / 비연결 그래프

https://velog.io/@boyeon_jeong/그래프-종류-및-개념

• 모든 노드에 대해 경로가 존재하면 연결 그래프
• 특정 노드에 대한 경로가 하나라도 존재하지 않을 경우 비연결 그래프

완전 그래프

https://coding-factory.tistory.com/610

• 그래프의 모든 정점이 간선으로 연결되어 있는 그래프

그래프의 탐색

DFS

[자료구조] DFS (Depth-First Search)

[자료구조] DFS (Depth-First Search)

 

BFS

[자료구조] BFS(Breadth-First Search)

[자료구조] BFS(Breadth-First Search)

 

연습

 

 

Reference

[Algorithm] 자료구조 그래프(Graph)란 무엇인가?

그래프 종류 및 개념 (알고리즘 문제 추천)

[알고리즘] 그래프(Graph)