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.

There are two general methods for searching through the connected nodes of a tree; breadth-first search(BFS) and depth-first search (DFS). BFS looks at a tree in layers, with the first layer being the root node and each successive layer being the nodes directly connected to the nodes in the layer before it. This creates a bushy tree. If a node is not contained in any layers, then we can safely say that the node is not connected and there is no path to it. DFS looks at a tree in paths, beginning with the left branch of the tree. The search will follow a path until it reaches a dead end and then back track and follow a new path. This creates a spindly tree. The set of all of the connected nodes is called the connected component. The algorithm for finding the connected component (page 82) is a very general algorithm and can be implemented using either type of search. If two nodes share a connected component, that connected component is identical. If two nodes do not share a connected component, then the connected components are entirely disjoint.

This section provides a strong introduction to the ways we can iterate and search through a graph.

I would give the section a 7/10 as it was very informative, but the explanations of the searches were a lot to take in. they confused me a little so I am glad that we spent time on these in class.

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. The DFS will also run in O(n+m) time as the initialization steps take O(n) time and we will add at most 2m nodes to the stack, running in O(m) time. We can uses both types of searches to find all of the connected components in a graph. These searches will also run in O(n+m) time as even though the algorithm may run DFS or BFS multiple times, only uses constant time to look at a given edge or node.

The motivation behind these algorithms is to find an efficient algorithm to determine whether or not a graph is connected and to what degree the graph is connected.

I am still a little foggy on how the bottom half of the algorithm runs in O(m) time and how this relates to it running in O(degree(u)) time. This distinction seems to be escaping me although I understand how everything else is set up.

I would give this section a 7/10 because although it was pretty easy to read, I still got a little jumbled up in the explanations.