数据结构作业系统 - 第七章答案

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