Question

请帮我写一个用c++实现图的实现和深度优先遍历的程序

一定要是c++的哈

Answer 1

呵呵~~楼主的意思我不是很明穗闹弊白，是说建立一个图，然后实现深度优先搜索与广度优先搜索对么？？如果我理解的没错的话，那么下面这个程序将是你需要的~
#include<iostream.h>
#define max 8;
typedef struct Enode
{
int adjvex;
struct Enode *next;
}*Pointer;
typedef struct Vnode
{
int vertex;
Enode *link;
}adjlist[8];
int Visited[8]={0,0,0,0,0,0,0,0};
void build_adjlist(adjlist &ga)
{
int n,e,i,j;
Pointer p;
cout<<"顶点弯备数和边数：";
cin>>n>>e;
for(i=0;i<n;i++)
{
ga[i].vertex=i;
ga[i].link=NULL;
}
for(int k=0;k<e;k++)
{
cout<<"dingdiandui:";
cin>>i>>j;

p=new Enode;
p->adjvex=j;
p->next=ga[i].link;
ga[i].link=p;
p=new Enode;
p->adjvex=i;
p->next=ga[j].link;
ga[j].link=p;

}

/*for(int k=0;k<2*e;k++)
{
cout<<"顶点对：";
cin>>i>>j;//(i,j)顶点对
p=new struct Enode;
p->adjvex=j;
p->next=NULL;
if(ga[i].link=NULL)
{
ga[i].link=p;
p1=p;
}
else
{
p1->next=p;
p1=p1->next;
}*/

}
void jianyan(adjlist &ga)
{
Pointer p;
int n;
cout<<"请输入顶点数:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<ga[i].vertex<<" ";
p=ga[i].link;
while(p!=NULL)
{
if(p->next!=NULL)
{
cout<<p->adjvex<<" ";
p=p->next;
}
else
{
cout<<p->adjvex<<endl;
p=p->next;

}
}
}
}

void dfs(adjlist &ga,int v0)
{
Pointer p;
cout<<v0<<endl;
Visited[v0]=1;
p=ga[v0].link;
while(p!=NULL)
{
if (Visited[p->adjvex]==0)//*
dfs(ga,p->adjvex);
else
p=p->next;
}

}

void bfs(adjlist &ga,int v0)
{

Pointer p;
int v,f,r;
for(int i=0;i<8;i++)
{
Visited[i]=0;
}
int q[50];
cout<<v0<<endl;
Visited[v0]=1;
f=0;
r=0;
p=ga[v0].link;
do
{
while(p!=NULL)

{
v=p->adjvex;
if(Visited[v]==0)
{
q[r]=v;
r++;
cout<<v<<endl;
Visited[v]=1;
}
p=p->next;
}
if(f!=r)
{
v=q[f];
f++;
p=ga[v].link;
}
}
while((p!=NULL)||(f!=r));

}

void main()
{
adjlist ga;
int v;
build_adjlist(ga);
jianyan(ga);
cout<<"请输入起始顶点：";
cin>>v;
cout<<"shendu:"<<endl;
dfs(ga,v);
cout<<"guangdu:"<猜族<endl;
bfs(ga,v);
}

这个程序是我上星期亲自编写而且已经验收过的，其中存贮结构用的是邻接表法，代码中的“jianyan”函数的功能是输出你所建立的邻接表从而检查你的图建立的是否正确，“dfs”和“bfs”两个函数分别是深度优先搜索（bfs）与广度优先搜索的函数，图的建立思路用和书上的一样.由于验收的比较仓促所以函数没有经过细致的优化，不过请楼主放心，这个代码是觉得没有错的，如果有什么不懂的话楼主可以hi我~~~~~~~我这里还编写了一个与书本上思路不一样的建立程序，但是害怕楼主看不懂，所以就不给你发了哈~

Answer 2

boolean vistited[max];
statue(*visitefunc)(int v);
void dfstraverse(graph g.status(*visit)(int v)
{
visitfunc=visit;
for(v=0;v<g.vexnum;++v)visited[v]=false;
for(v=0;v<g.vexnum;++v)
if(!visited[v]) dfs(g,v);
}