• <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
            


            		
	
            
	
            
		
			
		
		
			
            
				
					
	
            
		
            
			
            
				USP 無權(quán)最短路徑算法
			
            
 			Posted on 2009-04-09 10:44 lzmagic 閱讀(2229) 評論(0)  編輯 收藏 引用  所屬分類: Algorithm 
			
			


		
            
		
            /**
             * USP 無權(quán)最短路徑算法(Unweighted Shortest Path Algorithm)
             * 輸入：(1)圖g；        // 有向圖或者無向圖 
             *         (2)源點(diǎn)s。 
             * 輸出：(1)源點(diǎn)s到各點(diǎn)的無權(quán)最短路徑長dist(路徑的邊數(shù)最小)； 
             *         (2)源點(diǎn)s到各點(diǎn)的無權(quán)最短路徑prev。 
             * 結(jié)構(gòu): 圖g用鄰接表表示，最短路徑長dist用數(shù)組表示。 
             * 算法：廣度優(yōu)先搜索(BFS)
             * 復(fù)雜度：O(|E|+|V|)~O(|E|)  
                         */             
            #include             <iostream>
            #include             <vector>
            #include             <list>
            #include             <queue>
            #include             <iterator>
            #include             <algorithm>
            #include             <numeric>
            #include             <functional>
            #include             <climits>
            using namespace std;

            int n;                        // n : 頂點(diǎn)個數(shù) 
            vector<list<int> > g;        // g : 圖(graph)(用鄰接表(adjacent list)表示) 
            int s;                        // s : 源點(diǎn)(source)
            vector<int> dist;            // dist : 源點(diǎn)s到各點(diǎn)之間的距離
            vector<int> prev;            // prev : 各點(diǎn)最短路徑的前一頂點(diǎn)號 

            void USP()        // 廣度優(yōu)先搜索(BFS)
            {
                queue            <int> que;
                dist.assign(n, INT_MAX);                                 // 初始化dist， 
                prev.resize(n);                                // 初始化prev。 
                dist[s] = 0; que.push(s);                    // s到自身距離為0，s入隊。 
                while (!que.empty())                         
                            {
                                int v = que.front(); que.pop();            // v出隊， 
                    for (list<int>::iterator it = g[v].begin(); it != g[v].end(); ++it) // 遍歷v相鄰點(diǎn)*it， 
                        if (dist[*it] == INT_MAX)            // 如果*it未訪問， 
                        {
                            dist[            *it] = dist[v] + 1; prev[*it] = v;    // 調(diào)整點(diǎn)*it， 
                            que.push(*it);                    // *it入隊。 
                        }
                }
            }

            void Print_SP(int v)
            {
                             if (v != s) Print_SP(prev[v]);
                 cout             << v << " ";
            }

            int main()
            {
                n             = 7;
                g.assign(n, list            <int>()); 
                g[            0].push_back(1); g[0].push_back(3); 
                g[            1].push_back(3); g[1].push_back(4); 
                g[            2].push_back(0); g[2].push_back(5); 
                g[            3].push_back(2); g[3].push_back(4); g[3].push_back(5); g[3].push_back(6); 
                g[            4].push_back(6); 
                g[            6].push_back(5);
                
                s             = 2;
                USP();
                   
                copy(dist.begin(), dist.end(), ostream_iterator            <int>(cout, " ")); cout << endl;
                            for (int i = 0; i < n; ++i)
                                if(dist[i] != INT_MAX)
                                {
                        cout             << s << "->" << i << ": ";
                        Print_SP(i); 
                        cout             << endl; 
                    }
                    
                system(            "pause");
                            return 0;
            }
            

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



久久亚洲AV无码精品色午夜麻豆|
久久久亚洲裙底偷窥综合|
伊人色综合久久天天人守人婷|
久久亚洲欧美日本精品|
人妻精品久久无码区|
国内精品综合久久久40p|
久久天天躁夜夜躁狠狠|
久久夜色精品国产www|
久久激情五月丁香伊人|
久久精品国产精品亚洲|
精品国产婷婷久久久|
热久久这里只有精品|
成人精品一区二区久久久|
91精品国产9l久久久久|
精品国产91久久久久久久|
久久成人国产精品二三区|
久久国产午夜精品一区二区三区|
成人a毛片久久免费播放|
亚洲国产精品一区二区三区久久|
久久有码中文字幕|
狠狠色丁香久久婷婷综合|
精品久久久噜噜噜久久久|
伊人久久综在合线亚洲2019|
久久国产成人亚洲精品影院|
思思久久99热免费精品6|
伊人久久大香线蕉亚洲五月天|
久久婷婷五月综合国产尤物app|
国产精品久久久福利|
久久精品免费大片国产大片|
久久精品国产色蜜蜜麻豆|
国产国产成人精品久久|
亚洲七七久久精品中文国产
|
国产午夜久久影院|
国产成人精品久久一区二区三区av
|
亚洲精品国产第一综合99久久|
久久香蕉超碰97国产精品|
国产精品美女久久久久AV福利|
欧美日韩久久中文字幕|
日本精品久久久久中文字幕|
久久亚洲精品无码aⅴ大香|
国产综合精品久久亚洲|