기초 도 론 문제 알고리즘 총화
136020 단어 최소 생 성 트 리도 론최 단 로
1. 인접 표 저장 도 는 인접 행렬 로 희소 도 를 표시 하면 대량의 메모리 공간 을 낭비 할 수 있다.인접 표 에 서 는 '정점 0 에서 출발 하여 정점 1, 2, 3, 4 까지' 와 같은 정 보 를 링크 에 저장 하여 그림 을 나타 낸다.이렇게 하면 O (| V | + | E |) 의 메모리 공간 만 필요 합 니 다.
- #include <cstdio>
- #include <vector>
- std::vector<int> g[max_v];
- /**
- *
- *sturct edge{
- * int to, cost;
- *};
- *std::vector<edge> g[max_v];
- */
- int main(void)
- {
- int v, e;
- scanf("%d%d", &v, &e);
- for(int i = 0; i != e; ++i){
- int s, t;
- scanf("%d%d", &s, &t);
- g[s].push_back(t);
- //g[t].push_back(s);//
- }
- return 0;
- }
2. 최 단 로 문제 1. Bellman - ford 구 단원 최 단 로 기 는 출발점 s 에서 정점 i 까지 의 최 단 거 리 는 d [i] 이 고 d [i] = min {d [j] + (j 에서 i 까지 의 가중치) | e = (j, i) 8712 ° E} 이 있 습 니 다.그림 에 동그라미 가 있 는 경우 d [s] = 0, d [i] = INF 는 제 한 된 횟수 내 에 새로운 d 를 계산 할 수 있다.s 에서 도달 할 수 있 는 음 권 이 존재 하지 않 는 다 면 | V | - 1 회 순환 후 for (;) 는 break 이 므 로 복잡 도 는 O (| V |× |E|)。즉, 마이너스 코일 이 존재 하면 제 | V | 차 순환 에서 도 d 값 이 업데이트 되 며, 이 성질 을 이용 하여 마이너스 코일 이 존재 하 는 지 확인 할 수 있다.
- struct edge{
- int from;
- int to;
- int cost;
- };
- edge es[max_e];
- int d[max_v];
- int v, e;
- // s
- void bellman_ford(int s)
- {
- for(int i = 0; i != v; ++i)
- d[i] = INF;//
- d[s] = 0;
- for(;;){
- bool update = false;
- for(int i = 0; i != e; ++i){
- edge e = es[i];
- if(d[e.from] != INF && d[e.to] > d[e.from] + e.cost){
- d[e.to] = d[e.from] + e.cost;
- update = true;
- }
- }
- if(!update)
- break;
- }
- }
- // ，
- bool find_negative_loop(void)
- {
- memset(d, 0, sizeof(d));
- for(int i = 0; i != v; ++i){
- for(int j = 0; j != e; ++j){
- edge e = es[j];
- if(d[e.to] > d[e.from] + e.cost){
- d[e.to] = d[e.from] + e.cost;
- // n
- if(i == v - 1)
- return true;
- }
- }
- }
- return false;
- }
2. Dijkstra 는 마이너스 가 없 는 단원 의 최 단 로 설명 을 구한다. ① 최 단 거리 가 확 정 된 정점 을 찾 아 이웃 정점 의 최 단 거 리 를 업데이트 한 다음 에 '최 단 거리 가 확 정 된 정점' 에 더 이상 관심 을 가 질 필요 가 없다.어떻게 '최 단 거리 가 이미 확 정 된 정점' 을 얻 습 니까?시작 할 때 출발점 까지 의 최 단 거리 만 확정 된다.아직 사용 되 지 않 은 정점 에서 d [i] 에서 가장 작은 정점 은 가장 짧 은 거리 에서 이미 확 정 된 정점 이다.다음은 시간 복잡 도 를 O (| V |²)인접 행렬 로 이 루어 진 Dijkstra 알고리즘 을 사용 합 니 다.
- template <typename t>
- inline t min(t a, t b)
- {
- return a < b ? a : b;
- }
- int cost[max_v][max_v];//
- int d[max_v];//
- bool used[max_v];//
- int v;//
- void Dijkstra(int s)
- {
- for(int i = 0; i != v; ++i)
- d[i] = INF;
- for(int i = 0; i != v; ++i)
- used[i] = false;
- d[s] = 0;
- for(;;){
- int v = -1;
- //
- for(int u = 0; u != v; ++u)
- if(!used[u] && (v == -1 || d[u] < d[v]))
- v = u;
- if(-1 == v)
- break;
- for(int u = 0; u != v; ++u)
- d[u] = min(d[u], d[v] + cost[v][u]);
- }
- }
인접 표를 사용 할 때 가장 짧 은 거 리 를 업데이트 하려 면 각 변 에 한 번 만 접근 해 야 하기 때문에 이 부분의 복잡 도 는 O (| E |) 입 니 다.그러나 정점 을 찾 으 려 면 한 번 씩 매 거 져 야 합 니 다. 결국 복잡 도 는 제곱 입 니 다. C + STL 의 우선 대기 열 priority quue 를 사용 하여 이 루어 집 니 다. 업데이트 할 때마다 현재 최 단 거리 와 정점 값 을 더미 에 삽입 합 니 다. 최소 값 이 최 단 거리 가 아니라면 버 립 니 다. 이러한 알고리즘 은 O (| E | log | V |) 로 복잡 도가 최적화 되 었 습 니 다.. Dijkstra 는 Bellman - ford 보다 효율 이 높 지만 마이너스 가 존재 하 는 그림 에 적용 할 수 없습니다.
- #include <queue>
- #include <vector>
- #include <utility>
- struct edge{
- int to;
- int cost;
- };
- typedef std::pair<int, int> P;//first , second
- int v;
- std::vector<edge> g[max_v];
- int d[max_v];
- void Dijkstra(int s)
- {
- std::priority_queue<P, std::vector<P>, std::greater<P> > que;
- for(int i = 0; i != v; ++i)
- d[i] = INF;
- d[s] = 0;
- que.push(P(0, s));
- while(!que.empty()){
- P p = que.top();
- que.pop();
- int v = p.second;
- if(d[v] < p.first)
- continue;
- for(unsigned int i = 0; i != g[v].size(); ++i){
- edge e = g[v][i];
- if(d[e.to] > d[v] + e.cost){
- d[e.to] = d[v] + e.cost;
- que.push(P(d[e.to], e.to));
- }
- }
- }
- }
3. 여러 그림 에서 임의의 두 점 사이 의 거 리 를 구 하 는 데 적용 되 는 Floyd - Warshall 코드 는 매우 짧 고 매우 효과 적 이 며 원 리 를 설명 하지 않 습 니 다. 마이너스 권 이 있 는 지 판단 하 는 데 도 사 용 됩 니 다. d [i] [i] 가 있 는 지 확인 하 는 것 은 마이너스 입 니 다. 복잡 도: O (| V | ^ 3).
- template <typename t>
- inline t min(t a, t b)
- {
- return a < b ? a : b;
- }
- int d[max_v][max_v];
- int v;
- void Floyd_Warshall(void)
- {
- for(int k = 0; k != v; ++k)
- for(int i = 0; i != v; ++i)
- for(int j = 0; j != v; ++j)
- d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
- }
3. 최소 생 성 트 리 문제²)。
- template <typename t>
- inline t min(t a, t b)
- {
- return a < b ? a : b;
- }
- int cost[max_v][max_v];
- int mincost[max_v];// X
- bool used[max_v] ;// i X
- int v;
- int Prim(void)
- {
- for(int i = 0; i != v; ++i){
- mincost[i] = INF;
- used[i] = false;
- }
- mincost[0] = 0;
- int res = 0;
- for(;;){
- int v = -1;
- // X X
- for(int u = 0; u != v; ++u)
- if(!used[u] && (v == -1 || mincost[u] < mincost[v]))
- v = u;
- if(-1 == v)
- break;
- used[v] = true;// v X
- res += mincost[v];//
- for(int u = 0; u != v; ++u)
- mincost[u] = min(mincost[u], cost[v][u]);
- }
- return res;
- }
2. 인접 표 에 사용 할 Kruskal 은 변 의 가중치 순 으로 작은 것 부터 큰 것 까지 한 번 봅 니 다 (정렬 필요)원 이나 무 거 운 테 두 리 를 만 들 지 않 으 면 이 테 두 리 를 생 성 트 리 에 넣 습 니 다. 원 생 성 여 부 를 어떻게 판단 합 니까? u 와 v 를 연결 하 는 테 두 리 를 생 성 트 리 에 넣 으 려 면 그 전에 u 와 v 가 같은 연결 분량 에 있 지 않 으 면 e 를 넣 으 면 원 이 생기 지 않 습 니 다. 있 으 면 반드시 원 이 생 성 됩 니 다. 집합 을 도입 하고 찾 으 면 됩 니 다. 그리고 그 실현 은 코드 팩 에 포함 되 어 있 습 니 다. Kruskal가장 오래 걸 리 는 동작 은 변 에 대한 정렬 입 니 다. 시간 복잡 도: O (| E | log | V |).
- #include <algorithm>
- #include "Union_Find.cpp"
- struct edge{
- int u, v, cost;
- };
- bool comp(const edge &a, const edge &b)
- {
- return a.cost < b.cost;
- }
- edge es[max_e];
- int v, e;
- int Kruskal(void)
- {
- std::sort(es, es + e, comp);
- init(v);//
- int res = 0;
- for(int i = 0; i != e; ++i){
- edge e = es[i];
- if(!same(e.u, e.v)){
- unite(e.u, e.v);
- res += e.cost;
- }
- }
- return res;
- }
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 1875 는 최소 생 성 트 리 입 니 다.그들 이 다른 작은 섬 에 가 고 싶 을 때 작은 배 를 저어 이 루어 져 야 합 니 다.현재 정 부 는 백도 호 를 대대적으로 발전 시 키 기로 결정 했다. 조건 에 맞 는 다 는 것 은 작은 섬 2 곳 사이 의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
