Question

c++图的深度优先遍历 没错误 就不能遍历出来 总是少一个点

//图的深度优先遍历
#include<iostream>
using namespace std;
const int max=100;
int n;
void visite(int v){
cout<<v;
return;}
class graph{
public:
void creatG(){
int i,j,x;
cout<<"请输入图的顶点数"<<endl;
cin>>n;
for(i=0;i<n;i++){
for(j=i+1;j<n;j++){
cout<<"请输入这两个顶点是否为邻接点，如果是，输入1，否则请输入0"<<endl;
cout<<i+1<<j+1<<endl;
cin>>x;
edge[i][j]=x;
}
}
return;
}
void DFS_travel(){
int i;
for(i=0;i<n;i++)
visited[i]=false;
for(i=1;i<=n;i++)
if(visited[i]==false)
dfs(i);
return;
}
void dfs(int v){
int w;

visited[v]=true;
w=firstadj(v);
while (w!=0){
if(visited[w]==false)
dfs(w);
w=nextadj(v,w);
visite(w);
}
return;
}

int firstadj(int v)
{
int i;
for(i=0;i<n;i++){
if(edge[v-1][i]=1){
return i+1;
}
}
return 0;
}
int nextadj(int v,int w){
int i;
for(i=w;i<n;i++){
if(edge[v-1][i]==1&&visited[i+1]==false){
return i+1;
}
}
return 0;
}
private:
int edge[max][max];
int visited[max];
};
void main()
{
graph g;
g.creatG();
g.DFS_travel();
return ;
}

Answer 1

//图的深度优先遍历
#include<iostream>
using namespace std;
const int max=100;
int n;
void visite(int v)
{
    cout<<v;
    return;
}
class graph
{
public:
    void creatG()
    {
        int i,j,x;
        cout<<"请输入图的顶点数"<<endl;
        cin>>n;
        for(i=0;i<n;i++)
        {
            edge[i][i] = 0;//自身与自身应设为0
            for(j=i+1;j<n;j++)
            {
                cout<<"请输入这两个顶点是否为邻接点，如果是，输入1，否则请输入0"<<endl;
                cout<<i+1<<j+1<<endl;
                cin>>x;
                edge[i][j]=x;
                edge[j][i]=x;//这是无权的，所以反过来也要设为x
            }
        }
        return;
    }
    void DFS_travel()
    {
        int i;
        for(i=0;i<n;i++)
            visited[i]=false;
        for(i=0;i<n;i++) //从0开始
            if(visited[i]==false)
                dfs(i);
            return;
    }
    void dfs(int v)
    {
        int w;
                                                                                                                                                                                                  
        visited[v]=true;
        visite(v);
        for(w=firstadj(v);w!=0;w=nextadj(v,w))
        {
            if(visited[w]==false)
                dfs(w);
        }
                                                                                                                                                                                                  
        return;
    }
                                                                                                                                                                                            
    int firstadj(int v)
    {
        int i;
        for(i=0;i<n;i++)
        {
            if(edge[v][i]=1)//这都是v,i不是v+1,i-1什么的！
            {
                return i;
            }
        }
        return 0;
     }
    int nextadj(int v,int w)
    {
        int i;
        for(i=w;i<n;i++)
        {
            if(edge[v][i]==1&&visited[i]==false)//这也是！
            {
                return i;
            }
        }
        return 0;
    }
private:
    int edge[max][max];
    int visited[max];
};
void main()
{
    graph g;
    g.creatG();
    g.DFS_travel();
    return ;
}

LZ对图的储存与遍历还有误区啊！

建议自行调试，观察图中储存的变量的值的变化，能够加强理解！

不懂追问！为你们解决问题也是我学习的一部分！

2013 5 21 17:57

追问

太感谢了 已经会了
问一下 你是用的什么编程啊
看你的截图 我看我班也有和你一样的
很好奇 嘿嘿

追答

VC ++6.0……

我装了VC++6.0
又装了VS2012，还装了CFree……

平常给别人写我都是用VC++6.0，毕竟用这个的人多一些，但VC++有一些BUG……

学习愉快，晚安，少年！

Answer 2

visited数组的下标 注意下~