最小生成樹prime演算法、kruskal演算法 最短路徑演算法floyd、dijkstra

帶權圖分為有向和無向，無向圖的最短路徑又叫做最小生成樹，有prime演算法和kruskal演算法；有向圖的最短路徑演算法有dijkstra演算法和floyd演算法。

生成樹的概念：聯通圖G的一個子圖如果是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹 生成樹是聯通圖的極小連通子圖。所謂極小是指：若在樹中任意增加一條邊，則 將出現一個迴路；若去掉一條邊，將會使之編程非連通圖。生成樹各邊的權 值總和稱為生成素的權。權最小的生成樹稱為最小生成樹，常用的演算法有prime演算法和kruskal演算法。

最短路徑問題旨在尋找圖中兩節點之間的最短路徑，常用的演算法有：floyd演算法和dijkstra演算法。

構造最小生成樹一般使用貪心策略，有prime演算法和kruskal演算法

prime演算法的基本思想

1.清空生成樹，任取一個頂點加入生成樹

2.在那些一個端點在生成樹里，另一個端點不在生成樹里的邊中，選取一條權最小的邊，將它和另一個端點加進生成樹

3.重複步驟2，直到所有的頂點都進入了生成樹為止，此時的生成樹就是最小生成樹

View Code

int prime(int cur)

{

int index;

int sum = 0;

memset(visit, false, sizeof(visit));

visit[cur] = true;

for(int i = 0; i < m; i ++){

dist[i] = graph[cur][i];

}

for(int i = 1; i < m; i ++){

int mincost = INF;

for(int j = 0; j < m; j ++){

if(!visit[j] && dist[j] < mincost){

mincost = dist[j];

index = j;

}

}

visit[index] = true;

sum += mincost;

for(int j = 0; j < m; j ++){

if(!visit[j] && dist[j] > graph[index][j]){

dist[j] = graph[index][j];

}

}

}

return sum;

}

kruskal演算法：構造一個只含n個頂點，而邊集為空的子圖，若將該子圖中各個頂點看成是各棵樹的根節點，則它是一個含有n棵樹的森林 。之後，從網的邊集中選取一條權值最小的邊，若該邊的兩個頂點分屬不同的樹 ，則將其加入子圖，也就是這兩個頂點分別所在的 兩棵樹合成一棵樹；反之，若該邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直至森林只有一棵樹。kruskal演算法能夠在並查集的基礎很快的實現。結合例子來介紹具體演算法實現（其中並查集的部分可以詳見並查集介紹部分） http://poj.org/problem?id=1251

View Code

#include<iostream>

#include<algorithm>

using namespace std;

const int size = 128;

int n;

int father[size];

int rank[size];

//把每條邊成為一個結構體，包括起點、終點和權值

typedef struct node

{

int val;

int start;

int end;

}edge[SIZE * SIZE / 2];

//把每個元素初始化為一個集合

void make_set()

{

for(int i = 0; i < n; i ++){

father[i] = i;

rank[i] = 1;

}

return ;

}

//查找一個元素所在的集合,即找到祖先

int find_set(int x)

{

if(x != father[x]){

father[x] = find_set(father[x]);

}

return father[x];

}

//合併x,y所在的兩個集合：利用Find_Set找到其中兩個

//集合的祖先，將一個集合的祖先指向另一個集合的祖先。

void Union(int x, int y)

{

x = find_set(x);

y = find_set(y);

if(x == y){

return ;

}

if(rank[x] < rank[y]){

father[x] = find_set(y);

}

else{

if(rank[x] == rank[y]){

rank[x] ++;

}

father[y] = find_set(x);

}

return ;

}

bool cmp(pnode a, pnode b)

{

return a.val < b.val;

}

int kruskal(int n) //n為邊的數量

{

int sum = 0;

make_set();

for(int i = 0; i < n; i ++){ //從權最小的邊開始加進圖中

if(find_set(edge[i].start) != find_set(edge[i].end)){

Union(edge[i].start, edge[i].end);

sum += edge[i].val;

}

}

return sum;

}

int main()

{

while(1){

scanf("%d", &n);

if(n == 0){

break;

}

char x, y;

int m, weight;

int cnt = 0;

for(int i = 0; i < n - 1; i ++){

cin >> x >> m;

//scanf("%c %d", &x, &m);

//printf("%c %d ", x, m);

for(int j = 0; j < m; j ++){

cin >> y >> weight;

//scanf("%c %d", &y, &weight);

//printf("%c %d ", y, weight);

edge[cnt].start = x - "A";

edge[cnt].end = y - "A";

edge[cnt].val = weight;

cnt ++;

}

}

sort(edge, edge + cnt, cmp); //對邊按權從小到大排序

cout << kruskal(cnt) << endl;

}

}

最短路徑問題旨在尋找圖中兩節點之間的最短路徑，常用的演算法有：floyd演算法和dijkstra演算法。

floyd演算法是最簡單的最短路徑演算法，可以計算圖中任意兩點間的最短路徑 folyd演算法的時間複雜度是O(N3),如果是一個沒有邊權的圖，把相連的兩點 間的距離設為dist[i][j] = 1，不相連的兩點設為無窮大，用 floyd演算法可以判斷i,j兩點是否有路徑相連。

View Code

void floyd()

{

for(int k = 0; k < n; k ++){ //作為循環中間點的k必須放在最外一層循環

for(int i = 0; i < n; i ++){

for(int j = 0; j < n; j ++){

if(dist[i][j] > dist[i][k] + dist[k][j]){

dist[i][j] = dist[i][k] + dist[k][j]; //dist[i][j]得出的是i到j的最短路徑

}

}

}

}

}

dijkstra演算法用來計算從一個點到其他所有點的最短路徑的演算法，複雜度O(N2)。

View Code

void dijkstra(int s) //s是起點

{

memset(visit, false, sizeof(visit));

visit[s] = true;

for(int i = 0; i < n; i ++){

dist[i] = graph[s][i];

}

int index;

for(int i = 1; i < n; i ++){

int mincost = INF;

for(int j = 0; j < n; j ++){

if(!visit[j] && dist[j] < mincost){

mincost = dist[j];

index = j;

}

}

visit[index] = true;

for(int j = 0; j < n; j ++){

if(!visit[j] && dist[j] > dist[index] + graph[index][j]){

dist[j] = dist[index] + graph[index][j];

}

}

}

}

void dijkstra(int s) //s是起點

{

memset(visit, false, sizeof(visit));

for(int i = 0; i < n; i ++){

dist[i] = INF;

}

visit[s] = true;

dist[s] = 0;

int index;

for(int i = 1; i < n; i ++){

int mincost = INF;

for(int j = 0; j < n; j ++){

if(!visit[j] && dist[j] < mincost){

mincost = dist[j];

index = j;

}

}

visit[index] = true;

for(int j = 0; j < n; j ++){

if(!visit[j] && dist[j] > dist[index] + graph[index][j]){

dist[j] = dist[index] + graph[index][j];

}

}

}

}

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！