99클럽 코테 스터디 29일차 TIL + Graph(1)

학습 키워드

- Graph

 

공부한 내용

그래프 Graph 

• 그래프는 객체 또는 개체 간의 관계를 표현하는 자료구조이다.
• 그래프(Graph)는 정점(Vertex)의 집합 V와 간선(Edge)의 집합 E로 구성된 비선형 데이터 구조다.
• 그래프는 노드(Node)와 노드 사이를 연결하는 간선(Edge)으로 구성된다.

+ 노드(정점, Vertex) : 일반적으로 개별적인 개체나 개념

+ 간선 : 노드 사이의 관계

+ 그래프에서 자주 사용하는 용어

• vertex(정점): 노드(Node)라고도 하며 정점에는 데이터가 저장된다.
• edge(간선): 링크(arcs)라고도 하며 선을 통해 노드간의 관계를 나타낸다.
• adjacent vertex(인접 정점): 하나의 정점에서 edge에 의해 직접적으로 연결된 정점을 나타낸다.
• degree(차수): 무방향 그래프에서 하나의 정점에 인접한 정점의 수를 의미한다.

그래프는 현실 세계의 다양한 상황을 모델링하고 문제를 해결하는데 도움이 된다.

그래프의 종류

그래프는 vertex와 edge로 구성되어 있기만 하면 굉장히 다양한 방법으로 그려질 수 있다. 그리고 특징에 따라 여러 그래프를 특정 지을 수 있다.

방향 그래프(Directed Graph)

방향성(유향) 간선 (Directed edge)

• 방향을 가진 정점의 쌍 (u, v)으로 화살표로 표현하고 단방향을 가리킨다.
• 첫 번째 정점 u는 출발점을 의미하고 두 번째 정점 v는 도착점을 의미한다.
• 방향성 간선을 가진 그래프를 **방향성 그래프(Directed Graph)**라고 한다.

무방향성(무향) 간선(Undirected edge)

• 방향이 없는 정점의 쌍(u, v)으로 직선으로 표현한다.
• 무방향성 간선(u, v)와 (v, u)는 같다.(양방향을 가리킴)
• 무방향성 간선을 가진 그래프를 **무방향성 그래프(Undirected Graph)**라고 한다.

이 방향 그래프에서는 반드시 화살표 방향으로만 노드간의 이동을 할 수 있다.

가중치 그래프

노드 혹은 객체의 연결에 가중치가 부여된 형태의 경우를 의미하며 '네트워크'라고 불리기도 한다.

edge에 가중치가 부여된 그래프로 가중치는 양수와 음수 모두 될 수 있다.

위의 그림에서 A 부터 B까지 갈 수있는 경로는 두 가지이다.

• A -> B
• A -> C -> B

만약 가중치가 없다면 가장 적은 횟수로 갈 수 있는 첫번째 방법이 당연히 더 효율적일 것이다.

하지만 가중치 그래프이기 때문에 가중치를 비교해 보면 첫번째 방법은 '7'의 비용이 소모되고 두번째 방법은 총 '3'의 비용이 소모되기 때문에 두번째 방법이 더 효율적인 방법이 될 수 있는 것이다.

순환 그래프(Cyclic Graph)

한 vertex에서 edge를 타고 가다보면 다시 그 vertex로 돌아오게 되는 그래프를 순환 그래프라고 한다.

반면, 순환이 되지 않는 그래프(사이클이 없는)는 Acyclic Graph(비순환 그래프)라고 하며, 그래서 우리가 앞에서 배운 트리 구조는 순환이 없고 방향만 존재하는 Directed Acyclic Graph 이다.

신장트리(Spanning Tree)

기존 그래프에 모든 노드가 연결되어 있으면, 트리의 속성을 만족하는 그래프로 트리의 속성을 만족하기 때문에 사이클이 존재하면 안된다.

최소 신장트리(Minimun Spanning Tree, MST)

위의 신장트리(Spanning Tree) 중에서 edge의 가중치 합이 최소인 신장트리를 의미한다.

희소 그래프 (Sparse Graph) & 밀집 그래프 (Dense Graph)

• 희소 그래프는 노드 수보다 간선 수가 적은 그래프를 말한다.
• 밀집 그래프는 노드 수보다 간선 수가 큰 그래프이다.

완전 그래프(Complete Graph)

• 그래프에 속한 모든 정점들이 상호 연결된 그래프이다.
• n개의 정점의 수가 있는 경우 간선의 수는(n - 1)*n / 2 개가 다.

차수(Degree)란?

무방향 그래프에서는 단순히 차수(Degree)만을 계산한다. 즉, 특정 vertex에 연결된 간선의 갯수를 차수라고 보는 것이다.

유방향 그래프에서는 내차수(In-Degree)와 외차수(Out-Degree)를 계산한다. 내차수는 현재 정점 방향으로 들어오는 간선의 갯수이며, 외차수는 현재 정점에서 다른 정점 방향으로 나가는 간선의 갯수이다.

 

회고

발생한 문제

- 자료구조에 대한 공부가 부족하다고 생각했다.

 

해결 방법

- 자료구조인 그래프에 대해 공부했다.

 

 

 

참고 자료

- https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph%EA%B7%B8%EB%9E%98%ED%94%84#1.%20Graph%20-%20%EA%B7%B8%EB%9E%98%ED%94%84%EB%9E%80%3F-1

- https://hoehen-flug.tistory.com/33