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




            






            

				
			
            
		            		
	
            
	
            
		
			

		
	
            

            

    
    







            
	   
	



精品久久国产一区二区三区香蕉|
国产成人久久精品激情|
久久精品国产99久久久香蕉|
亚洲午夜福利精品久久|
精品无码久久久久国产|
精品久久久久国产免费|
日本人妻丰满熟妇久久久久久|
久久99精品国产麻豆蜜芽|
2021国内久久精品|
大美女久久久久久j久久|
亚洲精品无码久久久久去q
|
久久精品无码av|
性色欲网站人妻丰满中文久久不卡|
国产精品久久影院|
久久综合给久久狠狠97色|
久久精品国产只有精品66|
久久青青草原国产精品免费|
国产精品久久久久久久app|
精品无码久久久久久久动漫|
久久狠狠高潮亚洲精品|
午夜精品久久久久久久久|
免费精品久久天干天干|
深夜久久AAAAA级毛片免费看|
99精品久久久久中文字幕|
性欧美丰满熟妇XXXX性久久久|
午夜精品久久久久久影视riav|
久久精品亚洲精品国产欧美|
91久久国产视频|
久久99精品综合国产首页|
69久久夜色精品国产69|
www.久久99|
久久综合久久综合久久综合|
国产精品久久99|
伊人色综合久久天天|
国产精品gz久久久|
久久高清一级毛片|
久久久久亚洲av成人无码电影|
久久久久免费视频|
久久婷婷五月综合成人D啪|
一本色道久久综合亚洲精品|
人人狠狠综合久久88成人|