h**********c
发帖数: 4120 | 1 Consider a DAG as a tree structure, maybe multiple root, even not connected,
(I don't if it is not connected, is it still DAG).
So, treat it like a tree. DAG has n nodes. We have all the nodes' references
. Each node has the storage of its parents ( immediate nodes where directed
edges are from). Each node also has the storage of its children ( immediate
nodes where the directed edges are toward).
The question is if we want to store the DAG with such a structure, what will
be the space complexity of node references?
Or DAG has other storage structure and the space complexity? | c****p
发帖数: 6474 | 2 相当于问DAG的度？best case O(1) (全不相连)，worst case O(n^2)（全相连）
connected,
references
directed
immediate
will
【在 h**********c 的大作中提到】
: Consider a DAG as a tree structure, maybe multiple root, even not connected,
: (I don't if it is not connected, is it still DAG).
: So, treat it like a tree. DAG has n nodes. We have all the nodes' references
: . Each node has the storage of its parents ( immediate nodes where directed
: edges are from). Each node also has the storage of its children ( immediate
: nodes where the directed edges are toward).
: The question is if we want to store the DAG with such a structure, what will
: be the space complexity of node references?
: Or DAG has other storage structure and the space complexity?
| h**********c
发帖数: 4120 | 3 用连通性来考虑，解释的比较清晰，
n^2 是肯定的了，
如果排除重复边，
n^2的full connection,是不是cycle了? | c****p
发帖数: 6474 | 4 不是重复边。
假设有一个全连通的无向图，就是n(n-1)/2 = O(n^2)条边。
然后把这些无向边变成有向边，变换方法如下：
把节点按1...n编号，则任何一条连接(不妨设uv的有向边。
边的数目不变，且没有cycle，即不可能存在一个当u>v时，u->v的通路。
而且每个结点都要保存子链接和父链接，所以实际算链接的数目时其实可以不考虑边的
方向性。【 在 heteroclinic (asymptotically stable) 的大作中提到: 】 | h**********c
发帖数: 4120 | 5 把O(n^2) 当成n^2 条边了，
thanks
【在 c****p 的大作中提到】
: 不是重复边。
: 假设有一个全连通的无向图，就是n(n-1)/2 = O(n^2)条边。
: 然后把这些无向边变成有向边，变换方法如下：
: 把节点按1...n编号，则任何一条连接(不妨设uv的有向边。
: 边的数目不变，且没有cycle，即不可能存在一个当u>v时，u->v的通路。
: 而且每个结点都要保存子链接和父链接，所以实际算链接的数目时其实可以不考虑边的
: 方向性。【 在 heteroclinic (asymptotically stable) 的大作中提到: 】
| h**********c
发帖数: 4120 | 6 A small debrief of DAG
For the DAG storage structure at post 1, the space complexity could be O(n^2
), given n the number of vertices the graph. So in the geometrical point of
view, such structure is awful. We may say one thousand and three thousand
don't differ too much. But one thousand differ scarily from one million. The
difference is O(n), O(n log n) and O (n^2).
But if we think in the topological way, that is, we observe the space
complexity of this structure in relation to the number of edges of DAG. The
result could be quite optimistic. Given number of edges m, the space
complexity is O(m), because for all the vertices, they can be stored at most
twice.
So the space complexity of such DAG structure is rather decided by the
number of edges. But we also see for DAG, the number of edges can never
exceed n^2, given no repeated edges.
connected,
references
directed
immediate
will
【在 h**********c 的大作中提到】
: Consider a DAG as a tree structure, maybe multiple root, even not connected,
: (I don't if it is not connected, is it still DAG).
: So, treat it like a tree. DAG has n nodes. We have all the nodes' references
: . Each node has the storage of its parents ( immediate nodes where directed
: edges are from). Each node also has the storage of its children ( immediate
: nodes where the directed edges are toward).
: The question is if we want to store the DAG with such a structure, what will
: be the space complexity of node references?
: Or DAG has other storage structure and the space complexity?
|
|
