有一个邻接表存储的图G,分别设计实现以下要求的算法:求出图中每个顶点的出度;计算图中出度为0的顶点数。
时间: 2023-12-14 18:39:16 浏览: 80
图算法设计题
求出图中每个顶点的出度的算法可以使用邻接表表示法来实现。遍历每个顶点的邻接表,统计其中的元素个数即为该顶点的出度。具体步骤如下:
1. 初始化一个长度为n的数组outDegree,其中n为图中顶点的个数,将每个元素初始化为0。
2. 对于每个顶点i,遍历它的邻接表,统计其中的元素个数,将个数赋值给outDegree[i]。
以下是Python代码实现:
```python
def get_out_degree(adj_list):
n = len(adj_list)
out_degree = [0] * n
for i in range(n):
out_degree[i] = len(adj_list[i])
return out_degree
```
计算图中出度为0的顶点数的算法也可以使用邻接表表示法来实现。遍历邻接表,统计出度为0的顶点个数即可。具体步骤如下:
1. 初始化一个变量count为0。
2. 对于每个顶点i,遍历它的邻接表,如果邻接表为空,则将count加1。
以下是Python代码实现:
```python
def count_zero_out_degree_vertices(adj_list):
count = 0
for adj in adj_list:
if len(adj) == 0:
count += 1
return count
```
注意:以上代码都是基于邻接表表示法实现的。如果使用其他表示方法,可能需要不同的实现方式。
阅读全文