Chapter 3: Graphs

A graph is a data structure used to represent relationship pairs in a group of objects. Graphs can be used to represent transportation networks, like where flights go to/come from in regards to an airport, communication networks, like data sharing between computers, information networks, like how the links on a particular website work, social networks, such as Facebook, and finally, graphs can represent dependency networks, which can represent how certain objects in a collection depend on one another. One of the main things we analyze in graphs is their paths (ways to trace through the graph) and connectivity (how the nodes in the graph are connected and how strong of a connection they share). Finally a graph is a tree is it connected and without a cycle. Trees start with a root and have n nodes with n-1 edges. This section was a way to introduce all of the pertinent information about graphs. It clarified what we had discussed in class and was a solid review of something we only briefly covered in 112. I would give it a 6/10 as although it was easy to understand and had a lot of solid information, it was still a review of something I already had a solid grasp of, so it was a tad boring.

Graphs can be represented by adjacency matrices and adjacency lists with lists being the preferred representation. Many of the algorithms dealing with graphs run in O(m+n) time with n representing the number of nodes and m representing the number of edges. However, an adjacency matrix requires O(n^2) space to create whereas a list only requires O(n+m) space, which is one of the reasons a list is generally used instead. In order to maintain a O(n+m) runtime in both the breadth first and depth first, we must use different data structures to maintain the lists of nodes we have already visited in the search. The breadth first search algorithm (page 90) can use a queue or a stack as the order in which we view the elements of a layer L[i] does not matter. However, storing the nodes in a queue works well as we always consider the layers of the tree in order. The BFS runs in O(n+m) time as the initialization steps take O(n) time and the while loop considers all of the m edges and thus runs in O(m) time. The depth first search algorithm (page 93) uses a stack to store the nodes as it “explores” them.