存储树和图的数据？

在我试图解决的大多数树或图问题中，输入通常是整个树或图结构中的一个节点 - >叶节点或节点1 - >相邻节点格式。存储树和图的数据？

是否有常用结构的任意列表保存在存储器中的数据，后来帮助于预期algorithm.For例如：

Say i have a list of graph nodes like: 

1 3 8 2 4.....# 1 is connected to 3 8 2 4...nodes 
2 5 1 3... # 2 is connected to 5 1 3...nodes 
3 1 2... #likewise 
. ... 
8 ......

所以如果我想使用随机收缩算法（在我将不得不契约边缘说我收缩1和8 ..我使用一个多链表的结构，其中邻接列表上的每个节点指向其对应的行ie8在第一行指向第八节点

现在的问题，为什么我选择这种结构来存储数据？

合同是有效地做1〜8一个单一实体，

，所以我读1的3起邻接表和去三分之二邻接表变化1至8和明年8的排使1至8现在去2的名单变化1到8 ....最后我追加1s列表到8并删除重复..Yep，所以最后1从图中删除后收缩1和8

我想知道所有通常或很少使用的结构为存储树和图表，如果与algos algo名称关联？谢谢

来源

2014-10-20 sarat

存储图的一种常见方式是使用n-m atrix，其中n是图中顶点的数量。如果你只是想存储邻接关系，如果X是矩阵，那么X[i][j] = 1如果顶点j从顶点i和0可到达，否则。你也可以用这种方式存储边缘成本或边缘能力。缺点当然是使用的内存量，O(n^2)而不是O(n+m)，其中m是边的数量，但优点是对于每个可能的顶点对来说都是O(1)查找。

解决所有对最短路径问题的弗洛伊德算法自然可以使用这样的矩阵，以及更复杂的子立方算法来解决各种图路径问题，利用环上更快的矩阵乘法。

来源

2014-10-21 03:46:09 wookie919

你说如果我只是想存储邻接关系，还有更多吗？ – sarat 2014-10-21 06:20:19

@sarat我以为我已经给出了其他的例子，但对不起，如果我不清楚。 'X [i] [j] = c'可能意味着从'i'到'j'的边缘成本是'c'，或者可能意味着从'i'到'j'的边缘容量是'c' 。你可以存储你喜欢的任何信息，真的。 – wookie919 2014-10-21 08:22:25

我明白你在说什么，但是我所问的是结构性差异。你给我的是一个邻接矩阵，其优点是用值表示边权重，我在示例中提到的是一个多路链表，它有助于一个动态的删除...我问有没有更像这些？ – sarat 2014-10-21 09:28:29

存储树和图的数据？

回答

相关问题