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

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 Status EnQueue Queue Status DeQueue Queue Status QueueEmpty Queue q Status GetFront Queue q int 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 Status Push SStack Status Pop SStack Status StackEmpty SStack s Status GetTop SStack s SElemType void Traverse Graph dig VertexType v0 void visit VertexType int i v flag SStack s VertexType p flag 来记录某点还有没有邻接点 InitStack s if dig vexnumvisited 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 Add vertex v to path void depath char 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 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 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 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 void AllPath2 ALGraph g VertexType sv VertexType tv StrARR ArcNode p j LocateVex g sv visited j 1 A d sv if sv tv m 0 for n 0 nnextarc 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 VertexType A MAX VERTEX NUM B MAX VERTEX NUM for l 0 l 5 l strcpy B path l for j 0 j strlen path l j depath path l B j AllPath2 g sv tv path i d A 7 31 试完成求有向图的强连通分量的算法 并分析算法的时间复杂度 实现下列函数 void StronglyConnected OLGraph dig StrARR 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 VertexType data ArcBox firstin firstout VexNode typedef struct VexNode xlist MAX VERTEX NUM int vexnum arcnum OLGraph int count void DFS1 OLGraph dig int v void DFS2 OLGraph dig int v StrARR void StronglyConnected OLGraph dig StrARR count 0 for v 0 v dig vexnum v if visited v DFS1 dig v for v 0 v 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 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