• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>

    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>

            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            

    
            

            




            







												


        


            
	
            
		
			

            

            
	
            
		
			
            lzm
            
			who dare win.
		            		
	
            

            

            

            

            posts - 14, comments - 29, trackbacks - 0, articles - 0
            


            		
	
            
	
            
		
			
		
		
			
            
				
					
	
            
		
            
			
            
				Prim算法
			
            
 			Posted on 2009-04-10 19:11 lzmagic 閱讀(4367) 評(píng)論(1)  編輯 收藏 引用  所屬分類: Algorithm 
			
			


		
            
		
            /**
             * PRIM(簡(jiǎn)單版) 最小生成樹(shù)算法 (Minimum Spanning Tree) 
             * 輸入：圖g；                 // 有向圖或者無(wú)向圖 
             * 輸出：(1)最小生成樹(shù)長(zhǎng)sum； 
             *         (2)最小生成樹(shù)prev。
             * 結(jié)構(gòu): 圖g用鄰接矩陣表示，最短邊長(zhǎng)dist用數(shù)組表示。 
             * 算法：Prim算法  
             * 復(fù)雜度：O(|V|^2) 
                         */             
            #include             <iostream>
            #include             <vector>
            #include             <list>
            #include             <iterator>
            #include             <algorithm>
            #include             <numeric>
            #include             <functional>
            #include             <climits>
            using namespace std;

            int n;                    // n : 頂點(diǎn)個(gè)數(shù) 
            vector<vector<int> > g; // g : 圖(graph)(用鄰接矩陣(adjacent matrix)表示) 
            vector<bool> known;        // known : 各點(diǎn)是否已經(jīng)選取 
            vector<int> dist;        // dist : 已選取點(diǎn)集到未選取點(diǎn)的最小邊長(zhǎng) 
            vector<int> prev;        // prev : 最小生成樹(shù)中各點(diǎn)的前一頂點(diǎn)
            int s;                    // s : 起點(diǎn)(start) 
            int sum;                // sum : 最小生成樹(shù)長(zhǎng) 

            bool Prim()                // 貪心算法(Greedy Algorithm) 
            {
                known.assign(n,             false);
                dist.assign(n, INT_MAX);
                prev.resize(n);                        // 初始化known、dist、prev。 
                dist[s] = 0;            // 初始化起點(diǎn)到自身的路徑長(zhǎng)為0。
                int i; 
                            for (i = 0; i < n; ++i)
                            {
                                int min = INT_MAX, v;
                                for (int i = 0; i < n; ++i)
                                    if (!known[i] && min > dist[i])
                            min             = dist[i], v = i;    // 尋找未知的最短路徑長(zhǎng)的頂點(diǎn)v， 
                    if (min == INT_MAX) break;        // 如果找不到，退出； 
                    known[v] = true;                // 如果找到，將頂點(diǎn)v設(shè)為已知，
                    sum += dist[v];                 // 調(diào)整最小生成樹(shù)長(zhǎng) 
                    for (int w = 0; w < n; ++w)        // 遍歷所有v指向的頂點(diǎn)w， 
                        if (!known[w] && g[v][w] < INT_MAX && dist[w] > g[v][w])
                            dist[w]             = g[v][w], prev[w] = v;    // 調(diào)整頂點(diǎn)w的最短路徑長(zhǎng)dist和最短路徑的前一頂點(diǎn) prev。 
                }
                            return i == n; // 如果選取頂點(diǎn)個(gè)數(shù)為n，成功。 
            }

            int main()
            {
                n             = 7;
                g.assign(n, vector            <int>(n, INT_MAX));
                g[            0][1] = g[1][0] = 2; g[0][2] = g[2][0] = 4;   g[0][3] = g[3][0] = 1;
                g[            1][3] = g[3][1] = 3; g[1][4] = g[4][1] = 10;
                g[            2][3] = g[3][2] = 2; g[2][5] = g[5][2] = 5;
                g[            3][4] = g[4][3] = 7; g[3][5] = g[5][3] = 8; g[3][6] = g[6][3] = 4;
                g[            4][6] = g[6][4] = 6;
                g[            5][6] = g[6][5] = 1; 
                
                s             = 0;        // 起點(diǎn)任選 
                sum = 0;
                            if (Prim())
                            {
                    cout             << sum << endl;
                                for (int i = 1; i < n; ++i)
                                    if(i != s) cout << prev[i] << "->" << i << endl;
                }
                            else
                            {
                    cout             << "Some vertex cann't be reached." << endl; 
                }
                
                system(            "pause");
                            return 0;
            }
            

            
	
            


            
	    
    

            Feedback
            
	
			
            
				
            
					
            
						# re: Prim算法  回復(fù)  更多評(píng)論
						  
					
            
					2009-04-15 12:52 by brightcoder
				
            
				
            good!~
            
			
            
		




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



久久九九久精品国产免费直播|
99久久无码一区人妻|
日韩精品久久久久久久电影|
亚洲国产成人精品女人久久久
|
久久伊人五月丁香狠狠色|
亚洲精品乱码久久久久久蜜桃不卡|
精品久久人妻av中文字幕|
久久久久国产一区二区三区|
亚洲AV无码久久精品蜜桃|
国产精品久久久天天影视香蕉
|
高清免费久久午夜精品|
欧美伊人久久大香线蕉综合69|
无码日韩人妻精品久久蜜桃
|
国产婷婷成人久久Av免费高清
|
精品国产99久久久久久麻豆|
国产精品久久久久久福利漫画
|
久久综合噜噜激激的五月天|
国产精品99久久不卡|
亚洲女久久久噜噜噜熟女|
久久精品视频网|
国内精品久久久久影院一蜜桃|
久久精品中文字幕大胸|
国产精品免费久久久久电影网|
久久久国产精品亚洲一区|
精品国产99久久久久久麻豆|
久久久久99精品成人片三人毛片|
99久久无码一区人妻a黑|
亚洲AV无一区二区三区久久
|
久久强奷乱码老熟女|
久久成人影院精品777|
人妻无码αv中文字幕久久|
国产午夜电影久久|
伊人丁香狠狠色综合久久|
久久久免费精品re6|
亚洲精品高清国产一线久久|
热久久视久久精品18|
一本久久综合亚洲鲁鲁五月天|
狠狠色综合久久久久尤物|
国产一区二区精品久久凹凸|
国产高清国内精品福利99久久|
一级做a爰片久久毛片16|