用C ++或Java实现图形 [英] Implementing a graph in either C++ or Java

问题描述

在C ++或Java中实现图的最佳方式是什么？在C ++中，我正在考虑使用2d数组来做到这一点。在java中，我正在考虑一个arrayList。

解决方案

首先，语言选择并不是世界上最大的问题，我的想法。除非您有要求使用特定语言或可移植性，否则使用C ++或Java就足够了。话虽如此，你的问题似乎有点功课 - 是啊。您是否在您的MST实施中使用了 Prim的算法？

正如其他答案已经说过的，有几种方法来表示图。我最熟悉的用于表示图形的两种方法是： Adjacency Matrix（邻接矩阵），其是每个行和列是节点的2D阵列，并且矩阵的该位置处的值表示边缘（或边缘权重）和一个空值（或一个0值，或其他一些标记/有意义的值）表示没有边

邻接列表，它是一个二维数组（kinda），其中第i列表是连接到（邻近）节点的所有节点的列表 I 的。有时候，如果您的图形是定向/加权的，您也可以选择使列表成为节点名称和边权重对的列表。

在维基百科的邻接列表文章（链接上面）中有一段关于这两个表示之间的权衡。

关于MST算法的主题：

p>

使用邻接表可能会获得更好的性能，但这仅仅是理论上的（我认为？）。在实施方面，有些事情如参考地点需要考虑。然而，为了便于编码，我个人更喜欢使用邻接矩阵（我个人发现它们更容易处理，特别是在加权图上），除非需要非常好的性能。

邻接矩阵（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 ++真的很黑，因为我倾向于在编码竞争中使用它来攻击随机代码，所以这不是很好的代码，但它是编码这些数据表示的真正基本方法。

很抱歉发生了大规模的咆哮，我希望它能帮上忙。 p>

What's the best ways of implementing a graph in either C++ or Java? In C++, I was thinking about using a 2d array to do it. In java, I was considering an arrayList.

解决方案

Firstly, language choices aren't the most massive issue in the world, in my opinion. Unless you have a requirement to use a specific language or on portability, using either C++ or Java will be sufficient. Having said that, your question seems somewhat homework-ish. Are you using Prim's algorithm for your MST implementation?

As other answers have already said, there are a few ways to represent graphs. The two that I'm most familiar with for representing graphs are:

1. An Adjacency Matrix, which is a 2D array where each "row" and "column" is a node, and a value at that position of the matrix indicates an edge (or an edge weight) and a null-value (or a 0-value, or some other sentinel/meaningful value) indicates no edge
2. An Adjacency List, which is a 2D array (kinda), where the i-th list is the list of all the nodes that are connected to (adjacent to) node i. At times, you may also choose to make the list a list of pairs of node names and edge weights, if your graph is directed/weighted.

In the adjacency list article on Wikipedia (linked above) there is a section on tradeoffs between the two representations.

On the subject of the MST algorithm:

You will probably get better performance using an adjacency list, out of the top of my head, but that's only theoretically (I think?). Implementation-wise, there are things such as locality of reference to take into account. I would personally prefer, for ease of coding, however, to use an adjacency matrix (I just personally find them easier to work with, especially on weighted graphs), unless there's a need for really good performance.

Adjacency Matrix (C++):

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

where n is the number of nodes in the graph. Then adj_Mat[i][j] is the weight of the edge between nodes i and j.

Adjacency List (C++):

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

Then, if the i-th node has an edge weight of k to node j, I'd do something like this (assuming the graph is directed)

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

Now, my C++ is really hacky because I tend to use it for hacking random code in coding competitions, so this isn't really good code but it's really basic ways to code up these data representations.

Sorry about the massive rant, and I hope it does help.

这篇关于用C ++或Java实现图形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！