A graph is a collection of vertices (nodes) and edges (the lines that connect them). They're unique in that they don't just model data, they model the relationship between objects. Furthermore, graphs do not have a single starting point. They can be traversed starting at any node.
Tree structures are also non-linear data structures. However, tree structures have one entry point (the root) and traversal moves in one direction, away from the root.
Undirected versus Directed
Undirected graphs model two-way relationships. Major highway systems can be modeled using an undirected graph. When driving from St. Louis, Missouri to New Orleans, Louisiana, you take 1-55 to 1-10. When driving from New Orleans to the St. Louis, you take I-10 to I-55. Every highway moves in both directions.
In this simple graph, the shortest path from A to E is the shortest path from E to A. The shortest path from the starting node to the ending node, when reversed, is the shortest path from the ending node to the starting node.
However, driving from your house to your friend's house in New Orleans is not as easy. You're probably going to have to take a few one way streets. The route from house A to house B, when reversed, will not transport you from house B to house A. This is how a directed graph works.
Much like you can take the same major street to and from work, directed graphs can have two-way relationships. However, edges are not bidirectional by default.
To get from A to E with the fewest number of stops, travel from A to B to D to E. You can't travel from E to D to B to A. You have to take a different route.
Weighted versus Unweighted
An unweighted graph only stores if a one- or two-way relationship exists between nodes. All the graphs we've looked at thus far are unweighted.
Adding data to the edge is where graphs get really interesting. I spend a lot of time window-shopping for Crocs on Amazon. Coincidentally, when Amazon sends me an email containing links to products I may like, Crocs always make the cut. Why is this?
Instead of just storing that a relationship exists, weighted graphs store data pertaining to that relationship. For example, the edge between my user node and the Crocs node contains a numerical field that is set to one the first time I visit the site. It is incremented with every additional visit.
When determining what products to include in email, Amazon can simply iterate over all the nodes with which I have a relationship and display products from those with the most visits.
In this graph we're just storing a weight. In the real world, the weight could represent the number of times a user looked at a profile or product or the distance in miles between cities.
Use Cases
Graphs are used all over the place. They are used in mapping applications. Mapping applications use weighted, directed graphs. They are weighted because, to provide you with the shortest route, the distance between intersections must be taken into account, as does speed limit, number of traffic lights, et cetera. They are directed because not every road is a two way street.
Social networks are made possible by graphs. They most likely use weighted, directed graphs as well to keep track of all the users a user follows. They also track the number of times a user visits another user. That's why when you start typing the name of a profile you've visited many times, it's the first on the list.
Objects and arrays can meet your needs much of the time. However, when you don't have a set entry point or you're concerned with the line that connects the node, turn no further than a graph.
Top comments (0)