图算法：从基础到应用-编程实验室

一、引言
图是一种强大的数据结构，用于表示对象之间的关系。从社交网络到路线规划，从网页连接到生物信息学，图算法在计算机科学的各个领域都有着广泛的应用。本文将介绍图的基本概念、常见算法及其实现。

二、图的表示方法

邻接矩阵

classGraphMatrix:def__init__(self,vertices):self.V=vertices self.graph=[[0]*verticesfor_inrange(vertices)]defadd_edge(self,u,v,weight=1,directed=False):self.graph[u][v]=weightifnotdirected:self.graph[v][u]=weightdefprint_graph(self):foriinrange(self.V):print(f"顶点{i}:{self.graph[i]}")

邻接表（更节省空间）

fromcollectionsimportdefaultdictclassGraphAdjList:def__init__(self,directed=False):self.graph=defaultdict(list)self.directed=directed self.vertices=set()defadd_edge(self,u,v,weight=1):self.graph[u].append((v,weight))self.vertices.add(u)self.vertices.add(v)ifnotself.directed:self.graph[v].append((u,weight))defprint_graph(self):forvertexinself.graph:print(f"{vertex}:{self.graph[vertex]}")

三、基础图遍历算法

深度优先搜索 (DFS)

defdfs_recursive(graph,start,visited=None):"""递归实现DFS"""ifvisitedisNone:visited=set()visited.add(start)print(start,end=" ")forneighbor,_ingraph.get(start,[]):ifneighbornotinvisited:dfs_recursive(graph,neighbor,visited)returnvisiteddefdfs_iterative(graph,start):"""迭代实现DFS"""visited=set()stack=[start]whilestack:vertex=stack.pop()ifvertexnotinvisited:print(vertex,end=" ")visited.add(vertex)# 将邻居逆序加入栈中，以保持与递归相同的遍历顺序forneighbor,_inreversed(graph.get(vertex,[])):ifneighbornotinvisited:stack.append(neighbor)returnvisited

广度优先搜索 (BFS)

fromcollectionsimportdequedefbfs(graph,start):"""BFS实现"""visited=set([start])queue=deque([start])whilequeue:vertex=queue.popleft()print(vertex,end=" ")forneighbor,_ingraph.get(vertex,[]):ifneighbornotinvisited:visited.add(neighbor)queue.append(neighbor)returnvisited

四、最短路径算法

Dijkstra算法（单源最短路径，权重非负）

importheapqdefdijkstra(graph,start):"""Dijkstra最短路径算法"""# 初始化距离字典distances={vertex:float('inf')forvertexingraph}distances[start]=0previous={vertex:Noneforvertexingraph}# 优先队列priority_queue=[(0,start)]whilepriority_queue:current_distance,current_vertex=heapq.heappop(priority_queue)# 如果当前距离大于已知最短距离，跳过ifcurrent_distance>distances[current_vertex]:continue# 更新邻居节点的距离forneighbor,weightingraph.get(current_vertex,[]):distance=current_distance+weightifdistance<distances[neighbor]:distances[neighbor]=distance previous[neighbor]=current_vertex heapq.heappush(priority_queue,(distance,neighbor))returndistances,previousdefget_path(previous,target):"""从previous字典重构路径"""path=[]current=targetwhilecurrentisnotNone:path.append(current)current=previous[current]returnpath[::-1]

Floyd-Warshall算法（所有节点对最短路径）

deffloyd_warshall(graph_matrix,vertices):"""Floyd-Warshall算法"""# 初始化距离矩阵dist=[[float('inf')]*verticesfor_inrange(vertices)]foriinrange(vertices):dist[i][i]=0forj,weightinenumerate(graph_matrix[i]):ifweight!=0:dist[i][j]=weight# 动态规划forkinrange(vertices):foriinrange(vertices):forjinrange(vertices):ifdist[i][j]>dist[i][k]+dist[k][j]:dist[i][j]=dist[i][k]+dist[k][j]returndist

五、最小生成树算法

Prim算法

defprim_mst(graph,start):"""Prim最小生成树算法"""mst=[]visited=set([start])edges=[]# 初始化起始点的边forneighbor,weightingraph.get(start,[]):heapq.heappush(edges,(weight,start,neighbor))whileedgesandlen(visited)<len(graph):weight,u,v=heapq.heappop(edges)ifvnotinvisited:visited.add(v)mst.append((u,v,weight))# 添加新顶点的边forneighbor,wingraph.get(v,[]):ifneighbornotinvisited:heapq.heappush(edges,(w,v,neighbor))returnmst

Kruskal算法

