밸하~
밸로그 여러분 안녕하세요!

오늘은 자료구조중 비선형 자료구조인 그래프에 대해서 알아보겠습니다!

그래프란?

그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조입니다!

이 그래프는
정점 집합과 간선 집합으로도 표현할 수 있습니다!

여기서 정점과 간선은 노드(Node)와 엣지(Edge)라고도 불립니다!
이렇게만 들어서는 조금어렵죠?

일상생활에서 볼 수 있는 예제로
이 그래프는
인물관계도에서 볼 수 있습니다!
드라마나 영화의 인물관계도를 생각하시면 어떻게 생긴것인지 조금은 그려지실 것입니다!

여기서는 정점이 인물이고 간선은 인물과 인물간의 관계입니다!

실제 S/W에 적용된것은
지하철 노선도나 페이지 랭크 알고리즘이 있습니다!

지하철 노선도의 경우
각 정점이 지하철 역이 되며 각 지하철 역과 지하철 역 사이 간선은 이동시간 정보를 가지고 있습니다!

이번엔
페이지 랭크 알고리즘인데요
이 알고리즘은
저희가 가장 많이 사용한다고도 할 수 있는 구글이
존재할 수 있게된 검색 알고리즘 입니다!

간단히 설명을 드리자면
페이지 한개 한개가 정점이 되고 페이지에서 파생되는 링크들이 간선이 된다고 할 수있습니다!

페이지 랭크는 이런 방식으로 페이지와 링크를 수집하여 우선도를 측정하고 검색 결과를 계산합니다!

위의 두개만 봐도
그래프는 소프트웨어 개발에서 중요한 자료구조 중 하나입니다!

그러면 이러한 그래프는 어떤 특징을 가지고 있을까요??

그래프의 특징

1. 정점은 여러 간선을 가질 수 있다

• 이전에 배웠던 선형 자료구조는 앞 뒤로 한개의 자료만 가지고 있을 수 있었지만 ,
  비선형 자료구조인 그래프는 앞뒤로 여러개의 자료를 가질 수 있습니다

2. 크게 방향 그래프와 무방향 그래프로 나눌 수 있다

• 그래프는 크게 간선의 방향이 존재하는 방향그래프와 방향이 존재하지 않는 무방향 그래프로 나눌 수 있습니다!

3.간선은 가중치를 가질 수 있다

• 그래프의 간선은 가중치를 가질 수 있습니다!

4.사이클이 발생할 수 있다

• 마지막으로 그래프는 탐색시 계속 루프가 가능한 구역인 사이클이 있을 수 있습니다!
  그래서 탐색시에 무한루프에 빠지지 않도록 싸이클을 찾아야 할 필요가 있습니다!

자 이렇게 그래프의 특징에 대해서 알아보았는데요!

특징중에서 그래프는 크게 두가지로 나눌 수 있다고 이야기를 드렸죠??

이번에는 두가지 그래프를 한개씩 알아보겠습니다!

1. 무방향 그래프

먼저 무방향 그래프 입니다!
무방향 그래프는 말 그대로 간선에 방향이 존재하지 않습니다!
이것을 반대로 생각하면 양뱡향으로 이동가능한 간선으로 이루어져 있다고도 할 수 있습니다!

즉 한개의 정점에서 그 다음정점으로 이동할 수 있고 반대로 그 다음정점에서 다시 원래의 정점으로도 올 수 있다는 것입니다!

그 다음은

2. 방향 그래프

방향 그래프입니다!
방향 그래프는 이름 그대로 간선에 방향이 존재하는 그래프 입니다!

즉 방향이 존재하기 때문에
한개의 정점에서 그 다음 정점으로 이동할 수 있지만
그 다음 정점에서 기존의 정점으로 가는 방향의 간선이 없이는 다시 돌아올 수 없습니다!

이렇게 두 가지 그래프에 대해서 알아보았는데요
이번엔 방향이 아니라 연결상태에 따른 분류에 대해서도 알아보겠습니다!

연결상태에 따른 그래프

연결상태에 따른 그래프 분류는 세가지가 있습니다!

1. 연결 그래프

먼저 연결그래프는 모든 정점이 서로 이동 가능한 상태인 것을 의미합니다!
특정 정점에서 또 다른 특정 정점까지 모든 경우의 수가 이동 가능해야합니다!

2. 비연결 그래프

연결 그래프가 있다면 반대로 연결이 되어있지 않은 그래프 또한도 있어야겠죠??

그중 한 정점이 하나의 간선도 연결되지 않은 그래프를 비 연결 그래프라고 합니다!

3. 완전 그래프

마지막으로 완전 그래프입니다!

모든 정점끼리 연결된 상태를 의미합니다!
따라서 한 정점의 간선 수는 모든 정점의 수 -1 이 됩니다!
그리고 모든 정점의 수-1 을 한 값에 모든 정점 수를 곱하면 모든 간선 수를 알 수 있습니다!

자 이렇게 그래프의 분류에 대해서 알아보았는데요!

이번엔 특징을 설명할때 나왔던 용어인데 익숙하지 않는게 있었죠?
네! 바로 사이클 입니다!

이번엔 사이클에 대해서 알아보겠습니다!

사이클이란?

사이클은 이름 그대로 순환되는 영역을 의미하고 있습니다!

그럼 이 사이클이 들어간 그래프는 어떻게 구현할 수 있을까요??

사이클이 들어간 그래프의 구현 방법

사이클이 들어간 그래프는 두가지 방법으로 구현할수 있습니다
바로
인접행렬,인접 리스트 입니다!

인접행렬은 2차원 배열을 이용할 수 있고
인접 리스트는 연결리스트로 표현 가능합니다!

자 그럼 인접해렬은 어떻게 구현하는지 알아볼까요??

인접행렬 구현법

인접행렬은 간단합니다!
정점의 크기만큼 2차원배열을 만들고 연결이 안된상태로 초기화 합니다!
이후 행렬의 열 부분을 시작정점 행 부분을 도착정점으로 두고
true값을 넣어주면 간선이 연결된것으로 칩니다!
이런식으로 쉽게 구현이 가능합니다!

만약 간선에 가중치를 넣고 싶다면
false와 true가 아닌
null과 임의의 가중치 값을 넣으시면 됩니다!

참고로,
무방향 그래프를 구현한다면!
모든 값을 대칭으로 넣어주면 됩니다

인접 리스트 구현법

이번엔 인접리스트 구현방법 입니다!

인접리스트의 구현 또한도 간단합니다

특히 js의 배열은 연결리스트처럼 값이 무한정 늘어날 수 있기때문에
정점의 수 만큼 배열을 만든 이후 연결할 정점을 배열에 추가하면 됩니다!

자 오늘은 이렇게 그래프에 대해서 알아보았는데요!

그래프의 특징과 분류방법 그리고 사이클에 대해서 알아보았습니다!

그럼 오늘도 이만
밸~바!