关于邻接表的深度优先遍历，自己写了个小程序，无法实现，求大鸟们指教
#include<iostream.h>#include<string.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20
typedef char VertexType[5];
typedef struct ArcNode {
int adjvex; //边所指向的顶点的位置
struct ArcNode *nextarc;
int weight;//表示权
} ArcNode;
typedef struct VNode {
VertexType data;
ArcNode *firstarc;
} VNode;
typedef struct {
VNode vertices[MAX_VERTEX_NUM];// 注意
int vexnum, arcnum;
} ALGraph;
void Init_ALGraph(ALGraph &G)
{
cout<<"输入图的顶点数:";
cin>>G.vexnum;
cout<<"输入图的边数:";
cin>>G.arcnum;
int i;
cout<<"输入定点值:";
for(i=0;i<G.arcnum;++i) //构造表头向量
{
cin>>G.vertices[i].data;//输入顶点值
G.vertices[i].firstarc=NULL;//初始化链表头指针为“空”
}
}
//获取定点在定点向量中的位置 如果出错就终止运行
int Get_Vertex_Location( ALGraph G, VertexType v )
{
int i;
for( i=0; i<G.vexnum; ++i )
if( strcmp( v, G.vertices[i].data ) == 0 )
return i;
exit(0);
}
void CreatUDG(ALGraph &G)
{
int i,j,k;
Init_ALGraph(G);
VertexType v1,v2;
cout<<"输入图的边:";
for(k=0;k<G.arcnum;++k) //输入各边并构造邻接表
{
cin>>v1>>v2; //输入一条弧的始点和终点
i=Get_Vertex_Location( G, v1 ); //确定i和j在G中位置，即顶点的序号
j=Get_Vertex_Location( G, v2 );
ArcNode *pi,*pj;
pi=(ArcNode*)malloc(sizeof(ArcNode));
pi->adjvex=j; //对弧结点赋邻接点位置信息
pi->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=pi; //插入链表G.vertices[i]
pj=(ArcNode*)malloc(sizeof(ArcNode));
pj->adjvex=i; //
pj->weight=0;
pj->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=pj; // 插入链表G.vertices[j]
}
}
void DFSTraverse(ALGraph G,bool *&visited,int i,int n)
{
//cout<<i<<'';
//bool *&visited=new bool[n];
visited[i]=true;
ArcNode *p;
p = G.vertices[i].firstarc;
while(p!=NULL)
{
int j=p->adjvex;
if(!visited[j])
{
DFSTraverse(G,visited,j,n);
p=p->nextarc;
}
}
}
void Print_ALGraph(ALGraph G)
{
int i;
for(i=0;i<G.vexnum;++i)
{
ArcNode *p=G.vertices[i].firstarc;
while(p)
{
cout<<G.vertices[i].data;
cout<<G.vertices[p->adjvex].data;
}
p=p->nextarc;
}
}
int main()
{
ALGraph G;
int i,n;
CreatUDG(G);
Print_ALGraph( G );
bool*visited=new bool[n];
for(i=1;i<=n;i++)
visited[i]=false;
DFSTraverse(G,visited,1,n);
return 0;
}
