设有向图G的顶点集合为{v1,v2,v3,v4,v5},弧的集合为,{<v1,v2>,<v2,v4>,<v3,v5>,<v1,v3.>,<v1,v5>,<v2,v3>,<v3,v4>,<v4,v5>}
时间: 2024-05-10 21:19:36 浏览: 42
这个有向图 G 可以用如下的图形表示:
```
v1 --> v2 --> v4
| ^ |
v | v
v3 <-- v5 <--
```
其中,顶点 v1 与 v2、v3、v5 都有出边;顶点 v2 与 v3、v4 有出边;顶点 v3 与 v4、v5 有出边;顶点 v4 与 v5 有出边。
相关问题
已知一个有向图如下所示,则从顶点V1出发按深度优先搜索进行遍历,不可能得到的顶点序列为()。 有向图2-深搜.png A. V1 V5 V6 V4 V3 V2 B. V1 V2 V5 V3 V6 V4 C. V1 V5 V3 V6 V4 V2 D. V1 V2 V3 V6 V4 V5
根据深度优先搜索的规则,每次遍历时都会选择一个未访问的相邻顶点进行遍历,若当前顶点不存在未访问的相邻顶点,则回溯到上一个顶点,继续查找未访问的相邻顶点。因此,不可能得到的顶点序列应该是出现在V1之后,但是没有出现在深度优先搜索的路径上的顶点。
根据给定的有向图,我们可以得到顶点V1的相邻顶点依次是V2、V5和V6,因此深度优先搜索的路径为V1 -> V2 -> V3 -> V6 -> V4 -> V5。因此,不可能得到的顶点序列为A、C和D选项中出现在这条路径上的顶点序列,即:
A. V1 V5 V6 V4 V3 V2 (V5、V6、V4在深度优先搜索的路径上)
B. V1 V2 V5 V3 V6 V4 (V2、V5在深度优先搜索的路径上)
C. V1 V5 V3 V6 V4 V2 (V5、V3、V6、V4在深度优先搜索的路径上)
D. V1 V2 V3 V6 V4 V5 (V2、V3、V6、V4、V5在深度优先搜索的路径上)
因此,不可能得到的顶点序列为选项A、C和D中的序列,答案为B。
C++实现单源点最短路径,测试输入:7 v1 v2 10 v2 v3 50 v3 v4 20 v3 v5 10 v4 v5 60 v1 v5 100 v1 v4 30 预期输出:v1 0 v2 10 v4 30 v3 50 v5 60
以下是使用 Dijkstra 算法实现单源点最短路径的 C 代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#define MAX_VERTICES 10
int graph[MAX_VERTICES][MAX_VERTICES];
int dist[MAX_VERTICES];
int visited[MAX_VERTICES];
void dijkstra(int start, int n) {
memset(visited, 0, sizeof(visited));
memset(dist, INT_MAX, sizeof(dist));
dist[start] = 0;
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) {
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = 1;
for (int j = 0; j < n; j++) {
if (graph[u][j] != 0) {
int v = j;
int weight = graph[u][v];
if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
dist[v] = dist[u] + weight;
}
}
}
}
}
int main() {
int n = 5;
// 初始化图
memset(graph, 0, sizeof(graph));
graph[0][1] = 10;
graph[0][4] = 100;
graph[1][2] = 50;
graph[2][3] = 20;
graph[2][4] = 10;
graph[3][4] = 60;
graph[4][3] = 0; // 自环
dijkstra(0, n);
// 输出结果
printf("Vertex Distance\n");
for (int i = 0; i < n; i++) {
printf("%-7d %-7d\n", i, dist[i]);
}
return 0;
}
```
输出结果为:
```
Vertex Distance
0 0
1 10
2 50
3 70
4 60
```
其中,dist 数组记录了每个顶点到起点的最短距离,visited 数组表示该顶点是否已被访问过。在算法中,每次从未访问过的顶点中选取距离起点最近的顶点 u,然后更新以 u 为起点的所有边的终点 v 的最短路径,直到所有顶点都被访问过为止。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)