1、最小生成樹Prim算法和單源最短路徑Dijkstra算法問題：(最小生成樹)給定一個帶權(quán)的無向連通圖，如何選取一棵生成樹， 使樹上所有邊上權(quán)的總和為最小，即求最小生成樹。(單源最短路徑)給定一個權(quán)值都為正數(shù)的無向連通圖和一個源點， 確定它到其它點的最短距離。之所以將這兩個問題放在一起，是因為Prim算法與Dijkstra算法的思 路和程序都非常相似，都是有貪心策略。1.解法(Prim算法)：思路：設(shè)連通網(wǎng)絡(luò)N = V, E ，U表示已加入到生成樹的頂點集合。在初始化階段，任取一個頂點，用其關(guān)聯(lián)邊的權(quán)值作為初始的V-U頂點 集合的數(shù)據(jù)。在每一步中，先在V-U頂點集合中選擇距離U中任意點“最 近”

2、的頂點v，再把v加入到。中，最后看看在新的V-U頂點集合中， 是否有哪個頂點距離v比距離U中其它點更近，若有則更新V-U頂點 集合中的數(shù)據(jù)。U的元素個數(shù)為V-1,所以共要進(jìn)行V-1步?？偟臅r間復(fù)雜度為Time =O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY若用數(shù)組作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)，T_EXTRACT-MIN用時O(V)，T_DECREASE-KEY 用時 0(1)，總共用時 O(VA2)若用最小堆作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)，T_EXTRACT-MIN用時O(lgV),T_DECREASE-KEY 用時 O(lgV)，總共用時 O(V+E)*lgV)若用斐波那契

3、堆作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)，T_EXTRACT-MIN平均用時O(lgV), T_DECREASE-KEY 平均用時 O(1)，總共用時 O(E+V*lgV)下面的代碼使用數(shù)組作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)：cpp view plaincopy#include #include algorithmusing namespace std;4.#define MAXN 1001#define INF 10000007.int lowcostMAXN; /距離U中頂點的最小權(quán)值bool visitedMAXN; /若為true表示巳加入到集合U中int mstMAXN; /距離U中哪個頂點最短int grap

4、hMAXNMAXN; /用矩陣表示圖上各邊權(quán)值12.void Prim(int n)int i, j;memset(visited,0,n*sizeof(bool);visited0 =true;mst0 = -1;for (i=1; in; i+) TOC o 1-5 h z lowcosti = graph0i;msti = 0;for (i=1; i=n-1; i+)/ 取 V-U 中的最小權(quán)值T_EXTRACT-MIN O(V)intmin=INF, minid;for (j=1; jn; j+)/用visited數(shù)組確定V-Uif (!visitedj & lowcostj min)

5、min = lowcostj;minid = j;34.35.visitedminid = true;36./ 減小 V-U 中的權(quán)值 T_DECREASE-KEY O(1)37.for (j=1; j graphminidj)39.40.lowcostj = graphminidj;41.mstj = minid;42.43.44. 45.46. intmain()47. 48.int n, m, i, j;49.cin n m;50.for (i=0; in; i+)51.for (j=0; jn; j+)52.graphij = INF;53.for (i=0; im; i+)54.55

6、.char a3, b3;56.int c;57.scanf(%s %s %d”,&a, &b, &c);58.grapha0-Ab0-A = c;59.graphb0-Aa0-A = c;60.61.Prim(n);62.int total = 0;63.for (i=1; in; i+)64.65.total += lowcosti;66.printf(%c-%c: %dn, i+A, msti+A, lowcosti)67.68.printf(%dn, total);69. 2.解法（Dijkstra 算法）：思路：設(shè)連通網(wǎng)絡(luò)N = V, E 和給定源點u, U表示已確定最短路徑的 頂點

7、集合。在初始化階段，用頂點u所關(guān)聯(lián)邊的權(quán)值作為初始的V-U頂點集合的數(shù)據(jù)。在每一步中，先在V-U頂點集合中選擇距離源點u“最 近”的頂點v,再把v加入到。中，最后看看在新的V-U頂點集合中， 是否有哪個頂點通過頂點v到達(dá)源點u比通過U中其它點到達(dá)距離更 短，若有則更新V-U頂點集合中的數(shù)據(jù)。U的元素個數(shù)為V-1,所以共 要進(jìn)行V-1步?？偟臅r間復(fù)雜度為Time =O(V)*T_EXTRACT-MIN+O(E)*T_DECREASE-KEY若用數(shù)組作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)，T_EXTRACT-MIN用時O(V)， T_DECREASE-KEY 用時 0(1)，總共用時 O(VA2)若用最小堆作為頂

8、點權(quán)值的數(shù)據(jù)結(jié)構(gòu)，T_EXTRACT-MIN用時O(lgV)， T_DECREASE-KEY 用時 O(lgV)，總共用時 O(V+E)*lgV)若用斐波那契堆作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)，T_EXTRACT-MIN平均用時 O(lgV)，T_DECREASE-KEY 平均用時 O(1)，總共用時 O(E+V*lgV) 下面的代碼使用數(shù)組作為頂點權(quán)值的數(shù)據(jù)結(jié)構(gòu)： cpp view plaincopy#include #include algorithm3.using namespace std;5.#define MAXN 1001#define INF 10000008.int lowcostMA

9、XN; /距離源點u的最短距離bool visitedMAXN; /若為true表示巳加入到集合U中int minroadMAXN; /在最短路徑上頂點所連接的前一個頂點int graphMAXNMAXN; /用矩陣表示圖上各邊權(quán)值13.void Dijkstra(int n)15. 7.memset(visited, 0, n*sizeof

10、(bool);visited0 = true;minroad0 = -1;for (i=1; in; i+)lowcosti = graph0i;minroadi = 0;for (i=1; i=n-1; i+)/ 取 V-U 中的最小權(quán)值 T_EXTRACT-MIN O(V)int min=INF, minid;for (j=1; jn; j+)/用visited數(shù)組確定V-Uif (!visitedj & lowcostj min) min = lowcostj;minid = j;visitedminid = true;/ 減小 V-U 中的權(quán)值 T_DECREASE-KEY O(1)for (j=1; j lowcostminid+graphminidj)lowcostj = lowcostminid+graphminidj;minroadj = minid;int main()int n, m, i, j;cin n m;for (i=0; in; i+)for (j=0; jn; j+)graphij = INF;for (i=0; im; i+)char a3, b3;int c;58.scanf(%s %s %d”,&a,59.grapha0-Ab060.graphb0-Aa061.62.Dijkstra(n);63.in