发布时间 : 星期六 文章数据结构作业系统 - 第七章答案更新完毕开始阅读
VertexType GetVex(Graph g, int i); int FirstAdjVex(Graph g, int v); int NextAdjVex(Graph g, int v, int w); void visit(char v);
Status InitStack(SStack &s);
Status Push(SStack &s, SElemType x); Status Pop(SStack &s, SElemType &x); Status StackEmpty(SStack s);
Status GetTop(SStack s, SElemType &e); void Traverse(Graph dig,VertexType v0, void
(*visit)(VertexType)){inti,v,flag;SStack s;VertexType p;//flag来记录某点还有没有邻接点InitStack(s);
{i=LocateVex(dig,v0);visited[i]=TRUE;visit(v0);Push(s,v0); while(!StackEmpty(s))
{GetTop(s,p);v=LocateVex(dig,p);flag=0;
for(i=FirstAdjVex(dig,v);i>=0;i=NextAdjVex(dig,v,i)) { if(!visited[i]) {p=GetVex(dig,i); flag=1; break;}} if(flag)
{visit(p);visited[i]=TRUE; Push(s,p);}else{Pop(s,p); }}}}
7.27④采用邻接表存储结构，编写一个判别无向图中任意给定的 两个顶点之间是否存在一条长度为k的简单路径的算法。
5 / 14
实现下列函数：
Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp);
/* Judge whether it exists a path from sv to tv with length k */ /* in graph g, return path using string sp ifexists.*/ 图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM];
typedef charStrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VNode { VertexType data; ArcNode*firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; } ALGraph;
int LocateVex(Graph g, VertexType v);
6 / 14
void inpath(char *&path, VertexType v); /* Add vertex 'v' to 'path' */
void depath(char *&path, VertexType v); /* Remove vertex 'v' from 'path' */
Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp) /* Judge whether it exists a path from sv to tv with length k */ /* in graph g, return path using string sp ifexists.*/ {int i,j,l; ArcNode *p; if(sv==tv && k==0) { inpath(sp,tv); return OK; }
else{i=LocateVex(g,sv); visited[i]=1; inpath(sp,sv);
for(p=g.vertices[i].firstarc;p;p=p->nextarc){l=p->adjvex; if(!visited[l]){if(SinglePath(g,g.vertices[l].data,tv,k-1,sp)) return OK; else
depath(sp,g.vertices[l].data);}} visited[i]=0;}}
7 / 14
7.28⑤已知有向图和图中两个顶点u和v，试编写算法求 xx中从u到v的所有简单路径。 实现下列函数：
void AllPath(ALGraph g, VertexType sv, VertexType tv, StrARR &path, int &i);
/* Get all the paths from vertex sv to tv, save them */ /* Return the number of path using i*/
图的邻接表以及相关类型、函数和辅助变量定义如下： Status visited[MAX_VERTEX_NUM];
typedef char StrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType; typedef struct ArcNode { int adjvex;
struct ArcNode *nextarc; } ArcNode;
typedef struct VNode { VertexType data; ArcNode*firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices;
8 / 14