采用邻接矩阵存储结构,构造有向带权图,并求各顶点的入度和出度。用数据结构代码实现
时间: 2024-03-12 19:46:09 浏览: 70
用邻接矩阵作存储结构的图类
4星 · 用户满意度95%
好的,我可以给你提供一个用 Python 语言实现的代码示例,来构造有向带权图并求各顶点的入度和出度。
```python
# 定义邻接矩阵存储有向带权图
class WeightedGraph:
def __init__(self, vertices):
self.V = vertices
self.graph = [[0] * self.V for i in range(self.V)]
def add_edge(self, u, v, w):
self.graph[u][v] = w
def print_graph(self):
for i in range(self.V):
for j in range(self.V):
print("{:>4}".format(self.graph[i][j]), end=" ")
print()
def get_indegree(self, v):
indegree = 0
for i in range(self.V):
if self.graph[i][v] != 0:
indegree += 1
return indegree
def get_outdegree(self, v):
outdegree = 0
for j in range(self.V):
if self.graph[v][j] != 0:
outdegree += 1
return outdegree
# 构造一个有向带权图示例并计算各顶点的入度和出度
g = WeightedGraph(4)
g.add_edge(0, 1, 4)
g.add_edge(1, 2, 2)
g.add_edge(1, 3, 3)
g.add_edge(2, 3, 5)
g.print_graph()
print("节点 0:入度", g.get_indegree(0), ",出度", g.get_outdegree(0))
print("节点 1:入度", g.get_indegree(1), ",出度", g.get_outdegree(1))
print("节点 2:入度", g.get_indegree(2), ",出度", g.get_outdegree(2))
print("节点 3:入度", g.get_indegree(3), ",出度", g.get_outdegree(3))
```
在这个示例代码中,我们首先定义了一个 `WeightedGraph` 类来表示有向带权图,其中包含了图的节点数 `V` 和邻接矩阵 `graph`。然后,我们定义了 `add_edge` 方法来向图中添加有向边,并且定义了 `print_graph` 方法来打印邻接矩阵。
接下来,我们定义了 `get_indegree` 和 `get_outdegree` 方法来计算图中每个节点的入度和出度。这两个方法的实现方式与前面所述的计算方法是一致的。
最后,我们构造了一个有向带权图示例,并计算了各顶点的入度和出度。你可以根据这个示例代码来更好地理解有向带权图的存储和计算方式。
阅读全文