判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)

本文主要是介绍判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。 注意：算法中涉及的图的基本操作必须在此存储结构上实现。

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

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'.*/                       
{ArcNode *p;Queue Q;int e,k;InitQueue(Q);if(!g.vexnum || !g.arcnum)//图的当前顶点数或弧数为0时return ERROR;else{EnQueue(Q,i);while(!QueueEmpty(Q)){DeQueue(Q,e);visited[e] = TRUE;//标记被访问过的顶点p = g.vertices[e].firstarc; for(; p != NULL; p = p -> nextarc){k = p -> adjvex;//当前弧所指向顶点的位置if(k == j) return OK;else if(!visited[k])//当前顶点未被访问过EnQueue(Q,k);}}return ERROR;}
}                                                   

这篇关于判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---