以有向加权图为例
class Graph():
# 边列表表示法
def __init__(self, num_of_nodes, directed = True):
self.num_of_nodes = num_of_nodes
self.directed = directed
self.list_of_edges = []
def add_edge(self, node1, node2, weight):
# 从node1到node2添加权重
self.list_of_edges.append([node1, node2, weight])
# 如果是无向图,则需要再从node2到node1添加权重
if not self.directed:
self.list_of_edges.append([node2, node1, weight])
if __name__ == "__main__":
graph = Graph(5)
graph.add_edge(0,1,5)
graph.add_edge(0,2,3)
graph.add_edge(1,3,1)
graph.add_edge(0,4,15)
graph.add_edge(4,2,7)
graph.add_edge(4,3,11)
print(graph.list_of_edges)
# 输出:[[0, 1, 5], [0, 2, 3], [1, 3, 1], [0, 4, 15], [4, 2, 7], [4, 3, 11]]
class Graph():
# 邻接矩阵表示法
def __init__(self, num_of_nodes, directed = True):
self.num_of_nodes = num_of_nodes
self.directed = directed
self.edge_matrix = [[0 for _ in range(num_of_nodes)] for _ in range(num_of_nodes)]
def add_edge(self, node1, node2, weight):
# 从node1到node2添加权重
self.edge_matrix[node1][node2] = weight
# 如果是无向图,则需要再从node2到node1添加权重
if not self.directed:
self.edge_matrix[node2][node1] = weight
if __name__ == "__main__":
graph = Graph(5)
graph.add_edge(0,1,5)
graph.add_edge(0,2,3)
graph.add_edge(1,3,1)
graph.add_edge(0,4,15)
graph.add_edge(4,2,7)
graph.add_edge(4,3,11)
print(graph.edge_matrix)
# 输出:[[0, 5, 3, 0, 15], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 7, 11, 0]]
class Graph():
# 邻接表表示法
def __init__(self, num_of_nodes, directed = True):
self.num_of_nodes = num_of_nodes
self.directed = directed
self.adjacency_list = {node : {} for node in range(num_of_nodes)}
def add_edge(self, node1, node2, weight):
# 从node1到node2添加权重
self.adjacency_list[node1][node2] = weight
# 如果是无向图,则需要再从node2到node1添加权重
if not self.directed:
self.adjacency_list[node2][node1] = weight
if __name__ == "__main__":
graph = Graph(5)
graph.add_edge(0,1,5)
graph.add_edge(0,2,3)
graph.add_edge(1,3,1)
graph.add_edge(0,4,15)
graph.add_edge(4,2,7)
graph.add_edge(4,3,11)
print(graph.adjacency_list)
# 输出:{0: {1: 5, 2: 3, 4: 15}, 1: {3: 1}, 2: {}, 3: {}, 4: {2: 7, 3: 11}}
1.1、DFS的递归法实现
def dfs(graph, start, visited=set()):
visited.add(start)
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
if __name__ == "__main__":
graph = {
'a': ['b'],
'b': ['a', 'c', 'd'],
'c': ['b', 'e'],
'd': ['b', 'e', 'f'],
'e': ['c', 'd', 'g'],
'f': ['d'],
'g': ['e']
}
start = 'b'
dfs(graph, start) # 输出:b a c e d f g
利用搜索的范围还能判断图的连通性
def is_connected(graph):
visited=set()
dfs(graph, next(iter(graph.keys())), visited)
return len(visited) == len(graph)
1.2、DFS的栈实现
def dfs(graph, start):
visited = set() # 用于存储已访问过的节点
stack = [start] # 创建一个栈, 并将起始点压入栈中
while stack:
current = stack.pop() # 从栈中取出当前点
if current not in visited:
print(current, end=' ') # 输出当前点
visited.add(current) # 将当前点加入已访问的集合
# 将当前点的未访问过的邻点压入栈中(逆序处理)
for neighbor in reversed(graph[current]):
if neighbor not in visited:
stack.append(neighbor)
if __name__ == "__main__":
graph = {
'a': ['b'],
'b': ['a', 'c', 'd'],
'c': ['b', 'e'],
'd': ['b', 'e', 'f'],
'e': ['c', 'd', 'g'],
'f': ['d'],
'g': ['e']
}
start = 'b'
dfs(graph, start) # 输出:b a c e d f g
深度优先搜索的时间复杂度为O(V+E): 由于每个点最多被访问1次，每条边最多被访问两次。
from collections import deque
def bfs(graph, start):
visited = set() # 用于存储已访问过的节点
queue = deque([start]) # 创建一个队列, 并将起始点加入队列中
while queue:
current = queue.popleft() # 从队列中取出当前点
if current not in visited:
print(current, end=' ') # 输出当前点
visited.add(current) # 将当前点加入已访问集合
# 将当前点的未访问过的邻点加入队列中
for neighbor in graph[current]:
if neighbor not in visited:
queue.append(neighbor)
if __name__ == "__main__":
graph = {
'a': ['b'],
'b': ['a', 'c', 'd'],
'c': ['b', 'e'],
'd': ['b', 'e', 'f'],
'e': ['c', 'd', 'g'],
'f': ['d'],
'g': ['e']
}
start = 'b'
bfs(graph, start) # 输出: b a c d e f g
广度优先搜索的时间复杂度也为O(V+E): 由于每个点最多被访问1次, 每条边最多被访问两次.