Graph Traversal

  • (2 Pages)
  • +
  • 1
  • 2

17 Replies - 2473 Views - Last Post: 15 April 2010 - 09:37 AM

#1 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Graph Traversal

Posted 08 April 2010 - 09:54 AM

If i use a adjacency list to represent a graph then to traverse it i only have to traverse the linked list. Am i correct?
Is This A Good Question/Topic? 0
  • +

Replies To: Graph Traversal

#2 Galois  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Graph Traversal

Posted 08 April 2010 - 10:03 AM

Traverse how? Depth-first? Breadth-first?
Was This Post Helpful? 0
  • +
  • -

#3 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Graph Traversal

Posted 08 April 2010 - 10:11 AM

Consider the following adjacency list,

  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

Was This Post Helpful? 1
  • +
  • -

#4 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Graph Traversal

Posted 08 April 2010 - 10:18 AM

i mean if i use a adjacency list then all the vertices would be initialised like

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.
Was This Post Helpful? 0
  • +
  • -

#5 Galois  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Graph Traversal

Posted 08 April 2010 - 10:33 AM

If that's what your adjacency list looks like, then your graph is really just a list. In that case, sure, just go through a list element by element.
Was This Post Helpful? 0
  • +
  • -

#6 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Graph Traversal

Posted 08 April 2010 - 10:42 AM

View PostGalois, on 08 April 2010 - 04:33 PM, said:

If that's what your adjacency list looks like, then your graph is really just a list. In that case, sure, just go through a list element by element.


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.
Was This Post Helpful? 0
  • +
  • -

#7 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Graph Traversal

Posted 08 April 2010 - 10:48 AM

View PostAu-Z-C, on 08 April 2010 - 05:18 PM, said:

This is a basic graph. No subgraphs are present.


Actually, if there's a graph, it always contains a subgraph. ;)
Was This Post Helpful? 0
  • +
  • -

#8 Tom9729  Icon User is offline

  • Segmentation fault
  • member icon

Reputation: 180
  • View blog
  • Posts: 2,641
  • Joined: 30-December 07

Re: Graph Traversal

Posted 10 April 2010 - 05:17 PM

View PostGloin, on 08 April 2010 - 12:11 PM, said:

Consider the following adjacency list,

  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



Au-Z-C,
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)?
Was This Post Helpful? 0
  • +
  • -

#9 Galois  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Graph Traversal

Posted 10 April 2010 - 05:40 PM

Yes, Tom, what Gloin posted was an adjacency matrix. With that said, OP just needs to look at the material again, since he's obviously a bit confused about what traversal is and how graphs are represented.

This post has been edited by Galois: 10 April 2010 - 05:42 PM

Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10646
  • View blog
  • Posts: 39,536
  • Joined: 27-December 08

Re: Graph Traversal

Posted 10 April 2010 - 07:02 PM

View PostAu-Z-C, on 08 April 2010 - 01:42 PM, said:

View PostGalois, on 08 April 2010 - 04:33 PM, said:

If that's what your adjacency list looks like, then your graph is really just a list. In that case, sure, just go through a list element by element.


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
Was This Post Helpful? 0
  • +
  • -

#11 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Graph Traversal

Posted 11 April 2010 - 06:56 AM

Please have a look at the image.

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?

Posted Image

This post has been edited by Au-Z-C: 11 April 2010 - 07:07 AM

Was This Post Helpful? 0
  • +
  • -

#12 Galois  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Graph Traversal

Posted 11 April 2010 - 08:19 AM

No, you can't just start at the top and go downwards. Once you reach the third vertex you will be stuck, since there are no edges that connect it to vertex 4. In fact there are no edges come out of it. So vertex 3 needs to be visited last in your traversal.

Start at vertex 4. Use edge (4,1), then (1,2), then (2,3). That will traverse your graph.
Was This Post Helpful? 0
  • +
  • -

#13 Crunch  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 139
  • View blog
  • Posts: 1,222
  • Joined: 28-July 09

Re: Graph Traversal

Posted 11 April 2010 - 08:33 AM

View PostGalois, on 11 April 2010 - 02:19 PM, said:

No, you can't just start at the top and go downwards. Once you reach the third vertex you will be stuck, since there are no edges that connect it to vertex 4. In fact there are no edges come out of it. So vertex 3 needs to be visited last in your traversal.

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.
Was This Post Helpful? 0
  • +
  • -

#14 macosxnerd101  Icon User is offline

  • Self-Trained Economist
  • member icon




Reputation: 10646
  • View blog
  • Posts: 39,536
  • Joined: 27-December 08

Re: Graph Traversal

Posted 11 April 2010 - 08:44 AM

Each of Vertex[4]'s Edges go to a corresponding Vertex (ie., Edge[4][1] goes to Vertex[1]).
Was This Post Helpful? 0
  • +
  • -

#15 Galois  Icon User is offline

  • D.I.C Head

Reputation: 28
  • View blog
  • Posts: 207
  • Joined: 27-March 10

Re: Graph Traversal

Posted 11 April 2010 - 09:41 AM

OP, you don't understand what Graphs are. I strongly encourage you to either re-read the textbook material or find more resources online, Wikipedia as well as university websites are a good choice. Once you understand what graphs are, you can start tackling their traversal.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2