用C++或Java实现图形

Question

在C++或Java中实现图形的最佳方法是什么？在C++中,我正在考虑使用二维数组来完成它.在java中,我正在考虑一个arrayList.

Answer 1

首先,在我看来,语言选择并不是世界上最大的问题.除非您需要使用特定语言或可移植性,否则使用C++或Java就足够了.话虽如此,你的问题似乎有些功课.您是否正在使用Prim的算法进行MST实施？

正如其他答案已经说过的,有几种方法可以表示图形.我最熟悉的用于表示图形的两个是:

1. 一个邻接矩阵,这是一个二维阵列,其中每个"行"和"列"是一个节点,并在基体的该位置的值表示的边缘(或边缘重量)和一个空值(或0-值,或其他一些标记/有意义的值)表示没有边缘
2. 一个邻接表,它是一个二维阵列(有点),其中我个列表是所有连接到(邻近)节点的节点列表我.有时,如果图表是定向/加权的,您也可以选择使列表成为节点名称和边缘权重对的列表.

在维基百科上的邻接列表文章(上面链接)中,有一节关于两个表示之间的权衡.

关于MST算法的主题:

你可能会使用邻接列表获得更好的性能,但这只是理论上的(我认为？).在实施方面,有一些事项,如参考的地方考虑.然而,为了便于编码,我个人更喜欢使用邻接矩阵(我个人觉得它们更容易使用,特别是在加权图上),除非需要非常好的性能.

邻接矩阵(C++):

vector<vector<int> > adj_Mat(n, vector<int>(n, 0));

其中n是图中节点的数量.然后adj_Mat[i][j]是节点i和j之间边缘的权重.

邻接列表(C++):

vector<vector<pair<int, int> > > adj_list(n);

然后,如果第i个节点的边缘权重为k到节点j,我会做这样的事情(假设图是有针对性的)

adj_list[i].push_back(pair<int, int>(j, k));

现在,我的C++真的很酷,因为我倾向于在编码竞赛中使用它来破解随机代码,所以这不是很好的代码,但它是编写这些数据表示的基本方法.

对于大规模的咆哮感到抱歉,我希望它有所帮助.