Python输出无向图各顶点的度

可以使用邻接矩阵或邻接表来表示无向图，然后统计每个顶点的度数。

以下是使用邻接矩阵实现的Python代码：

# 定义邻接矩阵表示无向图
graph = [[0, 1, 1, 0],
         [1, 0, 1, 1],
         [1, 1, 0, 1],
         [0, 1, 1, 0]]

# 统计每个顶点的度数并输出
for i in range(len(graph)):
    degree = sum(graph[i])
    print("顶点{}的度为{}".format(i, degree))

输出结果如下：

顶点0的度为2
顶点1的度为3
顶点2的度为3
顶点3的度为2

其中，graph是一个4x4的邻接矩阵，表示一个有4个顶点的无向图。对于每个顶点i，通过sum函数计算出它所连接的边的数量，即为它的度数。最后输出每个顶点的度数即可。

相关问题

python带权无向图中邻接矩阵

在Python中，可以使用二维列表来表示带权无向图的邻接矩阵。邻接矩阵是一个方阵，其中的元素表示图中两个顶点之间的边权重。如果两个顶点之间没有边，则对应位置的元素为0或者无穷大。

下面是一个示例代码，展示了如何使用邻接矩阵表示带权无向图：

# 定义邻接矩阵
adjacency_matrix = [
    [0, 2, 0, 4, 0],
    [2, 0, 3, 0, 0],
    [0, 3, 0, 0, 1],
    [4, 0, 0, 0, 5],
    [0, 0, 1, 5, 0]
]

# 打印邻接矩阵
for row in adjacency_matrix:
    print(row)

输出结果为：

[0, 2, 0, 4, 0]
[2, 0, 3, 0, 0]
[0, 3, 0, 0, 1]
[4, 0, 0, 0, 5]
[0, 0, 1, 5, 0]

这个邻接矩阵表示了一个带权无向图，其中顶点之间的边的权重分别为2、4、3、1和5。

Python判断无向图中是否有环

### 回答1：
可以使用深度优先搜索（DFS）来判断无向图中是否有环。具体操作如下：

1. 从任意一个节点开始进行DFS遍历，并标记该节点为“已访问”状态。
2. 遍历该节点的所有邻居节点，如果邻居节点已经被访问过，且邻居节点不是当前节点的父节点，则说明存在环。
3. 如果邻居节点没有被访问过，则将邻居节点作为当前节点的子节点进行DFS遍历（即将邻居节点的父节点标记为当前节点）。
4. 重复步骤2和步骤3，直到所有节点都被访问过。

下面是Python代码实现：

def has_cycle(graph):
    visited = set()
    parent = {node: None for node in graph}

    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                parent[neighbor] = node
                if dfs(neighbor):
                    return True
            elif neighbor != parent[node]:
                return True
        return False

    for node in graph:
        if node not in visited:
            if dfs(node):
                return True
    return False

其中，graph是一个邻接表，表示无向图中每个节点的邻居节点。如果函数返回True，则说明无向图中存在环；否则，说明无向图中不存在环。

### 回答2：
判断一个无向图中是否存在环，可以使用深度优先搜索（DFS）算法来实现。具体步骤如下：

1. 创建一个空的集合visited，用于存储已经遍历过的节点。
2. 对于无向图中的每个节点v，如果节点v没有被访问过，则进行深度优先搜索。
3. 在DFS函数中，首先将节点v标记为已访问，并将节点v加入visited集合中。
4. 然后，对于节点v的每个相邻节点u，判断u是否已经被访问过。如果u已经被访问过，而且u不是v的父节点（避免回退），则说明存在环，返回True。
5. 否则，对于节点u递归调用DFS函数，继续搜索它的相邻节点。
6. 如果DFS函数在遍历结束后都没有返回True，则说明无向图中不存在环，返回False。

下面是用Python代码实现的例子：

'''
def hasCycle(graph, v, visited, parent):
visited.add(v)
for u in graph[v]:
if u in visited and u != parent:
return True
elif u not in visited:
if hasCycle(graph, u, visited, v):
return True
return False

def isCycle(graph):
visited = set()
for v in graph:
if v not in visited:
if hasCycle(graph, v, visited, None):
return True
return False

# 例子：判断无向图中是否有环
graph = {
1: [2, 3],
2: [1, 3],
3: [1, 2]
}

print(isCycle(graph)) # 输出：True
'''

在上述代码中，我们通过字典graph表示无向图的邻接表形式。例如，{1: [2, 3]}表示节点1与节点2、节点3相邻。然后，使用isCycle函数判断无向图中是否存在环，若存在则返回True，否则返回False。

### 回答3：
在Python中判断无向图中是否有环可以使用深度优先搜索（DFS）的方法进行判断。

首先，我们需要定义一个函数isCyclicUtil，该函数用于判断以某个顶点作为起始点的无向图是否有环。该函数的参数包括当前正在访问的顶点v，该顶点的上一级顶点parent，以及一个布尔数组visited，用于记录每个顶点是否被访问过。

在函数内部，首先将当前顶点v标记为已访问，并遍历其所有相邻顶点。对于每个相邻顶点u，如果u没有被访问过，则递归调用isCyclicUtil函数判断以u为起始点的子图是否有环。如果u已经被访问过且u不是v的上一级顶点parent，则说明存在环，返回True。

如果遍历完了所有相邻顶点，仍未找到环，则返回False。

接下来，再定义一个主函数isCyclic，该函数用于判断整个无向图是否有环。首先创建一个布尔数组visited，用于记录每个顶点是否被访问过。然后遍历图中的每个顶点，使用isCyclicUtil函数判断以每个顶点为起始点的子图是否有环。如果存在任意一个子图有环，则整个图也有环，返回True。如果遍历完了所有顶点，都没有找到环，则返回False。

最后，我们可以调用主函数isCyclic来判断一个给定的无向图是否有环。如果返回值为True，则说明有环；如果返回值为False，则说明没有环。

需要注意的是，在使用isCyclicUtil函数的递归调用时，我们需要将当前顶点v和其上一级顶点parent传入，用于判断是否存在回路。

这样，我们就可以使用Python来判断无向图中是否存在环。