试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i<>j)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。
时间: 2023-06-05 18:48:02 浏览: 145
采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径.doc
算法如下:
1. 初始化一个布尔型数组visited,用于记录每个顶点是否被访问过,初始值为false。
2. 从顶点vi开始,调用深度优先搜索函数dfs(vi, vj)。
3. 在dfs函数中,首先将当前顶点vi标记为已访问,即visited[vi] = true。
4. 然后遍历vi的所有邻接点,如果邻接点vj被访问过,则说明存在从vi到vj的路径,直接返回true。
5. 如果邻接点vj未被访问过,则递归调用dfs函数,传入邻接点vj作为参数。
6. 如果在遍历完所有邻接点后仍未找到从vi到vj的路径,则返回false。
完整算法代码如下:
bool visited[MAX_VERTEX_NUM]; // MAX_VERTEX_NUM为顶点数的最大值,需根据实际情况调整
bool dfs(ALGraph G, int vi, int vj) {
visited[vi] = true;
for (ArcNode* p = G.vertices[vi].firstarc; p != NULL; p = p->nextarc) {
int w = p->adjvex;
if (w == vj) {
return true;
}
if (!visited[w]) {
if (dfs(G, w, vj)) {
return true;
}
}
}
return false;
}
bool hasPath(ALGraph G, int vi, int vj) {
memset(visited, false, sizeof(visited));
return dfs(G, vi, vj);
}
阅读全文