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

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产国产成人久久精品|
亚洲精品无码久久久久|
午夜精品久久久久成人|
精品国产青草久久久久福利|
成人国内精品久久久久一区|
狠狠色综合网站久久久久久久|
热久久最新网站获取|
精品久久久久香蕉网|
久久婷婷五月综合97色直播|
久久99精品久久久久久久久久|
精品无码久久久久久久动漫|
天天爽天天狠久久久综合麻豆|
久久久久久极精品久久久
|
久久精品无码专区免费东京热|
国产精品久久久久影院色|
久久毛片一区二区|
91精品国产91久久久久久|
亚洲精品乱码久久久久66|
无码8090精品久久一区|
国产高清美女一级a毛片久久w|
久久精品国产99久久久|
久久久www免费人成精品|
色狠狠久久综合网|
国内精品伊人久久久久妇|
国产精品久久久久一区二区三区|
久久久久无码精品国产不卡|
久久精品国产亚洲av麻豆图片|
欧美日韩精品久久久免费观看|
99国产欧美精品久久久蜜芽
|
www久久久天天com|
亚洲精品乱码久久久久久蜜桃图片|
亚洲精品综合久久|
久久毛片一区二区|
久久久久国产精品嫩草影院|
亚洲国产精品无码久久久久久曰|
久久99精品国产99久久6|
国产2021久久精品|
久久久久99精品成人片三人毛片
|
无码超乳爆乳中文字幕久久
|
久久久女人与动物群交毛片|
久久婷婷五月综合97色|