免费视频淫片aa毛片_日韩高清在线亚洲专区vr_日韩大片免费观看视频播放_亚洲欧美国产精品完整版

　　帶權(quán)圖分為有向和無(wú)向，無(wú)向圖的最短路徑又叫做最小生成樹(shù)，有prime算法和kruskal算法；有向圖的最短路徑算法有dijkstra算法和floyd算法。

　　生成樹(shù)的概念：聯(lián)通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹(shù)，則該子圖稱(chēng)為G的生成樹(shù) 生成樹(shù)是聯(lián)通圖的極小連通子圖。所謂極小是指：若在樹(shù)中任意增加一條邊，則 將出現(xiàn)一個(gè)回路；若去掉一條邊，將會(huì)使之編程非連通圖。生成樹(shù)各邊的權(quán) 值總和稱(chēng)為生成素的權(quán)。權(quán)最小的生成樹(shù)稱(chēng)為最小生成樹(shù)，常用的算法有prime算法和kruskal算法。

　　最短路徑問(wèn)題旨在尋找圖中兩節(jié)點(diǎn)之間的最短路徑，常用的算法有：floyd算法和dijkstra算法。

　　構(gòu)造最小生成樹(shù)一般使用貪心策略，有prime算法和kruskal算法

　　prime算法的基本思想

1.清空生成樹(shù)，任取一個(gè)頂點(diǎn)加入生成樹(shù)

2.在那些一個(gè)端點(diǎn)在生成樹(shù)里，另一個(gè)端點(diǎn)不在生成樹(shù)里的邊中，選取一條權(quán)最小的邊，將它和另一個(gè)端點(diǎn)加進(jìn)生成樹(shù)

3.重復(fù)步驟2，直到所有的頂點(diǎn)都進(jìn)入了生成樹(shù)為止，此時(shí)的生成樹(shù)就是最小生成樹(shù)

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 = 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算法：構(gòu)造一個(gè)只含n個(gè)頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個(gè)頂點(diǎn)看成是各棵樹(shù)的根節(jié)點(diǎn)，則它是一個(gè)含有n棵樹(shù)的森林 。之后，從網(wǎng)的邊集中選取一條權(quán)值最小的邊，若該邊的兩個(gè)頂點(diǎn)分屬不同的樹(shù) ，則將其加入子圖，也就是這兩個(gè)頂點(diǎn)分別所在的 兩棵樹(shù)合成一棵樹(shù)；反之，若該邊的兩個(gè)頂點(diǎn)已落在同一棵樹(shù)上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類(lèi)推，直至森林只有一棵樹(shù)。kruskal算法能夠在并查集的基礎(chǔ)很快的實(shí)現(xiàn)。結(jié)合例子來(lái)介紹具體算法實(shí)現(xiàn)（其中并查集的部分可以詳見(jiàn)并查集介紹部分） http://poj.org/problem?id=1251 

View Code

#include
#include
using namespace std;

const int size = 128;
int n;
int father[size];
int rank[size];

//把每條邊成為一個(gè)結(jié)構(gòu)體，包括起點(diǎn)、終點(diǎn)和權(quán)值
typedef struct node
{
int val;
int start;
int end;
}edge[SIZE * SIZE / 2];

//把每個(gè)元素初始化為一個(gè)集合
void make_set()
{
for(int i = 0; i < n;="" i="">
father[i] = i;
rank[i] = 1;
}
return ;
}

//查找一個(gè)元素所在的集合,即找到祖先
int find_set(int x)
{
if(x != father[x]){
father[x] = find_set(father[x]);
}
return father[x];
}

//合并x,y所在的兩個(gè)集合：利用Find_Set找到其中兩個(gè)
//集合的祖先，將一個(gè)集合的祖先指向另一個(gè)集合的祖先。
void Union(int x, int y)
{
x = find_set(x);
y = find_set(y);
if(x == y){
return ;
}
if(rank[x] <>
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為邊的數(shù)量
{
int sum = 0;
make_set();
for(int i = 0; i < n;="" i="" ++){="">//從權(quán)最小的邊開(kāi)始加進(jìn)圖中
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); //對(duì)邊按權(quán)從小到大排序
cout < kruskal(cnt)="">< endl;="">
}
}

　　最短路徑問(wèn)題旨在尋找圖中兩節(jié)點(diǎn)之間的最短路徑，常用的算法有：floyd算法和dijkstra算法。

　　floyd算法是最簡(jiǎn)單的最短路徑算法，可以計(jì)算圖中任意兩點(diǎn)間的最短路徑  folyd算法的時(shí)間復(fù)雜度是O(N3),如果是一個(gè)沒(méi)有邊權(quán)的圖，把相連的兩點(diǎn)  間的距離設(shè)為dist[i][j] = 1，不相連的兩點(diǎn)設(shè)為無(wú)窮大，用 floyd算法可以判斷i,j兩點(diǎn)是否有路徑相連。

View Code

void floyd()
{
for(int k = 0; k < n;="" k="" ++){="">//作為循環(huán)中間點(diǎn)的k必須放在最外一層循環(huán)
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(luò)的最短路徑
}
}
}
}
}

　　dijkstra算法用來(lái)計(jì)算從一個(gè)點(diǎn)到其他所有點(diǎn)的最短路徑的算法，復(fù)雜度O(N2)。

View Code

void dijkstra(int s) //s是起點(diǎn){ 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]; } } }}