有哪些方法可以代表Java中的加权有向图?
发布时间:2020-12-15 00:56:51 所属栏目:Java 来源:网络整理
导读:我不能使用任何外部库,所以我试着想一些自己构建数据结构的方法.我在想也许是这样的: public class Node{ SetEdge adjacent; int value;}public class Edge{ Node target; int weight;} 但我猜这可能是一种更好的方法. 我最终使用这个图是在它上运行Bellman
我不能使用任何外部库,所以我试着想一些自己构建数据结构的方法.我在想也许是这样的:
public class Node{ Set<Edge> adjacent; int value; } public class Edge{ Node target; int weight; } 但我猜这可能是一种更好的方法. 我最终使用这个图是在它上运行Bellman Ford算法,但我显然首先需要一个功能图! 解决方法
答案很大程度上取决于您计划应用于图表的算法.
有两种常用的方法来表示图形 – 一个adjacency list和一个adjacency matrix.在你的情况下,邻接矩阵是一个表示权重的整数的正方形数组.您的表示使用邻接列表. 有些算法在邻接矩阵上工作得更好(例如Floyd-Warshall算法).其他算法在邻接列表上工作得更好(例如Dijkstra算法).如果图表稀疏,则使用邻接矩阵可能会令人望而却步. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |