s ravi chandran wrote:Thanks for the feedback.
You're welcome!
s ravi chandran wrote:I am not sure where is the edge count, the line I see is this:
This is definitely the vertices found and not the edge. Graph is not connected, that might be correct as there is no edge between 2-->3. Am I getting it wrong?
Well, yes and no. First of all, I misread 'vertexFound' as 'EdgeFound'. My bad, I apologize. But look what happens here. If you find that the pair(v1, v2) is connected, you do 'vertexFound++', and thus for every isConnected(v1, v2) you count a vertex. But 'isConnected(v1, v2)' also means that there is an edge between v1 and v2, and thus 'vertexFound' is equal to 'EdgeFound'. Think about it.
And also, you have that 'vertexFound' == 5, while there are 5 vertrices. So, why not conclude that the graph is connected, since we 'found all the vertices'? Complicated, isn't it? But then again, great excersize!
Then, as promised, an new explanation of the Queue method.
We start with the graph(5, true), with the edges (0, 1), (0,2), (2, 3), (2, 4) and (4, 5). By the way: wouldn't it be handy to have a Graph-method 'addEdge(int i1, int i2), somewhat simpler to use than 'addEdge(new Edge<>(i1, i2)'.
Now, if we make a drawing of the graph, we get:
Clearly connected.
Let's start with a random vertex, say 2. For the Queue we take a LinkedList<Integer>, and for Visited we take a Set<Integer>.
We start by putting 2 in the Queue and in the Visited.
Then the whole sv=cheme becomes:
Queue | head | remaining Q | neighbors | Visited | rem. neighbors | new Visited | new Queue | Queue empty? |
2 | 2 | empty | 0, 3, 4 | 2 | 0, 3, 4 | 0, 2, 3, 4 | 0, 3, 4 | No |
0, 3, 4 | 0 | 3, 4 | 1, 2 | 0, 2, 3, 4 | 1 | 0, 1, 2, 3, 4 | 3, 4, 1 | No |
3, 4, 1 | 3 | 4, 1 | 2 | 0, 1, 2, 3, 4 | - | 0, 1, 2, 3, 4 | 4, 1 | No |
4, 1 | 4 | 1 | 2, 5 | 0, 1, 2, 3, 4 | 5 | 0, 1, 2, 3, 4, 5 | 1, 5 | No |
1, 5 | 1 | 5 | 0 | 0, 1, 2, 3, 4, 5 | - | 0, 1, 2, 3, 4, 5 | 5 | No |
5 | 5 | - | 4 | 0, 1, 2, 3, 4, 5 | - | 0, 1, 2, 3, 4, 5 | - | Yes |
Now, is Vuisited equal to the list Of Vertices? Yes. So, graph is connected. Now, remove edge (0, 2) and repeat the procedure. Do we now find that the graph is unconnected?
Remains to put this table into real code. Reread my early description of the Queue method.
And since I typed the whole table from the keyboard, there may be the odd mistakes...