图扩展：带权图与有向无环图的数据结构与算法
图是数据结构中的一种重要类型，它由节点（也称为顶点）和边组成，用于表示实体之间的关系。在现实世界中，图广泛应用于网络、社交网络、交通系统等领域。本文将围绕带权图和有向无环图（DAG）这两种图的数据结构和算法进行探讨。
带权图
数据结构
带权图是一种特殊的图，其中每条边都有一个权重。在Python中，我们可以使用邻接表或邻接矩阵来表示带权图。
邻接表表示法
邻接表是一种使用链表来表示图的数据结构。对于带权图，我们可以使用一个字典来存储节点和与之相连的节点及其权重。
python
class WeightedGraph:
def __init__(self):
self.graph = {}
def add_edge(self, u, v, weight):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append((v, weight))
def get_edges(self, u):
return self.graph.get(u, [])
邻接矩阵表示法
邻接矩阵是一个二维数组，其中矩阵的元素表示两个节点之间的权重。对于带权图，我们可以使用一个二维列表来表示邻接矩阵。
python
class WeightedGraph:
def __init__(self, vertices):
self.vertices = vertices
self.graph = [[0] vertices for _ in range(vertices)]
def add_edge(self, u, v, weight):
self.graph[u][v] = weight
def get_weight(self, u, v):
return self.graph[u][v]
算法
Dijkstra算法
Dijkstra算法用于找到图中两个节点之间的最短路径。它适用于带权图，并且边的权重都是非负的。
python
import heapq
def dijkstra(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
if current_distance > distances[current_vertex]:
continue
for neighbor, weight in graph[current_vertex]:
distance = current_distance + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
Bellman-Ford算法
Bellman-Ford算法用于找到图中两个节点之间的最短路径，它适用于带权图，并且边的权重可以是负数。
python
def bellman_ford(graph, start):
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
for _ in range(len(graph) - 1):
for u in graph:
for v, weight in graph[u]:
if distances[u] + weight < distances[v]:
distances[v] = distances[u] + weight
检测负权重循环
for u in graph:
for v, weight in graph[u]:
if distances[u] + weight < distances[v]:
raise ValueError("Graph contains a negative-weight cycle")
return distances
有向无环图（DAG）
数据结构
有向无环图是一种没有环的有向图。在Python中，我们可以使用邻接表来表示DAG。
python
class DAG:
def __init__(self):
self.graph = {}
def add_edge(self, u, v):
if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)
def get_edges(self, u):
return self.graph.get(u, [])
算法
拓扑排序
拓扑排序是一种对有向无环图进行排序的方法，它确保了所有有向边都指向后续的节点。
python
def topological_sort(dag):
in_degree = {vertex: 0 for vertex in dag.graph}
for u in dag.graph:
for v in dag.graph[u]:
in_degree[v] += 1
queue = [vertex for vertex in dag.graph if in_degree[vertex] == 0]
sorted_list = []
while queue:
vertex = queue.pop(0)
sorted_list.append(vertex)
for v in dag.graph[vertex]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(sorted_list) == len(dag.graph):
return sorted_list
else:
raise ValueError("Graph has a cycle")
强连通分量
强连通分量是指在有向图中，任意两个节点之间都存在双向路径的子图。
python
def kosaraju(graph):
def dfs(v, visited, stack):
visited.add(v)
for i in graph[v]:
if i not in visited:
dfs(i, visited, stack)
stack.append(v)
def dfs2(v, visited, component):
visited.add(v)
component.append(v)
for i in graph2[v]:
if i not in visited:
dfs2(i, visited, component)
visited = set()
stack = []
graph2 = {v: [] for v in graph}
for v in graph:
for i in graph[v]:
graph2[i].append(v)
for v in graph:
if v not in visited:
dfs(v, visited, stack)
visited = set()
components = []
while stack:
v = stack.pop()
if v not in visited:
component = []
dfs2(v, visited, component)
components.append(component)
return components
总结
本文介绍了带权图和有向无环图（DAG）的数据结构和算法。带权图可以使用邻接表或邻接矩阵表示，并可以使用Dijkstra算法和Bellman-Ford算法来找到最短路径。有向无环图可以使用邻接表表示，并可以使用拓扑排序和Kosaraju算法来找到强连通分量。这些数据结构和算法在计算机科学和实际应用中都有广泛的应用。
Comments NOTHING