作者 主題: 使用相鄰矩陣找圖上兩點間所有路徑?  (閱讀 3146 次)

0 會員 與 1 訪客 正在閱讀本文。

summer1201

  • 可愛的小學生
  • *
  • 文章數: 2
    • 檢視個人資料
前輩們好
小弟用相鄰矩陣跟類似DFS的方法寫了一個程式
找圖上兩點間所有路徑
目前跑到16個點都還正確
但點一變多,像到100個點的話,程式跑到一半就關掉了
可能有邏輯判斷有寫錯,但小弟找很久還是找不出bug
希望大大們能給點意見,謝謝
代碼: [選擇]
#include <iostream>
#include <fstream>
#define SIZE 16
using namespace std;

int map[SIZE][SIZE] =  {{0,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0},
                        {1,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0},
                        {1,0,0,1,0,0,1,0,0,0,1,0,0,0,0,0},
                        {0,1,1,0,0,1,0,0,0,1,0,0,0,0,0,0},
                        {1,0,0,0,0,1,1,0,0,0,0,0,1,0,0,0},
                        {0,0,0,1,1,0,0,1,0,0,0,0,0,0,0,1},
                        {0,0,1,0,1,0,0,1,0,0,0,0,0,0,1,0},
                        {0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0},
                        {1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,0},
                        {0,0,0,1,0,0,0,0,1,0,0,1,0,0,0,1},
                        {0,0,1,0,0,0,0,0,1,0,0,1,0,0,1,0},
                        {0,1,0,0,0,0,0,0,0,1,1,0,0,1,0,0},
                        {0,0,0,0,1,0,0,0,1,0,0,0,0,1,1,0},
                        {0,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1},
                        {0,0,0,0,0,0,1,0,0,0,1,0,1,0,0,1},
                        {0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0}};
                            
int visit[SIZE];//存走過的點
int stack[SIZE];//存路徑
void dfs(int s,int d,int stack_index);
void dfs1(int s,int d,int stack_index,int visit_index);
void output(int stack_index);
ofstream fout("output.txt");
 
int main(void){            
    
    int source,destination;
  
    cout<<"source:";
    cin>>source;
    cout<<"destination:";
    cin>>destination;
    dfs(source,destination,0);
    
    fout.close();
    system("pause");
    return 0;
}

void dfs(int s,int d,int stack_index){
     int i;
    
     if(visit[s]!=-1){//起點不重複
        stack[stack_index]=s;//加入
        stack_index=stack_index+1;
        visit[s]=-1;//標記走過
        dfs1(s,d,stack_index,0);//找鄰點
     }
}

void dfs1(int s,int d,int stack_index,int visit_index){
    
     while(visit_index<SIZE){
        if(map[s][visit_index]==1 && visit[visit_index]!=-1){//鄰點且沒走過
           stack[stack_index]=visit_index;//加入
           stack_index=stack_index+1;
           visit[visit_index]=-1;//標記走過
           if(visit_index==d){
              output(stack_index);
              visit[visit_index]=0;
              stack_index=stack_index-1;
              //cout<<stack_index;
           }
           else{
              dfs1(visit_index,d,stack_index,0);//找鄰點
              break;
           }  
        }
        visit_index++;
     }
     if(visit_index==SIZE){
           stack_index=stack_index-1;
           visit[s]=0;
           if(stack_index!=0){
              dfs1(stack[stack_index-1],d,stack_index,s+1);
              //break;
           }
     }
}

void output(int stack_index){
     //if(stack_index==8){
     for(int i=0;i<stack_index;i++){
        fout<<stack[i]<<" ";
     }
     fout<<endl;//}
}
http://
« 上次編輯: 2010-05-26 11:13 由 summer1201 »