classDisjointSet:"""并查集实现，用于Kruskal算法"""def__init__(self,vertices):self.parent={v:vforvinvertices}self.rank={v:0forvinvertices}deffind(self,v):ifself.parent[v]!=v:self.parent[v]=self.find(self.parent[v])returnself.parent[v]defunion(self,v1,v2):root1=self.find(v1)root2=self.find(v2)ifroot1!=root2:ifself.rank[root1]>self.rank[root2]:self.parent[root2]=root1elifself.rank[root1]<self.rank[root2]:self.parent[root1]=root2else:self.parent[root2]=root1 self.rank[root1]+=1returnTruereturnFalsedefkruskal_mst(graph):"""Kruskal最小生成树算法"""edges=[]vertices=set()# 收集所有边foruingraph:vertices.add(u)forv,weightingraph.get(u,[]):vertices.add(v)edges.append((weight,u,v))# 按权重排序edges.sort()# 初始化并查集ds=DisjointSet(vertices)mst=[]forweight,u,vinedges:ifds.union(u,v):mst.append((u,v,weight))iflen(mst)==len(vertices)-1:breakreturnmst

六、拓扑排序（用于有向无环图）

deftopological_sort_kahn(graph):"""Kahn算法实现拓扑排序"""# 计算入度in_degree={vertex:0forvertexingraph}foruingraph:forv,_ingraph[u]:in_degree[v]=in_degree.get(v,0)+1# 初始化队列queue=deque([vforvingraphifin_degree.get(v,0)==0])topo_order=[]whilequeue:u=queue.popleft()topo_order.append(u)forv,_ingraph.get(u,[]):in_degree[v]-=1ifin_degree[v]==0:queue.append(v)iflen(topo_order)==len(graph):returntopo_orderelse:# 图中存在环returnNonedeftopological_sort_dfs(graph):"""DFS实现拓扑排序"""visited=set()temp=set()# 临时标记，用于检测环stack=[]defdfs(vertex):ifvertexintemp:# 检测到环raiseValueError("图中有环，无法进行拓扑排序")ifvertexinvisited:returntemp.add(vertex)forneighbor,_ingraph.get(vertex,[]):dfs(neighbor)temp.remove(vertex)visited.add(vertex)stack.append(vertex)forvertexingraph:ifvertexnotinvisited:dfs(vertex)returnstack[::-1]

七、应用示例：社交网络分析

classSocialNetworkAnalyzer:def__init__(self):self.graph=GraphAdjList(directed=False)defadd_friendship(self,person1,person2,strength=1):self.graph.add_edge(person1,person2,strength)deffind_degrees_of_separation(self,start,target):"""使用BFS查找两个人之间的分离度数"""ifstart==target:return0visited=set([start])queue=deque([(start,0)])# (person, distance)whilequeue:current_person,distance=queue.popleft()forneighbor,_inself.graph.graph.get(current_person,[]):ifneighbor==target:returndistance+1ifneighbornotinvisited:visited.add(neighbor)queue.append((neighbor,distance+1))return-1# 没有路径deffind_influential_people(self,top_n=5):"""使用度中心性查找最有影响力的人"""centrality={}forpersoninself.graph.vertices:centrality[person]=len(self.graph.graph.get(person,[]))# 按中心性排序sorted_centrality=sorted(centrality.items(),key=lambdax:x[1],reverse=True)returnsorted_centrality[:top_n]deffind_communities(self):"""使用DFS查找连通分量（社区）"""visited=set()communities=[]forpersoninself.graph.vertices:ifpersonnotinvisited:community=dfs_recursive(self.graph.graph,person,set())visited.update(community)communities.append(community)returncommunities# 使用示例if__name__=="__main__":# 创建图graph=GraphAdjList()graph.add_edge(0,1,4)graph.add_edge(0,7,8)graph.add_edge(1,2,8)graph.add_edge(1,7,11)graph.add_edge(2,3,7)graph.add_edge(2,8,2)graph.add_edge(2,5,4)graph.add_edge(3,4,9)graph.add_edge(3,5,14)graph.add_edge(4,5,10)graph.add_edge(5,6,2)graph.add_edge(6,7,1)graph.add_edge(6,8,6)graph.add_edge(7,8,7)print("图结构:")graph.print_graph()print("\nDFS遍历 (从节点0开始):")dfs_recursive(graph.graph,0)print("\n\nBFS遍历 (从节点0开始):")bfs(graph.graph,0)print("\n\nDijkstra最短路径 (从节点0开始):")distances,previous=dijkstra(graph.graph,0)forvertexindistances:print(f"到节点{vertex}的最短距离:{distances[vertex]}")print(f"路径:{get_path(previous,vertex)}")print("\nPrim最小生成树:")mst_prim=prim_mst(graph.graph,0)print(f"最小生成树边:{mst_prim}")total_weight=sum(weightfor_,_,weightinmst_prim)print(f"总权重:{total_weight}")# 社交网络示例print("\n--- 社交网络分析示例 ---")social_net=SocialNetworkAnalyzer()social_net.add_friendship("Alice","Bob")social_net.add_friendship("Alice","Charlie")social_net.add_friendship("Bob","David")social_net.add_friendship("Charlie","David")social_net.add_friendship("David","Eve")social_net.add_friendship("Frank","Grace")print(f"Alice和Eve之间的分离度数:{social_net.find_degrees_of_separation('Alice','Eve')}")print(f"最有影响力的人:{social_net.find_influential_people(3)}")print(f"发现的社区:{social_net.find_communities()}")