主题:深度优先搜索问题
最近写了一个基于邻接矩阵的深度优先算法,可是有问题,求高手相助,谢谢
#include<iostream>
using namespace std;
#define Max 6
typedef struct//邻接矩阵结构
{
int Nodenum,Arcnum;//节点个数,边长数
int array[Max][Max];//邻接矩阵
int Node[Max];//节点数组
}Matrix;
void Create(Matrix &G)//构造邻接矩阵
{
int i,j,k;
int v1,v2;
cout<<"请输入节点数和弧条数"<<endl;
cin>>G.Nodenum>>G.Arcnum;
for(i=0;i<G.Nodenum;i++)//初始化矩阵
for(j=0;j<G.Nodenum;j++)
G.array[i][j]=0;
for(i=0;i<G.Nodenum;i++)
{
cout<<"请输入节点(最小不能小于1)"<<endl;
cin>>G.Node[i];
}
for(i=1;i<=G.Arcnum;i++)
{
cout<<"请输入每条边的两个顶点"<<endl;
cin>>v1>>v2;
j=0;
k=0;
while(v1!=G.Node[j])//用来判读输入的节点是否有误
{
j++;
if(j==G.Nodenum)
{
cout<<"你输入的节点1有误"<<endl;
i--;
}
}
while(v2!=G.Node[k])
{
k++;
if(k==G.Nodenum)
{
cout<<"你输入的节点2有误"<<endl;
i--;
}
}
if((j!=G.Nodenum)&&(k!=G.Nodenum))//对称矩阵,我没有压缩储存
G.array[v1-1][v2-1]=G.array[v2-1][v1-1]=1;
}
}
void DFS(Matrix &G,int v,int count)//深度优先查找
{
int i,k,j;
int m=count;
int visited[Max]={0,0,0,0,0,0};//用于标志访问过的节点
for(i=0;i<G.Nodenum;i++)
{
if(G.array[v-1][i]==1)
{
k=i+1;
j=0;
while(k!=visited[j])
{
j++;
if(j==Max)
{
cout<<k<<endl;
visited[m]=k;
m++;
}
}
G.array[v-1][i]=G.array[i][v-1]=-1;//防止重复访问
DFS(G,k,m);
}
else
return;
}
}
void main()
{
int v;
Matrix G;
Create(G);
cout<<"请输入你想查找的第一个节点"<<endl;
cin>>v;
cout<<"变历结果是"<<endl;
cout<<v<<endl;
DFS(G,v,0);
}
#include<iostream>
using namespace std;
#define Max 6
typedef struct//邻接矩阵结构
{
int Nodenum,Arcnum;//节点个数,边长数
int array[Max][Max];//邻接矩阵
int Node[Max];//节点数组
}Matrix;
void Create(Matrix &G)//构造邻接矩阵
{
int i,j,k;
int v1,v2;
cout<<"请输入节点数和弧条数"<<endl;
cin>>G.Nodenum>>G.Arcnum;
for(i=0;i<G.Nodenum;i++)//初始化矩阵
for(j=0;j<G.Nodenum;j++)
G.array[i][j]=0;
for(i=0;i<G.Nodenum;i++)
{
cout<<"请输入节点(最小不能小于1)"<<endl;
cin>>G.Node[i];
}
for(i=1;i<=G.Arcnum;i++)
{
cout<<"请输入每条边的两个顶点"<<endl;
cin>>v1>>v2;
j=0;
k=0;
while(v1!=G.Node[j])//用来判读输入的节点是否有误
{
j++;
if(j==G.Nodenum)
{
cout<<"你输入的节点1有误"<<endl;
i--;
}
}
while(v2!=G.Node[k])
{
k++;
if(k==G.Nodenum)
{
cout<<"你输入的节点2有误"<<endl;
i--;
}
}
if((j!=G.Nodenum)&&(k!=G.Nodenum))//对称矩阵,我没有压缩储存
G.array[v1-1][v2-1]=G.array[v2-1][v1-1]=1;
}
}
void DFS(Matrix &G,int v,int count)//深度优先查找
{
int i,k,j;
int m=count;
int visited[Max]={0,0,0,0,0,0};//用于标志访问过的节点
for(i=0;i<G.Nodenum;i++)
{
if(G.array[v-1][i]==1)
{
k=i+1;
j=0;
while(k!=visited[j])
{
j++;
if(j==Max)
{
cout<<k<<endl;
visited[m]=k;
m++;
}
}
G.array[v-1][i]=G.array[i][v-1]=-1;//防止重复访问
DFS(G,k,m);
}
else
return;
}
}
void main()
{
int v;
Matrix G;
Create(G);
cout<<"请输入你想查找的第一个节点"<<endl;
cin>>v;
cout<<"变历结果是"<<endl;
cout<<v<<endl;
DFS(G,v,0);
}