개요 😄

그래프가 뭘까?
그래프란 현상이나 사물을 정점과 간선으로 표현한 것이라고 한다. 작년에 이산 수학 시간에 배운 기억이 있다.

그래프를 표현하는 방식은 굉장히 다양하다.

그래프의 표현

💡 첫번째 그래프 표현: 인접 행렬

인접행렬을 만드는 것은 굉장히 간단하다.

만약에 그래프가 이렇게 있었다고 생각해보자. 철수 기준으로 생각해보면 철수는 영희 / 동근 / 준호 / 승우와 연결되어 있다.

그러면 이 연결되어 있는 것을 체크해주면 된다.
이런 식으로 말이다. 영희 / 동근 / 준호 / 승우 는 숫자로 표현하면 1 / 2 / 3/ 5 이기 때문이다.

여기서 좀 더 복잡하게 방향 그래프를 인접 행렬로 표현할 수도 있다. 지금 위의 그림은 대칭이지만 방향 그래프로 만들면 대칭이 아니게 된다.

예시는 다음과 같다.

굉장히 직관적이면서 간선의 존재 여부를 즉각적으로 파악할 수 있다는 장점이 있다.

하지만 n * n 행렬을 유지하기 위해서 n ^ 2 의 공간이 필요하다는 단점이 있으면 또 이 행렬의 준비과정에서 n ^ 2의 시간이 필요하다.

간선의 밀도가 높은 경우에는 적합하지만 그렇지 않으면 낭비가 심하다.

💡 두번째 그래프 표현 : 인접 리스트

인접 리스트는 각 정점에 인접한 정점들을 (연결) 리스트로 표현한 것이라고 한다.

방향이 없는 그래프로 총 노드의 수는 총 간선의 수 * 2 라고 한다.

인접 리스트는 장접이 공간 낭비가 거의 없다는 점이다. 하지만 링크를 위해서 공간이 오버헤드 된다.

간선이 별로 없는 희소 그래프에서 적합하다고 한다. 간선의 밀도가 높은 경우에는 링크를 위한 오버헤드로 비효율적이다.

💡 세번째 그래프 표현 : 인접 배열

위에 것과 차별점은 각 정점에 연결된 정점들을 연결 리스트 대신 배열로 저장한 것이라고 한다.

링크를 위한 공간을 절약한다는 장점이 있다.
또 메모리 공간 지역성이 높아진다는 장점이 있다.

삽입과 삭제가 불편한 것이 배열이기 때문에 그래프가 한 번 만들어 진 후에 변하지 않는 경우에 적합하다고 한다.

배열 내에서 이진 탐색이 가능한 구조이다. ([log 2k] + 1 ) 번 내로 인접한지 확인 가능함.)

💡 네번째 그래프 표현 : 인접 해시 테이블

점점 뒤에 뭔가 추가된다.

이렇게 배열을 해쉬로 만들어 주는 것이다. 이렇게 바꾸어주면 당연하게도 빠르다. 하지만 인접 리스트에 준하는 크기가 되어 버린다. 순차 탐색에는 비효율적이라고 한다.

그래프의 순회

한 정점에서 시작하여 도달 가능한 모든 정점을 방문하는 것이다.

대표적인 알고리즘으로는 너비 우선 탐색과 깊이 우선 탁색이 있다. 교수님이 깊은 직관이 필요하다고 한다.

🪃 첫 번째 순회 방법 : BFS(너비 우선 탐색)

그림을 보면 상위 노드에서 하위 노드로 갈 때 상위 노드와 연관된 모든 노드로 가는 것이다.

알고리즘은 큐 를 사용해서 만든다.

그래프가 2개 이상 끊겨 있으면 모든 정점을 방문하기 위해서는 여러번 BFS를 수행할 수 있다.

🪃 두 번째 순회 방법 : DFS (깊이 우선 탐색)

이건 계속해서 하위로 내려 가는 것이다. 더이상 갈 수 없으면 그 다음 내려가는 길을 찾아서 내려간다. 마지막에 어떤 모양으로 되는지 기억하자.

이건 재귀적인 형태로 알고리즘을 만드나 보다.

최소 신장 트리

연결 그래프 : 간선의 방향이 없는 그래프에서 모든 정점들 간에 간선을 따라 서로 다다를 수 있는 그래프

신장 트리 : 트리는 " 싸이클이 없는 연결 그래프 "

최소한의 간선을 사용하여 연결된 그래프를 신장 트리라고 함. 여러 모양의 신장 트리가 생김.

최소 신장 트리 : 간선의 가중치 합이 최소가 되도록 하는 신장 트리

첫번째 : 프림 알고리즘

얘도 작년 이산 수학 시간에 배웠다.

노드에서 가장 작은 간선을 선택해 나간다.

두번째 : 크루스칼 알고리즘

여러 정점 집합으로 시작해 집합을 합쳐 나간다.

세번째 : 위상 정렬

상후 선후 관계가 존재하는 작업 정렬하기