Help with graphs - breadth search

2 次查看（过去 30 天）
Sofia Melo Vasconcellos
编辑： Christine Tobler 2017-8-1
Hello I need help to traverse a graph using Breadth-first graph search, so that the following conditions are met:   The vertices are initialized with 1 unit of water and the processing begins at a vertex v whose degree of entry is 0. This vertex is marked as visited and, assuming v directs the flow to vertex u, then the vertex flow v is added to the current stream of vertex u. In addition, the edge connecting vertex v to vertex u is removed thereby reducing the degree of input of vertex u - this vertex u will be processed (visited) when its degree of input becomes 0.
Would anyone help me? Thank you from now

请先登录，再回答此问题。

回答（2 个）

Josh Meyer
Josh Meyer 2017-8-1
Christine Tobler
Christine Tobler 2017-8-1
编辑：Christine Tobler 2017-8-1
This should be possible using the digraph object. Since you are modifying the graph, it may be best to write a for-loop that will search for a node with indegree 0 (no incoming edges), modify the weight of the succeeding nodes, and so on. Here's a simple example
g = digraph(triu(bucky)); % Example digraph
g.Nodes.Water = ones(numnodes(g), 1);
while any(indegree(g) == 0 & outdegree(g) > 0)
v = find(indegree(g) == 0 & outdegree(g) > 0, 1);
u = successors(g, v); % This could be more than one node.
g.Nodes.Water(u) = g.Nodes.Water(u) + g.Nodes.Water(v) / length(u); % splitting up the water
g = rmedge(g, v, u);
end
This will do what I think you were describing. However, it may not be the most efficient, because removing edges from a graph one at a time in a loop can be very expensive. It may be cheaper to save the vectors outdegree and indegree, and update these vectors when removing the edges instead of actually modifying the graph. This should be considerably faster.
Also, your algorithm is based on the assumption that the digraph does not contain a cycle - otherwise, it will be caught in an endless loop.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by