主题:求图的深度,广度优先搜索程序
首先声明,我不是来这求作业的。以下是我自己利用上班时间写的,写得头都乱了,问题太多,是故不敢请大侠帮我看了。只是想请哪位大侠提供一个可运行的参考参考,我好改进,我的邮箱:huangyingw@gmail.com
----------------------------------------------------------------------------
// 图.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
struct adjex
{
int vertex;
adjex *next;
};
struct vertex
{
adjex *firstedge;
};
adjex *gadjex=NULL;
vertex gvertex[4];
int pass[100];
int top=0;
bool visit[4];
bool check[4];
//建图
void createGraph(int *data,int dim)
{
for(int i=0;i<dim;i++)
{
gvertex[i].firstedge=NULL;
adjex *gadjex=NULL;
for(int j=0;j<dim;j++)
{
if(gvertex[i].firstedge==NULL&&data[i*dim+j]!=0)
{
gadjex=new adjex;
gadjex->vertex=j;
gvertex[i].firstedge=gadjex;
}
else if(data[i*dim+j]!=0)
{
gadjex->next=new adjex;
gadjex->next->vertex=j;
gadjex->next->next=NULL;
gadjex=gadjex->next;
}
}
}
}
void pringGraph()
{
adjex *gadjex=NULL;
for(int i=0;i<4;i++)
{
gadjex=gvertex[i].firstedge;
while(gadjex!=NULL)
{
cout<<gadjex->vertex;
gadjex=gadjex->next;
}
cout<<endl;
}
}
void push(int data)
{
pass[top++]=data;
}
int pop()
{
if(top>=0)
return pass[--top];
else
return -1;
}
void trerverse(int i)
{
while(!check[i])
{
check[i]=true;
visit[i]=true;
push(i);
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while((visit[i]||check[i])&&gadjex->next!=NULL)
{
gadjex=gadjex->next;
i=gadjex->vertex;
}
}
if(check[i])
{
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while((visit[i]||check[i])&&gadjex->next!=NULL)
{
gadjex=gadjex->next;
i=gadjex->vertex;
}
gadjex=gadjex->next;
i=gadjex->vertex;
visit[i]=true;
check[i]=true;
push(i);
}
}
void dfSearch()
{
int i;
for(i=0;i<4;i++)
{
visit[i]=false;
check[i]=false;
}
i=0;
//为每个结点增加一个标志位,记录该结点
//是否访问过
visit[i]=true;
check[i]=true;
push(i);//结点i入栈
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while(top>=0&&top<4)
{
trerverse(i);
for(int k=0;k<top;k++)
cout<<pass[k]<<",";
cout<<endl;
i=pop();
visit[i]=false;
//check[i]=false;
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while((visit[i]||check[i])&&gadjex->next!=NULL)
{
gadjex=gadjex->next;
i=gadjex->vertex;
}
if(gadjex->next==NULL)
{
i=pop();
visit[i]=false;
}
else
continue;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int vertex[4][4]={{0,1,1,1},{1,0,1,1},{1,1,0,0},{1,1,0,0}};
createGraph(*vertex,4);
pringGraph();
dfSearch();
return 0;
}
----------------------------------------------------------------------------
// 图.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
using namespace std;
struct adjex
{
int vertex;
adjex *next;
};
struct vertex
{
adjex *firstedge;
};
adjex *gadjex=NULL;
vertex gvertex[4];
int pass[100];
int top=0;
bool visit[4];
bool check[4];
//建图
void createGraph(int *data,int dim)
{
for(int i=0;i<dim;i++)
{
gvertex[i].firstedge=NULL;
adjex *gadjex=NULL;
for(int j=0;j<dim;j++)
{
if(gvertex[i].firstedge==NULL&&data[i*dim+j]!=0)
{
gadjex=new adjex;
gadjex->vertex=j;
gvertex[i].firstedge=gadjex;
}
else if(data[i*dim+j]!=0)
{
gadjex->next=new adjex;
gadjex->next->vertex=j;
gadjex->next->next=NULL;
gadjex=gadjex->next;
}
}
}
}
void pringGraph()
{
adjex *gadjex=NULL;
for(int i=0;i<4;i++)
{
gadjex=gvertex[i].firstedge;
while(gadjex!=NULL)
{
cout<<gadjex->vertex;
gadjex=gadjex->next;
}
cout<<endl;
}
}
void push(int data)
{
pass[top++]=data;
}
int pop()
{
if(top>=0)
return pass[--top];
else
return -1;
}
void trerverse(int i)
{
while(!check[i])
{
check[i]=true;
visit[i]=true;
push(i);
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while((visit[i]||check[i])&&gadjex->next!=NULL)
{
gadjex=gadjex->next;
i=gadjex->vertex;
}
}
if(check[i])
{
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while((visit[i]||check[i])&&gadjex->next!=NULL)
{
gadjex=gadjex->next;
i=gadjex->vertex;
}
gadjex=gadjex->next;
i=gadjex->vertex;
visit[i]=true;
check[i]=true;
push(i);
}
}
void dfSearch()
{
int i;
for(i=0;i<4;i++)
{
visit[i]=false;
check[i]=false;
}
i=0;
//为每个结点增加一个标志位,记录该结点
//是否访问过
visit[i]=true;
check[i]=true;
push(i);//结点i入栈
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while(top>=0&&top<4)
{
trerverse(i);
for(int k=0;k<top;k++)
cout<<pass[k]<<",";
cout<<endl;
i=pop();
visit[i]=false;
//check[i]=false;
gadjex=gvertex[i].firstedge;
i=gadjex->vertex;
while((visit[i]||check[i])&&gadjex->next!=NULL)
{
gadjex=gadjex->next;
i=gadjex->vertex;
}
if(gadjex->next==NULL)
{
i=pop();
visit[i]=false;
}
else
continue;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int vertex[4][4]={{0,1,1,1},{1,0,1,1},{1,1,0,0},{1,1,0,0}};
createGraph(*vertex,4);
pringGraph();
dfSearch();
return 0;
}