Topic 11- Graph Data Structures

Topic 11 – Graph Data Structures

Introduction

We end our journey with graphs. Graphs lift that limitation on trees where trees can only represent hierarchical relationships – graphs do not have this limitation. You use graphs theory in your head all the time. Unless you are totally brain dead and unable to get anywhere without a GPS, you have plotted a course from point A to Point B and driven there. This is a direct application of graph theory as you had to make a decision of route to get from A to B.

The map above represents a simple Graph. If I simplify here is the graph as a computer would see it.

Basics of Graphs

A graph is really made up of 2 elements; Nodes and Edges. The edges in turn may be directed (one way) or undirected (2 way). Edges may also have a value (like they do in this example). With these concepts; Adjacent Nodes (Neighbors) – Nodes connected to a given node by only one edge – we are able to perform all types of algorithms to traverse and analyze the graph. Read up on the graph at https://en.wikipedia.org/wiki/Graph_%28abstract_data_type%29

Khan Academy does an excellent job with understanding the representation of a Graph and as an added bonus shows an excellent method of how to represent the edges that makes it easy to understand the path analysis – https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/describing-graphs

Representations of Graphs

Graphs can be represented 3 ways, one is a physical drawing of the graph. This method is good for visualizing the graph, but not good for mathematical manipulation of the graph. The other 2 representations are a adjacency list and and adjacency matrix. An excellent discussion of these is included at Geeks for Geeks – http://www.geeksforgeeks.org/graph-and-its-representations/

Graph Traversal

When dealing with graphs in the computer science sense, there are 2 important algorithms – one to traverse the graph (ensuring all nodes are visited), and the other to find the shortest path. Think of driving directions in this case. You can look at algorithms for Graph Traversal at https://en.wikipedia.org/wiki/Graph_traversal . The most important algorithm for most practical applications is the shortest path problem – https://en.wikipedia.org/wiki/Shortest_path_problem You should seriously explore at least the basics of this. Specific code examples of Depth First Search and Breadth First Search in Javascript are at https://jsfiddle.net/reaglin/d8ncsejf/ . I also believe the implementation at Benoit Vallon is an excellent implementation and is easy to work with – http://blog.benoitvallon.com/data-structures-in-javascript/the-graph-data-structure/

Social Networks and Graphs

Graph theory has been fully applied to the analysis of social networks https://en.wikipedia.org/wiki/Social_network_analysis – This is a very large and expanding field as it is used for everything from determining likelihood of terrorist activity to figuring out what ads to place on your visited web pages. You should read through the wikipedia article to gain a basic understanding of the application of graph theory on networks.

What You Need to Know

You should understand and be able to implement;

  1. Differences between directed and undirected graphs
  2. Graph representations (ways to represent graphs mathematically and in code) (link)
  3. Graph traversal algorithms
  4. Graph search techniques – Breadth first ( link ) and Depth First
  5. Uses of the Depth First Traversal ( link ) and the Breadth First Traversal ( link )

Additional Resources

If you find additional resources that can help you or other students succeed in this course, please post to the discussion boards or email to Dr. Eaglin