# Graph Traversal

• (2 Pages)
• 1
• 2

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

### #1 Crunch

• D.I.C Lover

Reputation: 139
• 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

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

## Re: Graph Traversal

Posted 08 April 2010 - 10:03 AM

### #3 Gloin

• Expert Schmexpert...

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

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

• D.I.C Lover

Reputation: 139
• 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(){

for( ; tmp!=NULL; tmp=tmp->NextVertex ) cout << tmp->str << endl;

}

```

This is a basic graph. No subgraphs are present.

### #5 Galois

Reputation: 28
• 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.

### #6 Crunch

• D.I.C Lover

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

## Re: Graph Traversal

Posted 08 April 2010 - 10:42 AM

Galois, 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.

### #7 Gloin

• Expert Schmexpert...

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

## Re: Graph Traversal

Posted 08 April 2010 - 10:48 AM

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

### #8 Tom9729

• Segmentation fault

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

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

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 Galois

Reputation: 28
• 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

### #10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11790
• Posts: 44,311
• Joined: 27-December 08

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

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

### #11 Crunch

• D.I.C Lover

Reputation: 139
• 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?

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

### #12 Galois

Reputation: 28
• 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.

### #13 Crunch

• D.I.C Lover

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

## Re: Graph Traversal

Posted 11 April 2010 - 08:33 AM

Galois, 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.

### #14 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11790
• Posts: 44,311
• 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]).

### #15 Galois

Reputation: 28
• 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.