注册 登录
编程论坛 C++教室

我想了两天了,还是没有头绪,无向图寻找所有路径的问题

火蚂 发布于 2007-05-13 19:22, 879 次点击
只有本站会员才能查看附件,请 登录

如图所示,要求找到从1到6的所有路径
我在程序里面构造了一个无向图,一个栈
不知道使用循环还是用递归来控制栈,使得可行路径保存在栈中
输出格式如下:
1 2 3 4 6
1 2 3 5 6
1 2 4 3 5 6
1 2 4 6
1 3 2 4 6
1 3 4 6
1 3 5 6
帮忙想一想,万分感谢……

4 回复
#2
火蚂2007-05-13 20:38
希望帮我想想算法,我在线等的
主要是判断什么条件入栈,什么条件出栈,什么条件退出循环或者怎么使用递归等等,谢谢大家了
#3
火蚂2007-05-13 20:58
帮忙啊,数据结构高手们赐教好吗,不能让这个帖子沉底啊,谢谢了,叩首!
#4
leeco2007-05-14 22:43

程序代码:

#include <iostream>


using namespace std;


int adjmatrix[6][6]={
    {0,1,1,0,0,0},
    {1,0,1,1,0,0},
    {1,1,0,1,1,0},
    {0,1,1,0,0,1},
    {0,0,1,0,0,1},
    {0,0,0,1,1,0},
};


int x[6],used[6];


void dfs(int v)
{
    if(x[v-1]==5){
        printf(\"%d\",x[0]+1);
        for(int i=1;i<v;i++){
            printf(\" %d\",x[i]+1);
        }
        printf(\"\n\");
    }
    else {
        for(int i=0;i<6;i++){
            if(adjmatrix[x[v-1]][i]==1 && used[i]==0){
                used[i]=1;
                x[v]=i;
                dfs(v+1);
                used[i]=0;
            }
        }
    }
}


int main()
{
    x[0]=0;
    used[0]=1;
    dfs(1);
    system(\"pause\");
}

#5
herbert_19872007-05-16 02:09

用广度优先搜索应该可以吧

1