图的遍历输出的问题,恳请各位帮帮忙,急~~~~~~~~~~~~
利用深度(递归&非递归)&广度遍历图(先用矩阵存储再转为邻接表输出),以下是程序,我用cfree编的,但是不知道哪里有错....就是没法运行...一运行windows就自动关闭程序了T_T...各位高手帮我看一下行么?先谢过!
#include <stdio.h>
#include <malloc.h>
typedef int InfoType;
#define MAXV 100
typedef struct
{
int no;
InfoType info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int vexnum,arcnum;
VertexType vexs[MAXV];
}MGraph;
typedef struct ANode
{
int adjvex;
struct ANode *nextarc;
InfoType info;
}ArcNode;
typedef int Vertex;
typedef struct Vnode
{
Vertex data;
ArcNode *firstarc;
}VNode;
typedef VNode AdjList[MAXV];
typedef struct
{
AdjList adjlist;
int n,e;
}ALGraph;
void MatToList(MGraph g,ALGraph *&G)//矩阵转化为邻接表
{
int i,j,n=g.vexnum;//n顶点数
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
for(i=0;i <n;i++)G-> adjlist[i].firstarc=NULL;//邻接表所有头结点指针域赋初值
for(i=0;i <n;i++)
for(j=n-1;j> =0;j--)
if(g.edges[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode));
p-> adjvex=j;
p-> info=g.edges[i][j];//存边的权值
p-> nextarc=G-> adjlist[i].firstarc;//将*p链接
G-> adjlist[i].firstarc=p;
}
G-> n=n;
G-> e=g.arcnum;
}
void DispAdj(ALGraph *G)//输出邻接表
{
int i;
ArcNode *p;
for(i=0;i <G-> n;i++)
{
p=G-> adjlist[i].firstarc;
if(p!=NULL) printf( "%3d ",i);
while(p!=NULL)//处理所有相邻顶点
{
printf( "%3d ",p-> adjvex);
p=p-> nextarc;
}
printf( "\n ");
}
}
int visited[MAXV]; //全局数组
void DFS(ALGraph *G,int v)//递归深度优先
{
ArcNode *p;
visited[v]=1;//已访问标记
printf( "%3d ",v);//输出被访问顶点编号
p=G-> adjlist[v].firstarc;//p指向顶点v第一条弧的弧头结点
while(p!=NULL)
{
if(visited[p-> adjvex]==0)//若p-> adjvex顶点未访问,递归访问
DFS(G,p-> adjvex);
p=p-> nextarc;//指向下一条弧
}
}
void DFS1(ALGraph *G,int v)//非递归深度优先
{
int i,visited[MAXV],St[MAXV],top=-1;
ArcNode *p;
for(i=0;i <G-> n;i++) visited[i]=0;
printf( "3d ",v);//访问顶点
top++;//v入栈
St[top]=v;
visited[v]=1;
while(top> =-1)//栈不空时循环
{
v=St[top];//取栈顶顶点
top--;
p=G-> adjlist[v].firstarc;
while(p!=NULL&&visited[p-> adjvex]==1) p=p-> nextarc;
if(p==NULL) top--;
else{
v=p-> adjvex;
printf( "3d ",v);
visited[v]=1;
top++;
St[top]=v;
}
}
printf( "\n ");
}
void BFS(ALGraph *G,int v)//广度优先
{
ArcNode *p;
int queue[MAXV],front=0,rear=0;//循环队列初始化
int visited[MAXV];//存顶点数组
int w,i;
for(i=0;i <G-> n;i++) visited[i]=0;
printf( "3d ",v);//访问顶点
visited[v]=1;//标记访问过
rear=(rear+1)%MAXV;
queue[rear]=v;//进队
while(front!=rear)
{
front=(front+1)%MAXV;
w=queue[front];//出队
p=G-> adjlist[w].firstarc;//找与w邻接的第一个顶点
while(p!=NULL)
{
if(visited[p-> adjvex]==0)//未被访问
{
printf( "%3d ",p-> adjvex);//访问邻接顶点
visited[p-> adjvex]=1;
rear=(rear+1)%MAXV;
queue[rear]=p-> adjvex;
}
p=p-> nextarc;
}
}
printf( "\n ");
}
void main ()
{
int i,j;
MGraph g;
ALGraph *G;
int A[MAXV][6]={
{0,5,0,7,0,0},
{0,0,4,0,0,0},
{8,0,0,0,0,9},
{0,0,5,0,0,6},
{0,0,0,5,0,0},
{3,0,0,0,1,0}};
g.vexnum=6;
g.arcnum=10;
for(i=0;i <g.vexnum;i++)
for(j=0;j <g.vexnum;j++)
g.edges[i][j]=A[i][j];
G=(ALGraph *)malloc(sizeof(ALGraph));
MatToList(g,G);
printf( "邻接表:\n ");
DispAdj(G);
printf( "递归深度优先:\n ");
DFS(G,0);
printf( "\n ");
printf( "非递归深度优先:\n ");
DFS1(G,0);
printf( "\n ");
printf( "广度优先:\n ");
BFS(G,0);
printf( "\n ");
}
[解决办法]
强人啊，帮顶了...
[解决办法]
void MatToList(MGraph g,ALGraph *&G）
//ALGraph *&G这里是什么定义法？应该是这样吧：ALGraph *G
[解决办法]
其实只要调试一下该程序就好了。
[解决办法]
书上有啊
我用stl vector写了个你要不?
