python读取无权重邻接矩阵txt文件从1开始编号计算每个节点的偏心度并输出

偏心度（eccentricity）是指一个节点到图中所有其他节点的最短路径中的最大值。

假设我们有一个无权重邻接矩阵保存在名为`matrix.txt`的文本文件中，每行表示一个节点的邻居节点，以空格分隔。我们先读取这个文件并构建邻接矩阵。

import numpy as np

# 读取邻接矩阵
with open('matrix.txt', 'r') as f:
    lines = f.readlines()
    n = len(lines)
    matrix = np.zeros((n, n), dtype=int)
    for i, line in enumerate(lines):
        neighbors = list(map(int, line.strip().split()))
        for j in neighbors:
            matrix[i, j-1] = 1
            matrix[j-1, i] = 1  # 无向图需要对称

接下来，我们可以使用BFS算法计算每个节点的偏心度。

def bfs(matrix, start):
    """从start节点开始进行BFS"""
    n = matrix.shape[0]
    visited = np.zeros(n, dtype=bool)
    distance = np.zeros(n, dtype=int)
    queue = [start]
    visited[start] = True
    while len(queue) > 0:
        node = queue.pop(0)
        for nei in range(n):
            if matrix[node, nei] == 1 and not visited[nei]:
                visited[nei] = True
                distance[nei] = distance[node] + 1
                queue.append(nei)
    return distance

# 计算每个节点的偏心度
eccentricities = []
for i in range(n):
    distances = bfs(matrix, i)
    eccentricities.append(max(distances))

# 输出节点偏心度
for i, e in enumerate(eccentricities):
    print(f"节点{i+1}的偏心度为{e}")

完整代码如下：

import numpy as np

# 读取邻接矩阵
with open('matrix.txt', 'r') as f:
    lines = f.readlines()
    n = len(lines)
    matrix = np.zeros((n, n), dtype=int)
    for i, line in enumerate(lines):
        neighbors = list(map(int, line.strip().split()))
        for j in neighbors:
            matrix[i, j-1] = 1
            matrix[j-1, i] = 1  # 无向图需要对称

def bfs(matrix, start):
    """从start节点开始进行BFS"""
    n = matrix.shape[0]
    visited = np.zeros(n, dtype=bool)
    distance = np.zeros(n, dtype=int)
    queue = [start]
    visited[start] = True
    while len(queue) > 0:
        node = queue.pop(0)
        for nei in range(n):
            if matrix[node, nei] == 1 and not visited[nei]:
                visited[nei] = True
                distance[nei] = distance[node] + 1
                queue.append(nei)
    return distance

# 计算每个节点的偏心度
eccentricities = []
for i in range(n):
    distances = bfs(matrix, i)
    eccentricities.append(max(distances))

# 输出节点偏心度
for i, e in enumerate(eccentricities):
    print(f"节点{i+1}的偏心度为{e}")