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




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



国产精品免费久久久久电影网|
久久久久噜噜噜亚洲熟女综合|
国内精品久久久久影院老司|
无码乱码观看精品久久|
久久九九久精品国产免费直播|
中文字幕人妻色偷偷久久|
国产∨亚洲V天堂无码久久久|
久久久久亚洲精品男人的天堂|
7777精品伊人久久久大香线蕉|
亚洲伊人久久精品影院|
精品久久久久久无码免费|
久久精品免费全国观看国产|
国产精品岛国久久久久|
香蕉aa三级久久毛片|
国产精品久久久久国产A级|
四虎久久影院|
久久国产三级无码一区二区|
浪潮AV色综合久久天堂|
一级女性全黄久久生活片免费
|
国产精品永久久久久久久久久|
久久强奷乱码老熟女网站|
久久99精品国产麻豆婷婷|
狠狠色丁香久久综合婷婷|
亚洲国产欧美国产综合久久|
国产激情久久久久影院|
久久er热视频在这里精品|
久久亚洲私人国产精品|
无码国内精品久久综合88|
久久久久久久久久久免费精品|
国产一区二区三区久久|
久久国产免费观看精品3|
久久久久亚洲AV片无码下载蜜桃|
人人狠狠综合久久亚洲|
久久天天躁狠狠躁夜夜2020|
99久久www免费人成精品|
免费观看成人久久网免费观看|
97久久香蕉国产线看观看|
九九精品99久久久香蕉|
77777亚洲午夜久久多喷|
久久久久免费看成人影片|
大伊人青草狠狠久久|