Graph Traversal

  • (2 Pages)
  • +
  • 1
  • 2

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

#16 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 13 April 2010 - 06:19 AM

View PostGalois, on 11 April 2010 - 03:41 PM, said:

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.


Oh i think iam getting it. If you traverse a graph like this you don't get the edge weight. So because of that its useless. You need to do a BFS or DFS so that edge weights are also considered.
Was This Post Helpful? 0
  • +
  • -

#17 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 15 April 2010 - 08:58 AM

Iam confused with graphs

take a look at this adjacency list

Posted Image

In an adjacency list such as that you definitely need to do a dfs or bfs but in the image below
Posted Image

You can just travel down the linked list?

Please help me.
Was This Post Helpful? 0
  • +
  • -

#18 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 771
  • Joined: 27-June 09

Re: Graph Traversal

Posted 15 April 2010 - 09:37 AM

View PostAu-Z-C, on 15 April 2010 - 07:58 AM, said:

Iam confused with graphs

take a look at this adjacency list

Posted Image

In an adjacency list such as that you definitely need to do a dfs or bfs but in the image below
Posted Image

You can just travel down the linked list?

Please help me.



I think you are missing the point of a graph. In many graph data structures, even the one in the first picture, you can always arbitrarily go to any vertex without traversing the graph. If you just want to scan all vertices, yes you can just travel down the list of vertices. For certain problems, this may be all you need to do. However, this is not traversing the graph. Traversing the graph means going from vertex to vertex only through edges connecting adjacent vertices. This is important for representing and computing certain relationships between the vertices. For example, in your first picture how many edges must I cross to get from 2 to 4? Since 2 is not connected to 4, you must first go from 2 to 3 then from 3 to 4. It is not enough to look for a common vertex that connects to both 2 and 4 because other graphs may require several intermediate edges to travel from a to b. I must use an algorithm that traverses the graph in order to find the solution. I cannot just scan the list of vertices and expect to compute my solution.
Was This Post Helpful? 2
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2