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




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



欧美精品国产综合久久|
久久精品亚洲日本波多野结衣|
91精品国产综合久久香蕉|
日本一区精品久久久久影院|
久久99精品国产99久久6|
久久婷婷色香五月综合激情|
久久天天躁狠狠躁夜夜avapp
|
国产精品9999久久久久|
曰曰摸天天摸人人看久久久|
天天做夜夜做久久做狠狠|
国产V亚洲V天堂无码久久久|
久久九九久精品国产|
无码精品久久久久久人妻中字|
青青青国产成人久久111网站|
久久精品桃花综合|
久久国产香蕉一区精品|
久久夜色精品国产欧美乱|
欧美精品一区二区久久|
国产精品九九九久久九九|
久久精品人人做人人爽电影|
久久AAAA片一区二区|
久久久精品一区二区三区|
亚洲熟妇无码另类久久久|
四虎亚洲国产成人久久精品|
国产精品九九久久免费视频|
久久午夜羞羞影院免费观看|
久久这里都是精品|
亚洲精品综合久久|
日本精品久久久久影院日本|
中文字幕亚洲综合久久|
99久久精品毛片免费播放|
久久精品国产久精国产思思|
久久久久久国产精品美女|
久久婷婷人人澡人人爽人人爱|
婷婷久久综合九色综合绿巨人
|
久久人人爽人人爽人人片AV不
|
人人狠狠综合久久亚洲婷婷|
久久精品人成免费|
国产精品国色综合久久|
国产V亚洲V天堂无码久久久|
99久久99这里只有免费的精品|