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


            		
	
            
	
            
		
			
		
		
			
            
				
					
	
            
		
            
			
            
				Topsort 拓撲排序
			
            
 			Posted on 2009-04-06 09:40 lzmagic 閱讀(2065) 評論(2)  編輯 收藏 引用  所屬分類: Algorithm 
			
			


		
            
		
            /**
             * TOPSORT(簡單版) 拓撲排序(Topological Sort) 
             * 輸入：有向圖g 
             * 輸出：是否存在拓撲排序，如果存在，獲取拓撲排序序列seq
             * 結構：圖g用鄰接矩陣表示
             * 算法：廣度優先搜索(BFS) 
             * 復雜度：O(|V|^2) 
                         */
             
            #include             <iostream>
            #include             <vector>
            #include             <queue>
            #include             <iterator>
            #include             <algorithm>
            #include             <numeric>
            #include             <climits>
            using namespace std;

            int n;                            // n ：頂點個數 
            vector<vector<int> > g;           // g ：圖(graph)(用鄰接矩陣(adjacent matrix)表示)  
            vector<int> seq;                // seq ：拓撲序列(sequence) 

            bool TopSort()
            {
                vector            <int> inc(n, 0);     
                            for (int i = 0; i < n; ++i)
                                for (int j = 0; j < n; ++j)
                                     if (g[i][j] < INT_MAX) ++inc[j]; // 計算每個頂點的入度， 
                queue<int> que;
                            for (int j = 0; j < n; ++j)
                                if (inc[j] == 0) que.push(j); // 如果頂點的入度為0，入隊。
                int seqc = 0;
                seq.resize(n);
                            while (!que.empty())     // 如果隊列que非空，
                {
                                int v = que.front(); que.pop();     
                    seq[seqc            ++] = v;      // 頂點v出隊，放入seq中，
                    for (int w = 0; w < n; ++w)     // 遍歷所有v指向的頂點w，
                        if (g[v][w] < INT_MAX)
                                        if (--inc[w] == 0) que.push(w); // 調整w的入度，如果w的入度為0，入隊。 
                }
                            return seqc == n; // 如果seq已處理頂點數為n，存在拓撲排序，否則存在回路。
            }

            int main()
            {
                n             = 7;    
                g.assign(n, vector            <int>(n, INT_MAX));
                g[            0][1] = 1, g[0][2] = 1, g[0][3] = 1;
                g[            1][3] = 1, g[1][4] = 1;
                g[            2][5] = 1;
                g[            3][2] = 1, g[3][5] = 1, g[3][6] = 1;
                g[            4][3] = 1, g[4][6] = 1;
                g[            6][5] = 1;     

                            if (TopSort())
                            {
                     copy(seq.begin(), seq.end(), ostream_iterator            <int>(cout, " "));
                     cout             << endl;
                }
                            else
                            {
                     cout             << "circles exist" << endl;
                }
                
                system(            "pause");
                            return 0;
            }
            

            
	
            


            
	    
    

            Feedback
            
	
			
            
				
            
					
            
						# re: [圖論算法] TOPSORT 拓撲排序  回復  更多評論
						  
					
            
					2009-04-07 13:38 by aiver
				
            
				
            你的代碼輸出是 0 1 4 2 6 3 5， 2先于3輸出了，有問題。
            
			
            
		
			
            
				
            
					
            
						# re: [圖論算法] TOPSORT 拓撲排序  回復  更多評論
						  
					
            
					2009-04-07 14:37 by lzmagic
				
            
				
            @aiver

            啊哈，有個小bug，現在已經修改好了，謝謝指出錯誤~

            答案是：0 1 4 3 2 6 5
            
			
            
		




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



亚洲日本久久久午夜精品|
久久久国产99久久国产一|
人人妻久久人人澡人人爽人人精品|
久久久久久亚洲精品不卡
|
久久久久高潮综合影院|
一本色道久久88综合日韩精品
|
中文字幕热久久久久久久|
波多野结衣中文字幕久久|
国产成人精品久久亚洲高清不卡|
欧美伊人久久大香线蕉综合69|
精品精品国产自在久久高清|
久久人人爽人人爽人人片AV东京热
|
亚洲国产另类久久久精品|
97久久精品人人做人人爽|
久久99国产精品一区二区|
久久精品一区二区三区中文字幕|
午夜精品久久久久久久|
欧美精品丝袜久久久中文字幕|
国产精品久久久久一区二区三区|
亚洲欧美成人综合久久久|
久久免费99精品国产自在现线|
激情伊人五月天久久综合|
伊人久久国产免费观看视频|
国产精品激情综合久久|
777米奇久久最新地址|
精品久久久久久国产|
亚洲国产精品久久久天堂|
亚洲国产一成久久精品国产成人综合|
久久免费小视频|
国产精品99久久不卡|
久久精品www|
26uuu久久五月天|
91精品免费久久久久久久久|
国产精品久久久久9999高清|
久久精品中文闷骚内射|
精品一区二区久久|
狠狠久久亚洲欧美专区|
欧美激情精品久久久久|
伊人久久免费视频|
国产精品狼人久久久久影院|
国产精品综合久久第一页|