内容发布更新时间 : 2024/12/23 4:47:19星期一 下面是文章的全部内容请认真阅读。
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; 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 { VertexType 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, VertexType 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 { VertexType 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 */