试写一算法,判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径(i-->j)。 【输入形式】 顶点个数:n 边的条数:m 边的有向顶点对: (a,b)…… 待判断定点i,j
时间: 2024-05-04 13:19:32 浏览: 82
采用连接表存储有向图,设计算法判断任意两个顶点间是否存在路径.doc
可以使用深度优先搜索(DFS)算法来判断两个顶点之间是否存在路径。具体实现方式如下:
1. 初始化一个布尔型数组visited,表示每个顶点是否已经被访问过,将所有元素均初始化为false。
2. 从起点i开始进行深度优先搜索,递归地访问与i相邻的所有未被访问过的顶点。
3. 在递归过程中,如果访问到了目标顶点j,则说明i到j之间存在路径,返回true。
4. 如果遍历完所有与i相邻的顶点后,仍未找到目标顶点j,则返回false。
下面是具体的实现代码(假设邻接表已经存储在变量adjList中):
```python
def hasPath(adjList, i, j):
n = len(adjList)
visited = [False] * n
def dfs(node):
visited[node] = True
if node == j:
return True
for neighbor in adjList[node]:
if not visited[neighbor]:
if dfs(neighbor):
return True
return False
return dfs(i)
```
其中,dfs函数表示从当前节点开始进行深度优先搜索,并返回是否找到目标节点。在dfs函数内部,首先将当前节点标记为已访问,然后依次访问所有与当前节点相邻的未被访问过的节点。如果在这个过程中找到了目标节点j,则直接返回True;否则,最终返回False。在主函数中,直接调用dfs(i)即可判断从顶点i到顶点j是否存在路径。
阅读全文