면접 대비 자료구조 공부 ( 호로비츠 6장 그래프)

6장 그래프

6.1.3 그래프 표현법

1. 인접 행렬

??무슨말인지 모르겠다. 그래프 G에 있는 간선의 수를 알고자 하거나 그래프 G가 연결되어 있는가를 알고자 할 경우??
그래프 G가 연결되어 있는가를 알고자 한다는게 무슨말이징 ㅠ
어쨋든 이경우 O(n^2) 희소 그래프의 경우 O(e+n) 시간 복잡도라한다. -> 이 부분 이해 잘 못했다.

알고리즘 문제 풀다가 인전 리스트로 구현한적은 많은데 인접 행렬로 구현한 적은 없는거 같다 언제 쓰는 놈일까

2.인접 리스트

이 놈은 구현을 c++ vector로 워낙 많이해 보아서 잘안다고 생각하는데.... 아닐수도...

아 모르는 용어
진입 차수 : 해당 노드로 부터 나간 간선의 숫자
진출 차수 : 해당 노드로 들어오는 간선의 숫자

3. 인접 다중 리스트 (adjacency multilists)

잘 이해 안됬다 책봤는데
그래서 이 분 블로그 예시 보고 이해함
[링크] : https://kingpodo.tistory.com/46>

핵심은 노드들에 대한 배열과 간선을 기준으로 저장한다는 것 같다. 리스트에는 해당 간선을 방문했는지 표시와 해당 간선에 연결된 두 노드를 표시하고, 각 노드가 어떤 간선으로 이어지는지 알려준다.

관련된 문제를 풀어보는게 제일일거 같은데 대충 찾아보니 안나온다.

가중치 간선 (weighted edge)

가중치 간선을 가진 그래프를 네트워크(network)라 한다 함.

6.2 그래프의 기본 연산

깊이 우선 탐색

인접 리스트에서 구현을 가정하면
방문 지점을 스택에 저장하면서 한 노드에 연결된 지점들중 한 곳을 방문한다, 그리고 방문 안한 인접 리스트가 없는 노드에 도달하면 스택에서 하나 뺀다. 그리고 해당 노드에서 방문 안한 지점들을 방문하고 스택에 넣는 과정을 반복한다. pre order와 비슷하며 방문에 대한 체큰는 전역 변수로 visit을 사용한다. 스택이 비면 끝난다.

너비 우선 탐색

첫 시작 노드를 큐에 넣는다. 큐에서 뺀 노드를 방문하고 방문한 노드의 인접 리스트들 중 방문 안한 노드들을 큐에 넣는다. 이 과정을 반복한다. 큐가 비면 끝난다.

6.2.3 연결 요소 (connected component)

인접 리스트를 사용한 무방향 그래프의 연결 여부에 대한 시간 복잡도는 O(n+e)이다.
음 주어진 노느들이 연결 되어 있는지 아닌지 확인하는 문제이다.
이와 비슷한 문제가 그래프의 연결 요소(connected component)들을 나열하는 문제라 한다.

아무래도 완전 탐색이므로 dfs,bfs 무엇을 사용하던 시간 복잡도는 동일한거 같다.

6.2.4 신장 트리 (spanning tree)

그래프 G가 있을때 신장 트리란 G의 간선들로만 구성되고 모든 G의 정점들을 연결하는 트리다.
즉 모든 간선들중에서 그래프가 정점들을 갖도로 유지한채 일부 간선만 제거한 느낌인거 같다.

새로운 신장 트리는 dfs,bfs 둘 모두로 생성할 수 있다함. depth first spanning tree, breath first spanning tree라고 한다.

음 이 부분은 정확히 어떤 의미를 갖는지 모르겠는데 신장 트리에 임의의 간선을 추가하면 사이클이 형성된다 한다. 이런 신장 트리의 특성이 전기 네트워크에서 회로 등식의 독립적인 집합을 수하는데 활용될 수 있다...라고....

음 최소 부분 그래프인 신장트리는 도시 통신 네트워크 설계등에 사용된다 한다. 근데 이때는 가중치가 있으므로 다음 절에서 최소 비용 신장 트리를 구하는 방법을 알아보자고~

6.2.5 이중 결합 요소 biconnected component

이 부분은 지금 단계에서는 too much인거 같다
대회 알고리즘인듯 하다. 나중에 필요할때 공부하자.
https://m.blog.naver.com/PostView.nhn?blogId=kks227&logNo=220802704686&proxyReferer=https%3A%2F%2Fwww.google.com%2F

