图的分支分解
图的分支分解
提问于 2014-09-30 22:29:30
你好,
我想知道一种算法，以如下方式将图分解为具有排名的分支：
Rank | path (or tree branch)
0 1-2
1 2-3-4-5-6
1 2-7
2 7-8
2 7-9节点1将是根节点，节点6、8和9将是结束节点。分支的等级应该由直到根节点的分支节点的数量来给出。让我们假设这个图没有循环(但我希望没有这样的约束)
我是一名电气工程师，也许这是一个非常标准的问题，但到目前为止，我只找到了BFS算法来获得路径和所有的割集。我也不知道this是否适用。
我希望我的问题足够清楚。
PS:这个问题应该出现在堆栈溢出中吗？
回答 1
Stack Overflow用户
发布于 2014-10-01 13:42:35
从你的例子中，我做了一些假设：
当一个结点的度数大于2时，你想要进行分支，你的输入图是
对于增强的BFS，这可以从根r实现。下面将生成comp_groups，它将是一个组件列表(每个组件都是其成员顶点的列表)。在列表rank中，每个组件的排名将位于相同的索引下。
comp[1..n] = -1 // init all vertices to belong to no components
comp[r] = 0 // r is part of component 0
comp_groups = [[r]] // a list of lists, with the start of component 0
rank[0] = 0 // component 0 (contains root) has rank 0
next_comp_id = 1
queue = {r} // queues for BFS
next_queue = {}
while !queue.empty()
for v in queue
for u in neighbors(v)
if comp[u] == -1 // test if u is unvisited
if degree(v) > 2
comp[u] = next_comp_id // start a new component
next_comp_id += 1
rank[comp[u]] = rank[comp[v]] + 1 // new comp's rank is +1
comp_groups[comp[u]] += [v] // add v to the new component
else
comp[u] = comp[v] // use same component
comp_group[comp[u]] += [u] // add u to the component
next_queue += {u} // add u to next frontier
queue = next_queue // move on to next frontier
next_queue = {}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/26123359
复制相关文章
相似问题
腾讯云开发者
