[問題] 有向圖形找cycle/圖形判斷是否為二分圖

[supercygnus (......)]

開發平台(Platform): (Ex: VC++, GCC, Linux, ...) 

DEV C++
額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 


問題(Question)：

有向圖形找cycle/圖形判斷是否為二分圖
餵入的資料(Input)：


預期的正確結果(Expected Output)：


錯誤結果(Wrong Output)：


程式碼(Code)：(請善用置底文網頁, 記得排版) 

http://ideone.com/x31jcG

補充說明(Supplement)：

有向圖形要怎麼找cycle呢,我是用兩種記號,一種記號用來判斷是否拜訪過
另一種記號用來判斷是不是走過的路,現在的問題是當沒路走要回頭時,
要怎麼把沿路經過節點的記號塗銷掉,防止cycle誤判


判斷二分圖,我是用一個mark[]陣列使用一個count++%2紀錄每個節點的mark值
當相鄰節點的mark值相等時就代表不是二分圖
現在的問題是當要回頭時,給下一個未拜訪節點的mark值是不是有可能誤判
因為只是單純的count++%2,要怎麼解決呢?

void checkCycleDirection(Node *ptr)  在1053行
void checkBipart(Node *ptr)  在871行

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.252.240.31


用遞迴寫出來了,供大家參考

void cycle(Node *ptr){

        Node *w;
        visited[ptr->data]=true;
        cout<<"Visit:"<<ptr->data<<endl;
        predecessor[ptr->data]=true;


        for(w=Adjlist[ptr->data].link;w;w=w->link){
           if(predecessor[w->data]==true)
              cout<<"發現迴圈!!"<<endl;
           else if(visited[w->data]==false)
             cycle(w);

               }

        predecessor[ptr->data]=false;



     }


void checkBipartite(Node *ptr,int key){


        Node *w;

        mark[ptr->data]=key;
        cout<<"Visit:"<<ptr->data<<endl;


        for(w=Adjlist[ptr->data].link;w;w=w->link){
           if(mark[w->data]==0)
              checkBipartite(w,3-key);
            else if(mark[w->data]==mark[ptr->data])
                cout<<"不是二分圖!!"<<endl;


               }

     }
※ 編輯: supercygnus     來自: 111.252.240.31       (12/30 00:04)