• <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 閱讀(2073) 評論(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
            
			
            
		




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



亚洲精品乱码久久久久久|
久久无码人妻精品一区二区三区|
久久精品成人免费观看97|
思思久久99热免费精品6|
久久亚洲AV成人无码|
久久国产一区二区|
久久AV无码精品人妻糸列|
精品精品国产自在久久高清|
亚洲国产精品成人AV无码久久综合影院
|
亚洲国产高清精品线久久
|
欧美无乱码久久久免费午夜一区二区三区中文字幕
|
久久97久久97精品免视看秋霞
|
欧美亚洲国产精品久久蜜芽|
日本久久中文字幕|
国产精品欧美久久久久天天影视|
婷婷五月深深久久精品|
国产精品久久久久久久久软件|
色成年激情久久综合|
国产精品99久久99久久久|
国产精品99久久久精品无码|
久久精品成人欧美大片|
国产精品嫩草影院久久|
热99re久久国超精品首页|
精品国产一区二区三区久久久狼|
久久久久免费精品国产|
亚洲欧美一区二区三区久久|
久久亚洲国产成人精品无码区|
嫩草影院久久国产精品|
国产美女久久久|
久久91精品国产91久久小草
|
久久精品99无色码中文字幕|
99久久99久久精品国产|
久久综合九色综合精品|
久久亚洲国产午夜精品理论片|
久久久91精品国产一区二区三区
|
国内精品伊人久久久久妇|
最新久久免费视频|
亚洲色欲久久久综合网|
狠狠综合久久综合88亚洲|
欧美丰满熟妇BBB久久久|
久久久久久国产精品无码超碰|