关于在c ++中实现图形的问题 [英] Questions regarding Implementation of graph in c++

问题描述

我正在学习在C ++中实现图形，因此我阅读了维基百科条目，并在那里找到是两种常用的方法：邻接列表和邻接矩阵。我了解邻接列表和邻接矩阵之间的空间权衡。

我有三个问题

1）除了上面列出的两个以外，还有其他方法来实现图表？

2）什么是使用不同的数据结构之间的区别？链接列表VS矢量VS映射

3）文章中的以下段落意味着什么

邻接列表和邻接
矩阵之间的另一个显着差异在于它们执行的操作的效率。在
邻接列表中，每个顶点的邻居可以有效地列出
，其时间与顶点的程度成正比。在
邻接矩阵中，该操作需要与图中顶点数量
成比例的时间，这可能会显着高于
度。另一方面，邻接矩阵允许测试
两个顶点在恒定时间彼此相邻;
邻接列表的速度较慢，以支持此操作。

执行参考??什么类型的操作？

在$ 中，两个顶点在恒定时间内是相邻的。有任何实际使用知道两个顶点是否相邻？

解决方案

1. 是你也可以使用指向其他节点的指针来明确地实现它。


2. listS 消耗更多的内存，不是随机访问，而是迭代器）元素在插入和删除时保持有效; vectorS 是内存有效的随机访问，但无效句柄（迭代器）在插入和删除时无效;通常消耗更多的内存，不要迭代慢，句柄（迭代器）通常在插入和删除时保持有效;查找子节点可以非常快。这实际上是这些容器之间的一般区别，并不是特别的图形。


3. 明确地给出了操作：列出邻居和测试邻接。两者都具有不同的复杂性，这取决于图的实现。

两个顶点彼此相邻只是意味着两个节点之间有一个直接的边缘。要做到这一点在不断的时间意味着操作是独立于每个节点有多少邻居。作为实际目的：是的，吨。您可能想知道一个城市是否通过直达街道连接到另一个城市。您可能想知道两个顶点在折叠之前是否有边缘等。

正如您所说的C ++一样，我强烈建议您查看一些好的图形库，如 Boost.Graph 或柠檬。

I am learning to implement a graph in C++ hence i read Wikipedia entry and found out there are two commonly used methods : Adjacency list and Adjacency matrix. I understand the tradeoff in space between Adjacency list and Adjacency matrix.

I have three questions

1) Are there any more ways other than the two listed above to implement the graph ??

2) What are the differences between using the different data structures ??? Linked List VS Vector VS Map

3) What does the following paragraph mean in the article

The other significant difference between adjacency lists and adjacency matrices is in the efficiency of the operations they perform. In an adjacency list, the neighbors of each vertex may be listed efficiently, in time proportional to the degree of the vertex. In an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree. On the other hand, the adjacency matrix allows testing whether two vertices are adjacent to each other in constant time; the adjacency list is slower to support this operation.

What does efficiency of the operations they perform refer to ?? What type of operations???

What does two vertices are adjacent to each other in constant time mean and are there any practical usage of knowing if two vertices are adjacent to each other???

解决方案

1. Yes, you can also implement it explicitly using pointers to other nodes.
2. listS consume more memory and are not random access, but handles (iterators) to elements stay valid on insertion and deletion; vectorS are memory efficient, random access, but invalidate handles (iterators) get invalidated on insertion and deletion; mapS usually consume more memory, don't iterate slower, handles (iterators) usually stay valid on insertion and deletion; look up of child nodes can be very fast. This is really the general difference between those containers and not very graph specific.
3. The operations are explicitly given: listing neighbors and testing adjacency. Both have different complexities depending on the graph implementation.

two vertices are adjacent to each other just means that there is a direct edge between two nodes. To do that in constant time means that the operation is independent of how many neighbors each node has. As practical purposes go: Yes, tons of them. You might want to know if a city is connected to another city by a direct street. You might want to know if two vertices have an edge before collapsing it etc.

As you are talking C++ I would highly encourage you to have a look at some of the good graph libraries like Boost.Graph or Lemon.

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