• <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 閱讀(2233) 評(píng)論(0)  編輯 收藏 引用  所屬分類: Algorithm 
			
			


		
            
		
            /**
             * USP 無權(quán)最短路徑算法(Unweighted Shortest Path Algorithm)
             * 輸入：(1)圖g；        // 有向圖或者無向圖 
             *         (2)源點(diǎn)s。 
             * 輸出：(1)源點(diǎn)s到各點(diǎn)的無權(quán)最短路徑長(zhǎng)dist(路徑的邊數(shù)最小)； 
             *         (2)源點(diǎn)s到各點(diǎn)的無權(quán)最短路徑prev。 
             * 結(jié)構(gòu): 圖g用鄰接表表示，最短路徑長(zhǎng)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)個(gè)數(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)號(hào) 

            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入隊(duì)。 
                while (!que.empty())                         
                            {
                                int v = que.front(); que.pop();            // v出隊(duì)， 
                    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入隊(duì)。 
                        }
                }
            }

            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;
            }
            

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



精品综合久久久久久888蜜芽|
久久久久久精品无码人妻|
青青国产成人久久91网|
91久久精品国产91性色也|
久久九色综合九色99伊人|
中文字幕无码免费久久|
久久亚洲欧美日本精品|
伊人久久大香线蕉精品不卡|
久久99热只有频精品8|
久久精品免费网站网|
精品无码久久久久国产|
伊色综合久久之综合久久|
亚洲综合精品香蕉久久网97|
无码精品久久久天天影视
|
国产一区二区三区久久精品|
久久国产精品无|
国产亚州精品女人久久久久久
|
精品乱码久久久久久久|
久久综合九色综合欧美就去吻|
久久香蕉国产线看观看精品yw|
午夜精品久久久内射近拍高清|
国产成人久久777777|
久久久久久久尹人综合网亚洲|
久久久久亚洲av无码专区喷水|
一级a性色生活片久久无少妇一级婬片免费放
|
久久中文字幕一区二区|
亚洲精品国产字幕久久不卡|
久久强奷乱码老熟女|
国产精品美女久久久久AV福利|
99久久精品费精品国产一区二区|
亚洲中文久久精品无码ww16|
一本综合久久国产二区|
久久精品国产清自在天天线|
国产成人久久777777|
狠狠色综合久久久久尤物|
国产精品免费看久久久香蕉|
一本伊大人香蕉久久网手机|
久久久久综合网久久|
国产精品热久久毛片|
日韩一区二区三区视频久久|
伊人久久大香线蕉综合热线|