6.3 최소 비용 신장 트리

가중치가 부여된 무방향 그래프의 신장 트리의 비용이 최저가 되는 신장 트리가 최소 비용 신장 트리이다. 이를 위한 알고리즘은 Prim, Kruskal, Sollin 세가지가 있다. 셋 모두 greedy algorithm을 사용한다.

호로비츠 책에 의하면 그리디 알고리즘은 최적의 해법을 단계 별로 구한다. 각 단계에서는 몇 개의 판단 기준에 따라 최상의 결과를 내린다. 일단 내려진 결정은 번복이 불가능하므로, 각각의 결정이 가능한 해를 도출해낼 수 있는지 확인해야 한다.
최소 비용 신장 트리에서는 최저 비용이 각 단계의 기준이다.

그리고 다음 세 제한 조건을 만족해야 한다 하는데 읽어보니 뭔가 알고리즘에 대한 구상이 잘되서 적어보겠다.

1) 그래프 내에 있는 간선들만을 사용해야 한다.
2) 정확하게 n-1개의 간선만을 사용해야 한다.
3) 사이클을 생성하는 간선을 사용해선 안 된다.

크루스칼 알고리즘

일단 내가 설명해 보겠다.

크루스칼 알고리즘은 최소 비용의 간선을 찾아 추가하는 방식으로 진행된다. 단 선택한 간선이 사이클을 형성하지 않도록 해야한다. 이것과 관련해서 나는 알고리즘으로 구현할때 priority queue를 사용하여 최소 비용의 간선을 찾도록 했다. 이것에 대한 시간 복잡도는 음 우선 순위 큐 형성 시간일텐데 잘모르겠다. 그리고 사이클에 대한 확인은 잘 기억안난다. ㅋㅋ 왜 맨날 해본것도 까먹지

-> 한거 까먹은거 같아서 어제 5장 정리한 부분 다시 찾아 보았다. 우선 순위 큐는 min heap, max heap으로 구성된다.... 즉 내가 한 힙의 구성 시간은 그냥 맨 마지막 노드에 넣으면 되서어 음 오장에 가서 힙의 삽입과 삭제 코드좀 작성해 보아야 겠다.

이제 호로비츠
min heap을 이용하면 힙 구성에 O(n)이 최저 비용 탐색에 O(logE)가 소요된다. 정렬하는 방법도 있다한다. O(logE)
음 둘중에 뭐가 더 빠를까! -> 생각해볼 만한듯. 느낌으로는 min heap이 더 빠른거 같다.

그리고 이제 사이클에 대한 확인은 union find를 사용한다 함 -> 유용한듯...

프림 알고리즘

크루스칼은 포리스트를 이루면서 완성되었다. 이번에 프림은 트리를 이루면서 완성된다.
과정은 임의 한 노드부터 시작해서 연결된 노드들 중에 최소 비용의 간선을 선택한다. 그리고 간선에 연결된 노드를 트리 집합 T에 포함 시킨다. 각 단계에서 간선을 선택할때 반대쪽 노드가 T에 속하지 않은 것을 선택함으로서 사이클을 형성하지 않도록 한다.
시간 복잡도는 음 O(n^2)이라 한다. 아마 음 왜그러지...
찾아보니 외부 반복문이 모든 정점을 돌고 내부 반복문도 정점들을 돌면서 T에 속하지 않은 것 중에 최소 비용인 것을 선택하니 그런듯 하다.
프림을 _fibonacci_를 구현하면 점진적으로 더 빠르게 구현 가능하다고 한다. 9장... 꼭 보자!

Sollin 알고리즘

잠시 보류~

6.4 최단 경로와 이행적 폐쇠

이런 문제를 풀기 위한 절이라 한다.

1. X에서 Y로 가는 길이 있는가?
2. X로부터 Y로 가는 길이 2개 이상이라면, 어느 길이 최단 인가?

이 문제는 결국 길찾기 문제인 셈인데 위에 최소 비용 신장 트리는 네트워크 형성하는 문제라고 보면 될거 같다.

[최단 경로 다른 문제들] https://ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/

위의 두개는 각각 단일 출발 최단 경로 문제, 단일 쌍 최단 경로 문제이다.
다른 두개로 단일 도착 최단 경로(단일 출발 최단 경로 문제 거꾸로), 전체 쌍 최단 경로 문제가 있다.

