( 20分 ) 已知图以邻接矩阵作为存储结构,编写算法判断两个指定顶点之间是否存在路径。
时间: 2024-03-22 16:37:35 浏览: 26
可以使用深度优先搜索(DFS)或广度优先搜索(BFS)算法来判断两个指定顶点之间是否存在路径。以下是使用DFS算法的伪代码:
```
bool isPathExists(int start, int end, bool visited[], int graph[][MAX_SIZE]) {
if (start == end) {
return true;
}
visited[start] = true;
for (int i = 0; i < MAX_SIZE; i++) {
if (graph[start][i] && !visited[i]) {
if (isPathExists(i, end, visited, graph)) {
return true;
}
}
}
return false;
}
bool hasPath(int start, int end, int graph[][MAX_SIZE]) {
bool visited[MAX_SIZE] = {false};
return isPathExists(start, end, visited, graph);
}
```
其中,`graph`是邻接矩阵,`MAX_SIZE`是顶点的最大数量。`hasPath`函数是判断两个指定顶点`start`和`end`之间是否存在路径的接口函数,返回值为布尔类型。首先创建一个`visited`数组,用于记录顶点是否已经被访问。然后调用`isPathExists`函数,该函数递归地遍历图中与起点`start`相邻的所有顶点,如果遇到终点`end`,则返回`true`,否则继续遍历。如果所有与起点`start`相邻的顶点都被访问过,仍未找到终点`end`,则返回`false`。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)