7-20 有向图输出入度为0顶点 分数 6 作者 DS课程组 单位 临沂大学 本题要求实现一个函数,输出有向图所有入度为0的顶点。 函数接口定义: void PrintV(MGraph G); G为采用邻接矩阵作为存储结构的有向图。 裁判测试程序样例: #include <stdio.h> #define MVNum 100 //最大顶点数 typedef struct { char vexs[MVNum]; //存放顶点的一维数组 int arcs[MVNum][MVNum]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 }MGraph; void PrintV(MGraph G); void CreatMGraph(MGraph *G);/* 创建图 */ int main() { MGraph G; CreatMGraph(&G); PrintV(G); return 0; } void CreatMGraph(MGraph *G) { int i, j, k; scanf("%d%d", &G->vexnum, &G->arcnum); getchar(); for (i = 0; i < G->vexnum; i++) scanf("%c", &G->vexs[i]); for (i = 0; i < G->vexnum; i++) for (j = 0; j < G->vexnum; j++) G->arcs[i][j] = 0; for (k = 0; k < G->arcnum; k++) { scanf("%d%d", &i, &j); G->arcs[i][j] = 1; } } /* 你的代码将被嵌在这里 */ 输入样例: 例如有向图 有向图.png 第一行给出图的顶点数n和弧数e。第二行给出n个字符,表示n个顶点的数据元素的值。后面是e行,给出每一条弧的两个顶点编号。 4 5 ABCD 1 0 2 0 2 1 3 2 3 1 输出样例: 输出为两行,第一行为入度为0的顶点个数,第二行按照输入顺序输出所有入度为0的顶点元素值。顶点的元素值为字符型,输出格式为每个字符后面跟一个空格。如果没有入度为0的顶点,则输出只有一行,个数为0。 1 D
时间: 2023-12-03 18:44:41 浏览: 114
思路:遍历每个顶点,统计其入度,入度为0则输出。为了方便输出入度为0的顶点的元素值,可以开一个数组记录每个顶点的元素值。
代码实现:
```c++
void PrintV(MGraph G) {
int inDegree[MVNum] = {0}; // 入度数组
char elem[MVNum]; // 元素值数组
int idx = 0; // 元素值数组下标
for (int i = 0; i < G.vexnum; i++) {
for (int j = 0; j < G.vexnum; j++) {
if (G.arcs[j][i]) { // 统计入度
inDegree[i]++;
}
}
if (inDegree[i] == 0) { // 入度为0
elem[idx++] = G.vexs[i];
}
}
printf("%d\n", idx); // 输出入度为0的顶点个数
for (int i = 0; i < idx; i++) {
printf("%c ", elem[i]); // 输出入度为0的顶点元素值
}
}
```
相关问题
7-1 入度与出度分数 10作者 黄龙军单位 绍兴文理学院求有向图g中各顶点的入度与出
有向图中,每个顶点有两个相关的度数,即入度和出度。
入度表示指向该顶点的边的数量,而出度表示从该顶点出发的边的数量。
假设有向图g有n个顶点,则每个顶点的入度与出度可以用两个n维向量来表示。
设向量D表示每个顶点的入度,向量O表示每个顶点的出度,则有:
D = [d1, d2, ..., dn],O = [o1, o2, ..., on]
其中,di表示第i个顶点的入度,oi表示第i个顶点的出度。
通过遍历每个顶点,可以计算出它们的入度和出度。
具体计算方法如下:
1. 初始化D和O为长度为n的全0向量。
2. 遍历有向图g的每个边,若边的起点是i,终点是j,则将D的第j个元素增加1(即dj = dj + 1),将O的第i个元素增加1(即oi = oi + 1)。
3. 遍历完成后,得到了每个顶点的入度和出度。
举个例子,假设有向图g有4个顶点,边的表示如下:
1 -> 2
1 -> 3
2 -> 3
3 -> 4
则有:
D = [0, 2, 2, 1]
O = [0, 1, 2, 1]
其中,顶点1的入度为0,出度为2;顶点2的入度为2,出度为1;顶点3的入度为2,出度为2;顶点4的入度为1,出度为1。
通过计算每个顶点的入度和出度,可以帮助我们更好地理解有向图的结构,并在分析图的特性和性质时提供参考依据。
编写程序,计算含有5个顶点的有向图的入度和出度,输出每个顶点的入度和出度。
### 回答1:
以下是一个示例程序,可以计算有向图的入度和出度:
```python
# 定义有向图的邻接矩阵
graph = [[0, 1, 0, 0, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, 1],
[1, 0, 0, 0, 0]]
# 计算每个顶点的入度和出度
in_degree = [0] * 5
out_degree = [0] * 5
for i in range(5):
for j in range(5):
if graph[i][j] == 1:
out_degree[i] += 1
in_degree[j] += 1
# 输出结果
for i in range(5):
print("Vertex {}: in_degree = {}, out_degree = {}".format(i, in_degree[i], out_degree[i]))
```
这个程序输出的结果如下:
```
Vertex 0: in_degree = 1, out_degree = 1
Vertex 1: in_degree = 1, out_degree = 1
Vertex 2: in_degree = 1, out_degree = 1
Vertex 3: in_degree = 2, out_degree = 0
Vertex 4: in_degree = 0, out_degree = 2
```
其中,顶点0、1、2的入度和出度均为1,顶点3的入度为2,出度为0,顶点4的入度为0,出度为2。
### 回答2:
要编写程序来计算含有5个顶点的有向图的入度和出度,并输出每个顶点的入度和出度。我们可以使用邻接矩阵来表示有向图,其中矩阵的行表示起始顶点,列表示目标顶点。如果存在从起始顶点到目标顶点的边,则对应位置上的值为1,否则为0。
下面是一个示例程序:
```python
import numpy as np
# 定义有向图的邻接矩阵
adjacency_matrix = np.array([[0, 0, 1, 1, 1],
[1, 0, 1, 0, 1],
[0, 0, 0, 1, 0],
[0, 1, 1, 0, 0],
[0, 0, 0, 0, 0]])
num_vertices = 5 # 顶点数量
# 计算入度
indegrees = np.sum(adjacency_matrix, axis=0)
# 计算出度
outdegrees = np.sum(adjacency_matrix, axis=1)
# 输出每个顶点的入度和出度
for i in range(num_vertices):
print("顶点", i+1, "的入度为:", indegrees[i])
print("顶点", i+1, "的出度为:", outdegrees[i])
```
运行上述程序,将会输出每个顶点的入度和出度:
```
顶点 1 的入度为: 1
顶点 1 的出度为: 3
顶点 2 的入度为: 1
顶点 2 的出度为: 3
顶点 3 的入度为: 2
顶点 3 的出度为: 1
顶点 4 的入度为: 2
顶点 4 的出度为: 2
顶点 5 的入度为: 2
顶点 5 的出度为: 0
```
这样,我们就可以通过编写程序来计算有向图的入度和出度,并输出每个顶点的结果了。
### 回答3:
假设我们有一个5个顶点的有向图,可以使用邻接矩阵来表示该图。邻接矩阵是一个5x5的矩阵,其中的元素表示顶点之间是否有边连接。对于有向图,邻接矩阵的元素可以表示从行对应的顶点到列对应的顶点是否有边连接。
首先,我们需要创建一个5x5的邻接矩阵,并将所有元素初始化为0。然后,根据图的连接情况,将对应的元素设置为1,表示有边连接。
然后,我们可以遍历邻接矩阵的每一列来计算每个顶点的入度和出度。对于每一列,计算其中1的个数,即表示有多少个顶点与该顶点有边连接,这就是该顶点的入度。同时,计算每一行中1的个数,即表示该顶点有多少条边与其他顶点连接,这就是该顶点的出度。
最后,输出每个顶点的入度和出度。
以下是一个简单的Python程序示例:
```python
matrix = [[0]*5 for _ in range(5)] # 创建一个5x5的邻接矩阵
# 设置邻接矩阵中的元素,表示顶点之间的边连接情况
matrix[0][1] = 1
matrix[1][2] = 1
matrix[2][0] = 1
matrix[3][4] = 1
matrix[4][3] = 1
indegree = [0]*5 # 入度列表,初始化为0
outdegree = [0]*5 # 出度列表,初始化为0
# 计算入度和出度
for col in range(5):
for row in range(5):
if matrix[row][col] == 1:
indegree[col] += 1
if matrix[col][row] == 1:
outdegree[col] += 1
# 输出每个顶点的入度和出度
for i in range(5):
print(f"顶点{i}的入度为{indegree[i]},出度为{outdegree[i]}")
```
这个程序将输出:
```
顶点0的入度为1,出度为1
顶点1的入度为1,出度为1
顶点2的入度为1,出度为1
顶点3的入度为1,出度为1
顶点4的入度为1,出度为1
```
这表明了该有向图中每个顶点的入度和出度均为1。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.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)