一、判断路径是否存在
判断有向图 $G$ 中是否存在从 $s$ 顶点到 $t$ 顶点的路径。
如果从 $s$ 到 $t$ 的路径存在,则从 $s$ 出发进行遍历,必能搜索到 $t$ ,且一旦访问到 $t$ ,则遍历终止。此问题采用深度优先遍历和广度优先遍历均可。
基于连通图的深度优先遍历
Status isReachable_DFS(MGraph G, int s, int t)
{ //判断有向图G中是否存在从顶点s到t的路径,图G采用邻接数组存储结构
int i;
Status found = FALSE; //标识是否找到终点t
G.tags[s] = VISITED;
if (s == t) return TRUE; //一旦遇到终点t,则遍历终止
for (i = FirstAdjVex_M(G, s); i >= 0 && FALSE == found; i = NextAdjVex_M(G, s, i))
{
if (G.tags[i] == UNVISTTED)
found = isReachable_DFS(G, i, t); //保存查找结果
}
return found;
}
标签:遍历,int,路径,有向图,应用,二十四,found,顶点 From: https://www.cnblogs.com/haibersut/p/16891495.html