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

7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶

点vi到顶点vj的路径(i≠j)。注意：

算法中涉及

的图的基本操作必须在此存储结构上实现。

实现下列函数：

Status DfsReachable(ALGraph g, int i, int j);

/* Judge if it exists a path from vertex 'i' to*/

/* vertex 'j' in digraph 'g'.*/

/* Array 'visited[]' has been initialed to 'false'.*/

图的邻接表以及相关类型和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

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;

Status DfsReachable(ALGraph g, int i, int j)

/* Judge if it exists a path from vertex 'i' to*/

/* vertex 'j' in digraph 'g'.*/

/* Array 'visited[]' has been initialed to 'false'.*/{int k; ArcNode *p;

visited[i]=1;

for(p=g.vertices[i].firstarc;p;p=p->nextarc){if(p){k=p->adjvex; if(k==j)return 1;

if(visited[k]!=1)

if(DfsReachable(g,k,j))return 1;}}

return 0;}

7.23③同

7.22题要求。试基于图的广度优先搜索策略写一算法。实现下列函数：

Status BfsReachable(ALGraph g, int i, int j);

/* Determine whether it exists path from vertex i to */

/* vertex j in digraph g with Breadth_First Search.*/

/* Array 'visited' has been initialed to 'false'.*/

图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM];

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;

Status InitQue(Que &q);

Status EnQue(Que &q, int e);

Status DeQue(Que &q, int &e);

Status QueEmpty(Que q);

Status GetFront(Que q, int &e);

Status BfsReachable(ALGraph g, int i, int j)

/* Determine whether it exists path from vertex i to */

/* vertex j in digraph g with Breadth_First Search.*/

/* Array 'visited' has been initialed to 'false'.*/{Que q;

int k,n;

ArcNode *p;

InitQue(q);

EnQue(q,i);

while(!QueEmpty(q)){DeQue(q,k);

visited[k]=1;

for(p=g.vertices[k].firstarc;p;p=p->nextarc){n=p->adjvex;

if(n==j)return 1;

if(visited[n]!=1)EnQue(q,n);}}

return 0;}

7.24③试利用栈的基本操作编写，按深度优先搜索策略

遍历一个强连通图的非递归形式的算法。算法中不规定具

体的存储结构，而将图Graph看成是一种抽象的数据类型。实现下列函数：

void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType)); /* Travel the digraph 'dig' with Depth_First Search. */

图以及相关类型、函数和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

int LocateVex(Graph g, VertexType v);

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的简单路径的算法。

实现下列函数：

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);

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.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;

} ALGraph;

int LocateVex(Graph g, VertexType v);

void inpath(char *path, VertexType v);

/* Add vertex 'v' to 'path' */

void depath(char *path, VertexType v);

/* Remove vertex 'v' from 'path' */

void AllPath2(ALGraph g, VertexType sv, VertexType tv, StrARR &path, int &i,int &d,VertexType A[])

{ int j,k,l,m,n;

ArcNode *p;

j=LocateVex(g,sv);

visited[j]=1;

A[d++]=sv;

if(sv==tv){m=0;

for(n=0;n

path[i][m++]=A[n];

i++;}else

for(p=g.vertices[j].firstarc;p;p=p->nextarc){l=p->adjvex;

if(!visited[l])

AllPath2(g,g.vertices[l].data,tv,path,i,d,A);}visited[j]=0;

d--;}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*/{int d=0,j,l;

VertexType A[MAX_VERTEX_NUM],B[MAX_VERTEX_NUM];

for(l=0;l<5;l++){strcpy(B,path[l]);

for(j=0;j

depath(path[l],B[j]);}AllPath2(g,sv,tv,path,i,d,A);}

7.31③试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。

实现下列函数：

void StronglyConnected(OLGraph dig, StrARR &scc, int &n);

/* and put the ith into scc[i] which is a string.*/

图的十字链表以及相关类型和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

int finished[MAX_VERTEX_NUM];

typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]; //记录各强连通分量typedef struct ArcBox {

int tailvex,headvex;

struct ArcBox *hlink,*tlink;

} ArcBox;

typedef struct VexNode {

VertexType data;

ArcBox*firstin,*firstout;

} VexNode;

typedef struct {

VexNode xlist[MAX_VERTEX_NUM];

} OLGraph;

int count;

void DFS1(OLGraph dig,int v);

void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k);

void StronglyConnected(OLGraph dig, StrARR &scc, int &n) /* and put the ith into scc[i] which is a string.*/{int i,k=0,v; count=0;

for(v=0;v

if(!visited[v])

DFS1(dig,v);

for(v=0;v

visited[v]=0;

for(i=dig.vexnum-1;i>=0;i--){v=finished[i];

if(!visited[v]){DFS2(dig,v,scc,n,k);

n++;}}}void DFS1(OLGraph dig,int v){int w;

ArcBox *p;

visited[v]=1;

for(p=dig.xlist[v].firstout;p;p=p->tlink)

{w=p->headvex;

if(!visited[w])

DFS1(dig,w);}finished[count++]=v;}void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k){int w;

ArcBox *p;

visited[v]=1;

scc[j][k++]=dig.xlist[v].data;

for(p=dig.xlist[v].firstin;p;p=p->hlink){w=p->tailvex;

if(!visited[w])

DFS2(dig,w,scc,j,k);}}

7.29⑤试写一个算法，在以邻接矩阵方式存储的

有向图G中求顶点i到顶点j的不含回路的、长度为k

的路径数。

实现下列函数：

int SimplePath(MGraph G, int i, int j, int k);

/*求有向图G的顶点i到j之间长度为k的简单路径条数*/

图的邻接矩阵存储结构的类型定义如下：

typedef enum {DG,DN,AG,AN} GraphKind; //有向图,有向网,无向图,无向网

typedef struct {

VRType adj; //顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；

//对带权图，则为权值类型

InfoType *info; //该弧相关信息的指针(可无)

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {

AdjMatrixarcs; //邻接矩阵

VertexType vexs[MAX_VERTEX_NUM]; //顶点向量

GraphKindkind; //图的种类标志

}MGraph;

int SimplePath(MGraph G, int i, int j, int k)

/*求有向图G的顶点i到j之间长度为k的简单路径条数*/{int sum=0,v; if( G.arcs[i][j].adj &&k==1 && !visited[j])

sum=1;

else

if(k>1)

{visited[i]=1;

for(v=0;v

sum+=SimplePath(G,v,j,k-1);}visited[i]=0;}return sum;}实现下列函数：

int Search(SSTable s, KeyType k);

/* Index the element which key is k */

/* in StaticSearchTable s.*/

/* Return 0 if x is not found.*/

静态查找表的类型SSTable定义如下：

typedef struct {

KeyType key;

... ...//其他数据域

} ElemType;

typedef struct {

ElemType *elem;

intlength;

} SSTable;

int Search(SSTable a, KeyType k)

/* Index the element which key is k*/ /* in StaticSearchTable s.*/

/* Return 0 if x is not found.*/{int i; for(i=1;i<=a.length;i++)

if(a.elem[i].key==k)return i;

return 0;}