YaccConstructor / QuickGraph

Generic Graph Data Structures and Algorithms for .NET
http://yaccconstructor.github.io/QuickGraph/
Microsoft Public License
530 stars 198 forks source link

Can someone give a simplest example of BFS? #189

Open petrasvestartas opened 5 years ago

petrasvestartas commented 5 years ago

I have undirected-graph below, and try to compute bfs, but I do not how how to get the visited edges. So far I have: The test file is too difficult for me to understand in the GitHub repository. HELP

//Create undirected graph
UndirectedGraph<string, Edge<string>> g = new UndirectedGraph<string, Edge<string>>();

g.AddVertexRange(N);
for (int i = 0; i < U.Count; i++){
  g.AddEdge(new QuickGraph.Edge<string>(U[i], V[i]));
 }

//BFS
 var algo = new QuickGraph.Algorithms.Search.UndirectedBreadthFirstSearchAlgorithm<string, QuickGraph.Edge<string>>(g);
jnyrup commented 5 years ago

Here's a complete example:

UndirectedGraph<string, Edge<string>> g = new UndirectedGraph<string, Edge<string>>();

g.AddVerticesAndEdge(new Edge<string>("0", "1"));
g.AddVerticesAndEdge(new Edge<string>("0", "2"));
g.AddVerticesAndEdge(new Edge<string>("2", "3"));

var algo = new UndirectedBreadthFirstSearchAlgorithm<string, Edge<string>>(g);

var observer = new UndirectedVertexPredecessorRecorderObserver<string, Edge<string>>();

var rootVertex = "0";
using (observer.Attach(algo))
{
    algo.Compute(rootVertex);
}

var targetVertex = "3";
bool foundPath = observer.TryGetPath(targetVertex, out IEnumerable<Edge<string>> path);

path will then contain the two edges:

[0]: "0"->"2"
[1]: "2"->"3"