## 17 Replies - 2717 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

**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)?

### #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

Au-Z-C, 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 **Au-Z-C**: 11 April 2010 - 07:07 AM

### #12

## Re: Graph Traversal

Posted 11 April 2010 - 08:19 AM

*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.

### #13

## Re: Graph Traversal

Posted 11 April 2010 - 08:33 AM

Galois, on 11 April 2010 - 02:19 PM, said:

*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.

### #14

## Re: Graph Traversal

Posted 11 April 2010 - 08:44 AM

### #15

## Re: Graph Traversal

Posted 11 April 2010 - 09:41 AM