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 {
V ertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} 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 {
V ertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
Status InitQueue(Queue &q);
Status EnQueue(Queue &q, int e);
Status DeQueue(Queue &q, int &e);
Status QueueEmpty(Queue q);
Status GetFront(Queue 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'. */
{
Queue q;
int k,n;
ArcNode *p;
InitQueue(q);
EnQueue(q,i);
while(!QueueEmpty(q))
{
DeQueue(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)EnQueue(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, V ertexType v0, void (*visit)(VertexType))
{
int i,v,flag;SStack s;VertexType p; //flag来记录某点还有没有邻接点InitStack(s);
if(dig.vexnum&&dig.arcnum)
{ 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 if exists. */
图的邻接表以及相关类型、函数和辅助变量定义如下：
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 {
V ertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} 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 if exists. */
{ 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，试编写算法求
有向图中从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 */
/* into Array path which contains string components. */
/* 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 {
V ertexType data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} 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, V ertexType 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 */ /* into Array path which contains string components. */ /* 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); /* Get all the strongly connected components in the digraph dig, */ /* 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 { V ertexType data; ArcBox *firstin,*firstout; } VexNode; typedef struct { V exNode xlist[MAX_VERTEX_NUM]; int vexnum, arcnum; } 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) /* Get all the strongly connected components in the digraph dig, */ /* 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 { AdjMatrix arcs; // 邻接矩阵 V ertexType vexs[MAX_VERTEX_NUM]; // 顶点向量 int vexnum,arcnum; // 图的当前顶点数和弧数 GraphKind kind; // 图的种类标志 }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 { if(G.arcs[i][v].adj && !visited[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; int length; } 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; }
相关主题
文本预览