17 Replies  2562 Views  Last Post: 15 April 2010  09:37 AM
#1
Graph Traversal
Posted 08 April 2010  09:54 AM
Replies To: Graph Traversal
#2
Re: Graph Traversal
Posted 08 April 2010  10:03 AM
#3
Re: Graph Traversal
Posted 08 April 2010  10:11 AM
A B C D E F A 0 1 1 0 0 0 B 1 0 1 0 0 0 C 1 1 0 0 0 0 D 0 0 0 0 1 1 E 0 0 0 1 0 1 F 0 0 0 1 1 0
It represents a graph containing two disjoint subgraphs and you can't traverse all nodes in this graph with either BFS or DFS. So my immediate answer would be no.
Are there any characteristics of your graph that prevents this and like Galois asked, how are you planning to traverse the graph?
This post has been edited by Gloin: 08 April 2010  10:11 AM
#4
Re: Graph Traversal
Posted 08 April 2010  10:18 AM
class Vertex{ Vertex *NextVertex; Vertex(char *str){ this>str = str; NextVertex = NULL; } };
then to display all the nodes i can traverse the Vertex linkedlist.
printall(){ Vertex *tmp=head; for( ; tmp!=NULL; tmp=tmp>NextVertex ) cout << tmp>str << endl; }
This is a basic graph. No subgraphs are present.
#5
Re: Graph Traversal
Posted 08 April 2010  10:33 AM
#6
Re: Graph Traversal
Posted 08 April 2010  10:42 AM
Galois, on 08 April 2010  04:33 PM, said:
I didn't inlcude the code for Edges. I guess its the usual way of implementing a adjacency list isnt it. All the Vertices are on one linkedlist and the edges spread out from that.
#7
Re: Graph Traversal
Posted 08 April 2010  10:48 AM
#8
Re: Graph Traversal
Posted 10 April 2010  05:17 PM
Gloin, on 08 April 2010  12:11 PM, said:
A B C D E F A 0 1 1 0 0 0 B 1 0 1 0 0 0 C 1 1 0 0 0 0 D 0 0 0 0 1 1 E 0 0 0 1 0 1 F 0 0 0 1 1 0
It represents a graph containing two disjoint subgraphs and you can't traverse all nodes in this graph with either BFS or DFS. So my immediate answer would be no.
Are there any characteristics of your graph that prevents this and like Galois asked, how are you planning to traverse the graph?
Isn't that an adjacency matrix?
An adjacency list would look more like this.
A => B, C B => A, C C => A, B D => E, F E => D, F F => D, E
AuZC,
If you have a list of vertices then you really can't just go through the list to traverse the graph because for example say your list L = { A, B, C, D }; you want to go A>B>C>D but what if there is no edge between (A,B) or (B,C) or (C,D)?
#9
Re: Graph Traversal
Posted 10 April 2010  05:40 PM
This post has been edited by Galois: 10 April 2010  05:42 PM
#10
Re: Graph Traversal
Posted 10 April 2010  07:02 PM
AuZC, on 08 April 2010  01:42 PM, said:
Galois, on 08 April 2010  04:33 PM, said:
I didn't inlcude the code for Edges. I guess its the usual way of implementing a adjacency list isnt it. All the Vertices are on one linkedlist and the edges spread out from that.
Huh? Vertices are Edges. What I did when I designed a Graph class was to encapsulate a List of Edges in the Graph class, then have the Edges point to other Edges (handled in the Edge class). So that way, we have easy access to the Edges without hampering the Graph Structure.
It sounds like you are a little confused on how Graphs work, as I remember your other thread about comparing Graphs and Linked Lists. I've actually written tutorials about designing both data structures in Java. While you are using C/C++, you may find my tutorials helpful for nothing else than concepts. Below are the links:
http://www.dreaminco...topic163842.htm
http://www.dreaminco...topic143089.htm
#11
Re: Graph Traversal
Posted 11 April 2010  06:56 AM
So in the image you can see that there is a link from one vertex to the next. So can't i start from the top most vertex and traverse downwards?
This post has been edited by AuZC: 11 April 2010  07:07 AM
#12
Re: Graph Traversal
Posted 11 April 2010  08:19 AM
Start at vertex 4. Use edge (4,1), then (1,2), then (2,3). That will traverse your graph.
#13
Re: Graph Traversal
Posted 11 April 2010  08:33 AM
Galois, on 11 April 2010  02:19 PM, said:
Start at vertex 4. Use edge (4,1), then (1,2), then (2,3). That will traverse your graph.
Start at vertex 4? To reach vertex 4 you have to go through Vertex 1 , 2, 3. Why would you have to go through edges?
You can travel from head of graph and go down.
So then the order will be
Vertex 1, Vertex 2, Vertex 3, Vertex 4
Please tell me why the above graph traversal is wrong.
#14
Re: Graph Traversal
Posted 11 April 2010  08:44 AM
#15
Re: Graph Traversal
Posted 11 April 2010  09:41 AM
