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

            
	
            


            
	    
    




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



亚洲精品无码久久久久|
国产精品久久久久乳精品爆
|
97久久精品无码一区二区|
久久久久久精品久久久久|
无码8090精品久久一区|
久久久久久毛片免费看|
久久久久亚洲AV无码专区网站|
激情久久久久久久久久|
看全色黄大色大片免费久久久|
内射无码专区久久亚洲|
色综合久久天天综线观看|
久久婷婷色香五月综合激情|
欧美亚洲国产精品久久|
色综合久久无码中文字幕|
91精品国产91久久综合|
国产亚州精品女人久久久久久|
国产精品综合久久第一页|
久久亚洲视频|
久久精品无码专区免费青青|
久久精品视频网|
亚洲精品WWW久久久久久|
婷婷久久香蕉五月综合加勒比|
A狠狠久久蜜臀婷色中文网|
久久se这里只有精品|
久久久久久精品免费免费自慰|
MM131亚洲国产美女久久|
久久综合九色欧美综合狠狠
|
久久久99精品一区二区
|
久久精品欧美日韩精品|
国内精品久久久久久久亚洲|
偷偷做久久久久网站|
日本久久久久久中文字幕|
丁香色欲久久久久久综合网|
A级毛片无码久久精品免费|
色综合久久久久无码专区|
精品久久久久久无码免费|
久久久老熟女一区二区三区|
国内精品久久久久久不卡影院|
亚洲中文久久精品无码ww16
|
97超级碰碰碰久久久久|
四虎国产精品成人免费久久
|