在图论的世界里，图是一种用来描述对象及其之间关系的数据结构。而图中的节点（顶点）和边（连接）则构成了复杂的社会网络、交通网络、计算机网络等。今天，我们就来一起探讨如何计算图顶点的度数，这是图论中最基础也是最重要的概念之一。
什么是顶点的度数？
顶点的度数是指与该顶点相连的边的数量。简单来说，就是顶点“认识”的边的数量。在无向图中，每个顶点的度数都是其相连边的数量；而在有向图中，每条进入或离开该顶点的边都计算为该顶点的度数。
计算顶点度数的方法
1. 邻接表法
邻接表是一种表示图的常见方法，特别适用于稀疏图。它由一个数组构成，数组中的每个元素是一个链表，链表中的每个节点表示图中的一个顶点，并存储了与该顶点相连的所有顶点。
class Graph:
def __init__(self):
self.adj_list = {}
def add_edge(self, u, v):
if u in self.adj_list:
self.adj_list[u].append(v)
else:
self.adj_list[u] = [v]
def degree(self, u):
return len(self.adj_list[u]) if u in self.adj_list else 0
# 使用示例
g = Graph()
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
print(g.degree(1)) # 输出: 2
2. 邻接矩阵法
邻接矩阵是一个二维数组，其元素表示顶点之间的关系。在无向图中，如果顶点i与顶点j相连，则矩阵中对应元素为1，否则为0；在有向图中，元素为1表示从顶点i指向顶点j的边存在。
def degree_adj_matrix(matrix, i):
return sum(matrix[i])
# 使用示例
matrix = [[0, 1, 0, 1], [1, 0, 1, 0], [0, 1, 0, 1], [1, 0, 1, 0]]
print(degree_adj_matrix(matrix, 0)) # 输出: 2
3. 度序列法
度序列是指将图中所有顶点的度数按升序或降序排列的序列。在有向图中，可以分别计算入度和出度，得到两个度序列。
总结
通过学习如何计算图顶点的度数，我们不仅可以更好地理解图论的基础知识，还可以将所学应用于解决实际问题。无论是通过邻接表、邻接矩阵还是度序列法，我们都能量化网络中节点的连接数量，为后续的图论研究奠定基础。