다익스트라 벨만-포드는 단일 출발 최단 경로 문제를 푸는데 적합한데, 좀 더 응용하면 나머지 3개도 풀 수 있다 하심...

6.4.1 하나의 출발점/모든 목표점 : 음이 아닌 간선 비용

이 경우는 가중치가 모두 0이상인 경우이다!

어쨋든 최단 경로는 dijkstra 알고리즘을 구현하면 된다 한다.

일단 내가 기억나는 다익스트라 알고리즘은
출발점 u로 부터 모든 노드까지의 비용을 cost[]에 저장한다. 처음에는 매우 큰 값으로 한다. 아직 비용 계산전이니까
그렇다면 현재 노드로부터 연결되 있는 지점들의 cost를 간선 가중치 w + cost[u]로 구해서 갱신한다. 이제 다시 cost들 중에 최소 비용인 노드를 구한다.그리고 이 지점에서 다시 위에 처럼 반복한다. 음 언제 끝나냐면 모든 지점을 방문했으면 끝난다.
이 횟수가 n-1번으로 고정되어 있다 볼 수 있다.

시간복잡도가 O(n^2)이라 하는데 피보나치 힙을 이용하면 좀더 효율적으로 구할 수 있다 한다.

6.4.2 하나의 출발점/모든 목표점 : 일반적 가중치

이 경우는 가중치가 음수일 수 도 있는 경우이다.

벨만 포드 알고리즘을 사용한다.

아래의 링크를 참고하자
[bellman ford] https://ratsgo.github.io/data%20structure&algorithm/2017/11/27/bellmanford/
[optimal substructure] https://ratsgo.github.io/data%20structure&algorithm/2017/11/25/shortestpath/

optimal substructure는 최단 경로의 부분 경로는 역시 최단 경로라는 내용인데, 다익스트라를 이해하는데 도움이 많이 되는거 같다.

사실 위의 블로그랑 호로비츠를 보고 이해가 안되서
[bellman ford 절차] https://leeyongjeon.tistory.com/entry/%EB%B2%A8%EB%A8%BC%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98BellmanFord-algorithm

이 블로그를 보니 이 분이 동작 원리라고

1. 시작점을 제외한 모든 점의 거리를 무한으로 초기화 한다.(시작점은 0)
2. 모든 점의 수 만큼 반복적으로 가중치가 있는 선분을 검사한다. -> 여기서 시간 복잡도가 인접 리스트의 경우 O(VE)인듯 하다.
3. 갱신 가능한 거리가 있으면 최단 거리를 갱신한다. 처음 올린 블로그에서 edge relaxing 이라 하는 기법 ㅋㅋ
4. 음수 싸이클이 있는지 검사하고 검사 결과를 반환 한다. ->이 말은 이해가 안된다.

*일단 사이클이 안 생기려면 간선이 노드수가 V이면 V-1이여야 한다. V번
음 즉 모든 정점에 대한 모든 간선의 edge relaxing을 하는데 그 횟수가 V-1번 더하는 거 같다. 시간 복잡도가 음 뭐지..
인접 리스트를 기준으로 생각하면 *

[bellman ford] https://codemcd.github.io/algorithm/Algorithm-%EB%B2%A8%EB%A7%8C-%ED%8F%AC%EB%93%9C-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

여기가 더 이해 잘되서 이걸 정리해 보겠다.

작동 원리

벨만-포드 알고리즘은 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤, 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식으로 동작한다.

그래서 벨만포드는 upper[u] 즉 시작점에서 u까지의 상한을 계속해서 갱신하면서 최단거리에 도달하게 한다.

음수 사이클 판정

벨만 포드에 음수 사이클이 있으면 무한히 거리가 작아져서 의미 없는 값을 반환한다.
완화 과정은 최단 경로를 V-1번 수행하면 찾을 수 있지만 음수 사이클이 존재 한다면 그 이상 수행해도 거리가 줄어들어 완화가 진행될 것이다. 따라서 벨만 포드는 V번동안 모든 간선에 대해 완화 과정을 수행한다. ??
모든 정점에 대한 모든 간선을 edge relaxing하면 된다 음 근데 *V번 하는건 이해되는데 왜 V-1번인지는 모르겠다 ㅋㅋ 그냥 한번만 갱신하면 안되나... 추측에는 사이클이 있으면 몇번 더 해줘야 계산되서 그런거 같은데 한번 혼자 해보자
-> 이 부분 V번 하는건 모든 노드들을 출발점으로 E번 만큼 edge relaxing 하면 된다