[자료구조][C언어]그래프란?(1)_그래프의 개념

 

그래프의 개념

 

그래프란 지하철 노선도, 도로망 등 연결되어있는 것들 간의 관계를 표현하는 자료 구조라 생각하면 된다. 

도로망, 교통망, 길찾기 기능 등등을 만들 때 매우 적절하게 사용이 가능하다.

 

그래프의 정의 및 구조

 

그래프는 다음 그림과 같이 객체인 정점(Vertex, or Node)과 이러한 정점들 간의 관계를 나타내는 간선(Edge, or Line)으로 구성되어있다.

 

그래프 관련 용어

 

V(G): 그래프G의 정점들의 집합

E(G): 그래프G의 간선들의 집합

부분 그래프: 그래프의 부분집합. V(G)와 E(G)의 부분집합으로 구성된 그래프

 

인접 정점(adjacent Vertex): 한 정점에 대해 간선으로 직접적으로 연결된 정점들을 의미한다.

ex) G1의 0의 인접 정점은 1, 2이다.

 

그래프의 차수(degree): 무방향 그래프의 경우 하나의 정점에 연결된 간선의 수를 의미하며,

ex) G1의 0의 차수는 2이다.

방향 그래프의 경우 하나의 정점에 대해 들어오는 간선의 개수는 진입 차수(in-dgree), 나가는 간선의 개수는 진출 차수(out-degree)라고 한다.

ex) G2의 0의 진출 차수는 1, 진입 차수는 2이다.

 

그래프의 경로: 무방향 그래프에서 정점 a부터 임의의 정점 k까지의 경로를 의미. 정점의 나열로 표현한다.

단, 나열된 정점들 간에는 간선이 무조건 존재해야 한다.

ex) G1에서 A, B, D는 경로이다. B, D, A는 경로가 아니다. 

단순 경로: 경로 중에 반복되는 간선이 없는 경로 ex) A, B, D는 단순 경로이다.

사이클: 경로 중에서 시작점과 끝점이 같은 경로 ex) A, B, C, A는 사이클이다. 단순 경로가 아니다.

 

연결 그래프: 그래프에서 모든 정점 쌍에 대해서 경로가 존재하는 그래프를 의미한다.

 

완전 그래프: 모든 정점이 간선으로 연결되어있는 그래프를 의미한다. N개의 정점을 가지는 완전 그래프의 간선의 개수는 N*(N-1)/2 개다.

 

 

 

 

그래프의 종류

 

그래프의 종류에는 는 무방향 그래프, 방향 그래프, 가중치 그래프 등 다양한 종류가 있다.

 

무방향 그래프의 경우는 위의 G1과 같이 간선에 방향이 없는 그래프를 의미하며,

방향 그래프의 경우는 G2와 같이 간선에 방향이 있는 그래프를 의미한다.

가중치 그래프는 간선에 가중치가 존재하는 그래프를 의미한다. 

 

 

그래프의 표현 방식

 

그래프는 나타내는 방식에는 대표적으로 인접 행렬 방법(adjacent matrix)과 인접 리스트(adjacent list) 방법이 있는데 오늘은 이 두 개에 대해서 알아볼 예정이다.

 

 

인접 행렬 방법(adjacent matrix)

 

간선 (i, j)가 존재하면 M[i][j] = 1

존재하지 않으면 M[i][j] = 0으로 나타내는 방식이다.

 

 

인접 리스트 방법(adjacent list)

 

각 정점에 인접한 정점을 연결 리스트로 나타내는 방식이다.

 

 

 

오늘은 자료구조로서의 그래프가 무엇인지와 그래프를 어떻게 나타내는지에 대해 알아보았다.

혹시 잘못되거나 궁금한 점이 있다면 언제든 댓글을 달아주시면 감사하겠습니다!!

 

 

참조

 

천인국 외 2인 , C언어로 쉽게 풀어쓴 자료구조, 생능출판, 2019