相关疑难解决方法(0)

我想知道在c ++中快速编写图形的实现.我需要数据结构易于操作和使用图形算法(例如BFS,DFS,Kruskal,Dijkstra ......).我需要这个实现的算法Olympiad,所以更容易编写数据结构更好.

你能建议这样的DS(主要结构或类别以及将在其中的内容).我知道邻接列表和邻接矩阵是主要的可能性,但我的意思是更详细的代码示例.

例如,上次我必须为DFS实现图形时,我想到了这个DS:

struct Edge {
  int start;
  int end;
  struct Edge* nextEdge;
}

然后使用一个大小为n的数组,在第i个位置包含表示从第i个节点开始的边的边缘列表(struct Edge).

但是当在这个图上尝试DFS时,我不得不用大约10个while循环编写50行代码.

有什么'好'的实施？

我随时都看到有三种表示图形的方法:

1. 对象和指针
2. 邻接矩阵
3. 邻接列表

但是,我只是简单地不明白这些对象和指针表示是什么 - 但是每个招聘人员和许多博客都引用了Steve Yegge的博客,他们确实是一个单独的代表.

对于一个非常相似的问题,这个被广泛接受的答案似乎表明顶点结构本身没有指向其他顶点的内部指针,而是所有边都由包含指向相邻顶点的指针的边结构表示.

在任何情况下,这种表示如何提供任何可辨别的分析优势？

我有个要求,定义Data Structure和Algorithm用于Circular Data Graph为网络客户端.
在服务器上,数据将以2列CSV格式提供(例如发送者,接收者).
最终输出将以JSON格式呈现并发送到Web请求.
我见过一些Tree可以帮助父子关系的例子.但在我的情况下,我有一个递归的关系i.e. A Parent's grand child can also be used as a Parent; 当我遇到无限循环时,这会让生活变得困难.

数据:

Sender,Receiver
A,B
A,H
B,C
B,D
D,E
E,F
F,G
G,C
H,I
H,J
J,K
K,L
L,M
M,K
L,N
N,O
N,P
P,A
N,Q

客户端可以像这样呈现(我只关心Java结构):
客户端可以请求任何节点,我必须生成整个树并发送响应,即A,K或N.

问题:

1. Data Structure这个要求最好的是什么？例如Tree喜欢还是其他？
2. 我应该编写自己的逻辑来读取数据并设置Tree或是否有任何标准算法？
3. 什么是避免递归的最佳方法？

任何工作的例子都会有帮助:)

另请参阅下面的工作解决方案.

我可以在很多书中看到图表的最坏情况内存需求是O(V).但是,如果我没有弄错,图表通常表示为邻接矩阵而不是节点的创建(如链表/树中).因此,对于包含5个顶点的图形,我需要5x5矩阵,即O(V ^ 2).他们为什么说它是O(V)？

我在某处遗漏了什么吗？对不起,如果这个问题太天真了.