不知道是不是出了逻辑错误，遍历不了，求关注
程序代码：/*
*图的深度优先搜索
*/
#include<stdio.h>//EOF(=^Z或F6),NULL
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 5//顶点字符串的最大长度+1
#define MAX_INFO 20//相关信息字符串的最大长度+1
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
typedef int Boolean;
#define MAX_VEX_NUM 20
typedef struct
{
VRType adj;//顶点关系类型
InfoType *info;//该弧相关信息的指针
}ArcCell,AdjMatrix[MAX_VEX_NUM][MAX_VEX_NUM];
typedef struct
{
VertexType vexs[MAX_VEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;//当前顶点数和弧数
}MGraph;
/* 初始条件:图G存在,u和G中顶点有相同特征 */
/* 操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */
int getLocateVex(MGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vexs[i])==0)
return i;
return 1;
}
/* 采用数组(邻接矩阵)表示法,构造无向图G */
int createUDG(MGraph *G)
{
int i,j,k,l,IncInfo;
char s[MAX_INFO],*info;
VertexType va,vb;
printf("请输入无向图G的顶点数，边数，边是否含有其他信息(是:1,否:0)");
scanf("%d%d%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf("请输入%d个顶点的值(<%d个字符)",(*G).vexnum,MAX_NAME);
for(i=0;i<(*G).vexnum;++i)//构造顶点向量
scanf("%s",(*G).vexs[i]);
for(i=0;i<(*G).vexnum;++i)
for(j=0;j<(*G).vexnum;++j)
{
(*G).arcs[i][j].adj=0;
(*G).arcs[i][j].info=NULL;
}
printf("请输入%d条边的顶点1 顶点2(以空格作为间隔):\n",(*G).arcnum);
for(k=0;k<(*G).arcnum;++k)
{
scanf("%s%s%*c",va,vb);//%*c吃掉回车符
i=getLocateVex(*G,va);
j=getLocateVex(*G,vb);
(*G).arcs[i][j].adj=(*G).arcs[j][i].adj=1;//无向图
if(IncInfo)
{
printf("请输入该边的相关信息(<%d个字符):",MAX_INFO);
gets(s);
l=strlen(s);
if(l)
{
info=(char *)malloc((l+1)*sizeof(char));
strcpy(info,s);
(*G).arcs[i][j].info=(*G).arcs[j][i].info=info;//无向图
}
}
}
return 1;
}
/* 初始条件: 图G存在，v是G中某个顶点的序号。操作结果: 返回v的值 */
VertexType* GetVex(MGraph G,int v)
{
if(v>=G.vexnum||v<0)
exit(0);
return &G.vexs[v];
}
/* 初始条件: 图G存在,v是G中某个顶点 */
/* 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1 */
int FirstAdjVex(MGraph G,VertexType v)
{
int i,j=0,k;
k=getLocateVex(G,v);
for(i=0;i<G.vexnum;i++)//k为顶点v在图G中的序号
if(G.arcs[k][i].adj!=j)
return i;
return -1;
}
/* 初始条件: 图G存在,v是G中某个顶点,w是v的邻接顶点 */
/* 操作结果: 返回v的(相对于w的)下一个邻接顶点的序号, */
/* 若w是v的最后一个邻接顶点,则返回-1 */
int NextAdjVex(MGraph G,VertexType v,VertexType w)
{
int i,j=0,k1,k2;
k1=getLocateVex(G,v);//k1为顶点v在图G中的序号
k2=getLocateVex(G,w);//k2为顶点w在图G中的序号
for(j=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=j)
return i;
return 1;
}
Boolean visited[MAX_VEX_NUM];//访问标志数组
int (*VisitFunc)(VertexType);//函数变量
/* 从第v个顶点出发递归地深度优先遍历图G*/
void DFS(MGraph G,int v)
{
VertexType w1,v1;
int w;
visited[v]=1;//设访问标志为已访问
VisitFunc(G.vexs[v]);//访问第v个顶点
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,*GetVex(G,w))))
if(!visited[w])
DFS(G,w);//对v的尚未访问的序号为w的邻接顶点递归调用DFS
}
/* 初始条件: 图G存在,Visit是顶点的应用函数。*/
/* 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit */
/* 一次且仅一次。一旦Visit()失败,则操作失败 */
void DFSTraverse(MGraph G,int(*Visit)(VertexType))
{
int v;
VisitFunc=Visit;//使用全局变量VisitFunc，使DFS不必设函数指针参数
for(v=0;v<G.vexnum;v++)
visited[v]=0;//访问数组初始化(未访问)
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v);//对未访问的顶点调用DFS
printf("\n\n");
}
int visit(VertexType v)
{
printf("%s ",v);
return 1;
}
int main()
{
MGraph G;
createUDG(&G);
printf("图的优先深度搜索:");
DFSTraverse(G,visit);
return 0;
}
[ 本帖最后由 世界模型 于 2011-8-8 18:46 编辑 ]
