Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Check If Graph Is Connected?

Graph c#

  • Please log in to reply
5 replies to this topic

#1 Hobbel007

Hobbel007

    CC Lurker

  • New Member
  • Pip
  • 3 posts
  • Programming Language:Java, PHP, JavaScript, PL/SQL
  • Learning:C#

Posted 25 June 2012 - 04:32 AM

Hello,

I have an assignment to check if a given graph is connected or not.http://mathworld.wol...ectedGraph.html
But I don't know how to do this. I have a a graph class who contains a dictionary with all the vertex.
The Vertex class has a list with all the edges.
Now I have to check if the graph that is build is connected or not.
Can someone give me some clue's how to handle this problem?
The graph is also inserted as an attachment in this post

Attached Files


Edited by Hobbel007, 25 June 2012 - 05:33 AM.

  • 0

#2 Hobbel007

Hobbel007

    CC Lurker

  • New Member
  • Pip
  • 3 posts
  • Programming Language:Java, PHP, JavaScript, PL/SQL
  • Learning:C#

Posted 25 June 2012 - 07:04 AM

I found this pseudo code:

est-connected(G)
{
choose a vertex x
make a list L of vertices reachable
from x,
and another list K of vertices to be explored.
initially, L = K = x.

while K is nonempty
find and remove some vertex y
in K
for each edge (y, z)
if (z is not in L)
add z to both L and K

if L has fewer than n items
return disconnected
else return connected
}.

I tried to rewrite it but i'm stuck at the last part.


This is what I have now:
I'm stuck in the last while loop.
public Boolean connected(Graph g)
{
Boolean connected = true;
string index = vertexMap.Keys.First();
Vertex x = vertexMap[index];
LinkedList<Vertex> L = new LinkedList<Vertex>();
Dictionary<string, Vertex> K = vertexMap;
foreach(Edge e in x.adj)
{
L.AddFirst(e.dest);
}
while(K.Count != 0)
{
find and remove some vertex y in K
for each edge (y, z)
if (z is not in L)
add z to both L and K
}
if(L.Count < n items)
{
return false;
}
else
{
return true;
}
}
  • 0

#3 Yonatan

Yonatan

    CC Regular

  • Member
  • PipPipPip
  • 37 posts
  • Location:Israel
  • Programming Language:C, Java, C++, C#, JavaScript, PL/SQL, Visual Basic .NET
  • Learning:Python, JavaScript

Posted 25 June 2012 - 12:16 PM

First of all, add x to L, not its adjacent nodes.
and Init K to only x

than in the while.
Find and remove some vertex y from L
for each edge(y,z)
if z not in K.
add z both to K and L

after the while
if(K.count != N)
return false;

else
return true;

try that, let me know
  • 0

#4 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 25 June 2012 - 01:41 PM

To do this all you have to do is pick ONE vertex and show that there exits a path from the vertex to every other vertex.

How I would do this is use a modified version of Dijkstra's shortest path algorithm on a vertex. The algorithm should compute the length of a path from a vertex to all other vertices. So maintain an array of the length of the paths and set them to -1. Then run Dijkstra's and then iterate through the array and if you find a -1 then there is no path from vertex to some other vertex and your graph is disconnected.
  • 0

#5 Yonatan

Yonatan

    CC Regular

  • Member
  • PipPipPip
  • 37 posts
  • Location:Israel
  • Programming Language:C, Java, C++, C#, JavaScript, PL/SQL, Visual Basic .NET
  • Learning:Python, JavaScript

Posted 25 June 2012 - 02:09 PM

chili5, what is the complexity of running multiple dijkstras?
Just cause I think that in that way its O(|E|)

But im not sure, dont have much experience with this...
  • 0

#6 Hobbel007

Hobbel007

    CC Lurker

  • New Member
  • Pip
  • 3 posts
  • Programming Language:Java, PHP, JavaScript, PL/SQL
  • Learning:C#

Posted 29 June 2012 - 03:38 AM

I just used dijkstra from the first vertex and then just call dijkstra to the other vertexs and check if there's a path.
This works for know. I'm going to look to better ways to optimize.
  • 0




Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download