Python深度学习-有向图合并、排序、最长路径计算

news/2024/10/30 9:25:20/

一、有向图方向、权重表示方法

Python通常使用有向图中边的起点和终点来表示边的方向。例如,如果有一条从节点A到节点B的边,则可以使用以下方式表示该有向边:

graph = {'A': {'B': 1}
}

在这个例子中,节点'A'和节点'B'之间存在一条权重为1的边,它的方向是从'A'指向'B'。这表示从节点'A'可以到达节点'B',但不一定反过来。如果要表示从节点'B'到节点'A'的边,需要另外定义一个字典:

graph = {'A': {'B': 1},'B': {'A': 2}
}

在这个例子中,节点'A'和节点'B'之间存在两条边。第一条是从'A'到'B',权重为1,第二条是从'B'到'A',权重为2。注意,这两条边是不同的,因为它们的方向不同。

二、有向图合并原理

有向图合并指的是将多个有向图合并成一个有向图的过程。这种操作在图数据处理中比较常见,例如将多个社交网络中的用户关系、兴趣爱好等信息进行整合,以便进行更全面、准确的分析。

有向图合并的原理主要涉及节点合并和边合并两个方面。

节点合并:当有多个有向图的节点表示同一个实体时,需要将这些节点合并成一个节点,避免在后续操作中出现重复计算问题。节点合并可以使用哈希表等数据结构实现,将每个节点关联到对应的实体上,通过哈希表查找实体对应的节点进行合并。

边合并:当有多个有向图中的两个节点之间存在相同的边时,需要将这些边合并成一条边,以避免重复计算。边合并可以根据具体情况进行不同的处理。例如,如果边的权重值相同,则可以直接合并;如果不同,则可以选择采用加权平均值、加权求和等方法来合并边的权重值。

以下是Python实现有向图合并的示例代码:

def merge_digraphs(graphs):# 合并有向图merged_graph = {}# 记录每个实体对应的节点entity_to_node = {}for graph in graphs:for node, neighbors in graph.items():# 合并节点if node in entity_to_node:curr_node = entity_to_node[node]else:curr_node = nodeentity_to_node[node] = curr_node# 合并边for neighbor, weight in neighbors.items():if neighbor in entity_to_node:curr_neighbor = entity_to_node[neighbor]else:curr_neighbor = neighborentity_to_node[neighbor] = curr_neighborif curr_node not in merged_graph:merged_graph[curr_node] = {}if curr_neighbor in merged_graph[curr_node]:merged_graph[curr_node][curr_neighbor] += weightelse:merged_graph[curr_node][curr_neighbor] = weightreturn merged_grapharr_graph1 =  [{'A': {'B': 3, 'C': 6},'B': {'C': 2, 'D': 1},'C': {'D': 1},'D': {}}
]arr_graph2 =  [{'A': {'B': 3, 'C': 6},'B': {'C': 2, 'D': 1},'C': {'D': 1},'D': {}},{'A': {'B': 1, 'C': 1},'B': {'C': 1, 'D': 1},'C': {'D': 1},'D': {}}
]
print(merge_digraphs(arr_graph1))
print(merge_digraphs(arr_graph2))

运行结果:

 

graphs是待合并的多个有向图,每个有向图用邻接表形式表示。在合并节点时,首先判断该节点是否已经存在于之前的有向图中,如果是,则直接将当前节点关联到该实体上;否则,将当前节点作为新的节点,并将其关联到对应的实体上。在合并边时,如果两个节点之间的边已经存在,则将其权重值相加;否则,将其作为新的边添加到合并后的有向图中。

三、有向图最长路径算法

下面是一个Python实现有向图最长路径计算的代码示例:

from collections import dequedef topological_sort(graph):# 对有向图进行拓扑排序in_degree = {v: 0 for v in graph}  # 记录每个节点的入度for node in graph:for neighbor in graph[node]:in_degree[neighbor] += 1queue = deque([node for node in in_degree if in_degree[node] == 0])result = []while queue:node = queue.popleft()result.append(node)for neighbor in graph[node]:in_degree[neighbor] -= 1if in_degree[neighbor] == 0:queue.append(neighbor)if len(result) != len(graph):  # 存在环return Nonereturn resultdef longest_path(graph, start, end):# 计算有向图中从start到end的最长路径topological_order = topological_sort(graph)print(f'有向图拓扑排序结果:{topological_order}')dist = {node: float('-inf') for node in graph}dist[start] = 0prev = {node: None for node in graph}for node in topological_order:if node == end:breakif dist[node] != float('-inf'):for neighbor in graph[node]:new_dist = dist[node] + graph[node][neighbor]if new_dist > dist[neighbor]:dist[neighbor] = new_distprev[neighbor] = node# 生成路径path = []node = endwhile node is not None:path.append(node)node = prev[node]path.reverse()return dist[end], path# 举个例子
graph = {'A': {'B': 3, 'C': 6},'B': {'C': 2, 'D': 1},'C': {'D': 1},'D': {}}
length, path = longest_path(graph, 'A', 'D')
print(f"最长路径为{path},路径长度(权重)为{length}")

运行结果:

 

有向图:

 

 

这个例子中,我们先使用topological_sort函数对有向图进行拓扑排序,然后依次计算每个节点的最长路径和路径终点,并使用prev字典记录每个节点在最长路径上的前驱节点。最后,我们生成从起点到终点的最长路径。这个算法的时间复杂度为O(V+E),其中V是节点数量,E是边数量。


http://www.ppmy.cn/news/841720.html

相关文章

龙岗大运中心体育中心纯航拍多图32张(航拍深圳第5集)

全景再现科技用5年时间航拍整个深圳,制作成VR地图,最终形成全景元宇宙。大家自己搜索,全景再现科技,或搜索航拍整个深圳,这样你也可以和我一样身临其境,任意放大体验,点击地图看更多深圳全景。点…

k8s安装mysql

k8s安装mysql Docker安装验证MySQL镜像 docker pull mysql:5.7 运行 docker run --name jackie-mysql -p 3306:3306 -e MYSQL_ROOT_PASSWORDbigdata -d mysql:5.7 查看日志 docker logs jackie-mysql 查看容器状态 docker ps 找到容器IP地址 docker inspect jackie-mysql…

2023-07-12力扣每日一题

链接&#xff1a; 2544. 交替数字和 题意&#xff1a; 一个数字字符串&#xff0c;根据符号求和&#xff0c;符号规律 - - … 解&#xff1a; 简单题&#xff0c;遍历 实际代码&#xff1a; 手写&#xff1a; #include<bits/stdc.h> using namespace std; typed…

java中连连看_JAVA版连连看功能模块介绍(续)

进入游戏界面的功能模块介绍 变换游戏背景&#xff1a;本游戏支持十张图片可以变换&#xff0c;可直接点击游戏当中的背景按钮变换游戏的背景&#xff0c;如果用户需要可以将项目bin目录下的背景文件更换掉&#xff0c;文件格式必须是.png格式的&#xff0c;图像高宽度必须是80…

ios 水果连连看游戏源码

原创文章&#xff0c;转载请注明出处&#xff1a;http://blog.csdn.net/donny_zhang/article/details/9251917 demo功能&#xff1a;水果连连看游戏源码。iphone6.1 测试通过。功能是清除屏幕上的所有的水果&#xff0c;并尝试每个关卡上获得更高的分数。包括“开始游戏”&am…

4399小游戏—宠物连连看经典版2—游戏辅助脚本

引言 期末的时候看到一篇博客&#xff0c;写的宠物连连看的辅助脚本&#xff0c;感觉很有意思&#xff0c;就自己跟着博客自己实现了一遍&#xff0c;开发过程中遇到了一些问题&#xff0c;也体会到了解决问题的乐趣&#xff0c;遂在此记录一下。 先放一下博客的链接&#xf…

南邮Android大作业(连连看口袋妖怪版)

基础原型&#xff1a; https://blog.csdn.net/ouyang_peng/article/details/14115627 修改&#xff1a; 可以选择游戏难度&#xff1a;简单、普通、困难&#xff08;其实就是图片变多了&#xff09;每个难度总共有5关&#xff1a;初始100秒&#xff0c;每关递减15秒增加排行榜功…

在中国以外的市场,华为和中兴颇为无奈,爱立信和三星则是大赢家

早前信通院公布了一份今年上半年全球5G设备市场的数据&#xff0c;数据显示华为仍然是全球第一大通信设备商&#xff0c;但是信通院其实当时还发布了另一份数据&#xff0c;那就是除中国以外的5G设备市场最大赢家却是爱立信和三星。 一、为何说爱立信和诺基亚是赢家 信通院公布…