Learning About the Graph Construct using Games, Part 1 - Variations on graph representation
(Page 4 of 7 )
Not all graphs are created equal! The nature of a graph varies widely by the nature of the problem we are trying to solve. Here we give the three most important variations, and how we can handle them.
Directed vs. Undirected Graphs
This is by far the most important variation. In our previous examples we were basically dealing with directed graphs; the word directed here refers to the edges. In all of the examples we have seen, edges had directions. An edge going from A to B is not necessarily also going the other way round. All our examples were based on this.
But, in real life, it doesn’t always work that way. In certain applications, the edges of a graph could have no specific direction. An edge just connects two nodes, and the direction is not important. This is the case with undirected graphs.
An example of a problem with directed graphs is the problem of World Wide Web representations, where pages are represented as nodes, and links are represented as edges. Clearly the direction of a hyperlink matters. If your site links to the Yahoo homepage, it does not mean the same thing as Yahoo putting a link to you on its front page! This is a typical example of a directed graph.
An example of an undirected graph is the initial example we gave about cities, and highways, where cities were represented as nodes, and highways represented as edges. We were interested to find the shortest path from city A to city B. In this example, there are no clear directions for edges. A highway connects two cities, and that’s pretty much it. (Well… I never heard about one way highways anywhere in the world. Please email me if you know any!)
Now, all of our discussion until now was about directed graphs. How can we handle undirected graphs? Should we throw everything out and start over? Absolutely not!
Basically to represent an undirected graph, we use either of the two methods explained above (adjacency lists and adjacency matrices), but for every edge, we actually add two edges in the graph. For example, to add an edge between A and B, we add an edge from A to B, and an edge from B to A.
We have to be careful though, because this approach can cause problems later if we are not careful. It is important to think of both edges as just one edge, not two. Any operation that is done to one must be done to the other.
By the way, directed graphs are drawn without any arrows on the edges. This is to indicate the edges have no specific direction.
Next: Weighted Edges >>
More Development Cycles Articles
More By Mohamed Saad
