Chech if a graph is connected
-
Hello, How can I check if my graph stays connected, after removing one or more edges from it? I try to implement Christofides heuristik, and in some cases my code works (that is when the graph dosent disconnect under the process). Unlucky that is not the case for all the graphs. I use Dijkstras to check if there is a route from my last node in the edge I am to remove, to other nodes. But, how du I see that "this" edge if removed is disconnecting the graph, so I can leave the edge and try the next one? Thanks... It would be easier to understand if I could post a picture of the problem. :(
-
Hello, How can I check if my graph stays connected, after removing one or more edges from it? I try to implement Christofides heuristik, and in some cases my code works (that is when the graph dosent disconnect under the process). Unlucky that is not the case for all the graphs. I use Dijkstras to check if there is a route from my last node in the edge I am to remove, to other nodes. But, how du I see that "this" edge if removed is disconnecting the graph, so I can leave the edge and try the next one? Thanks... It would be easier to understand if I could post a picture of the problem. :(
how about a visited bool flag on each node. make it false on all node then start visit the graph from a root to all its connected node recursively and set the visited flag to true for each visited node when finished review all node, those with the false to false are disconnected, voila! :) For your information this is roughly what the GC is doing to find object to collect!! ^^
My programming get away... The Blog... DirectX for WinRT/C# since 2013! Taking over the world since 1371!