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.

A bipartite graph is a graph that has a node set V that can be partitioned into a set of red nodes and blue nodes so that every edge has one red node and one blue node. It can be found that if a graph has an odd cycle, then it is not bipartite and if a graph has no odd cycles then it is bipartite. The odd-length cycle is the only thing that prevents a graph from being bipartite. In order to tell if a graph is bipartite we can use a breadth-first search and we can assign each layer a color. Then if any edges have the same color we know that the graph is not bipartite.

The breadth-first search algorithm runs in O(n+m).

This was a pretty easy concept to understand (it might be the colors) and the section just outlined what we had discussed in class.

This section was pretty clear, quick, and easy to read. I would give it an 8/10.

In a directed graph, edges have directions. Directed graphs can be represented by a list of nodes that each have two lists, one with the edges coming into it and another with the edges leaving it. In order to determine what the connected components are we can run either BFS or the DFS in the forwards direction and then in the backwards direction. A graph is strongly connected if for nodes u and v, there is a path from u to v and a path from v to u. Directed graphs also have a transitive property. That is, if u and v are mutually reachable and v and w are mutually reachable, then u and w are mutually reachable. Finally, for any two nodes, their strongly connected components are either disjoint or identical. This means that there cannot be a node t such that u and v are each strongly connected to t but not strongly connected to each other.

The algorithms to find the strongly connected components run in O(n+m) time.

I feel like a lot of the concepts in the graph sections are most easily explained by pictures. Such as the idea of a strongly connected component being either identical or disjoint. This is a pretty easy thing to draw out and see, but a little bit confusing to just think of as I was reading. Having the visual component in class is extremely helpful to internalize and understand.

I would give this section a 8/10. It was easy to understand and a helpful recap of directed graphs. I had gotten used to thinking of graphs as trees rather than graphs and the can be very different!

A directed graph which contains no cycles is referred to as a directed acyclic graph or a DAG. DAGs are useful to represent dependencies, such as the classes necessary to take in order to be a computer science major (i.e. there are some classes with prerequisites and it would be nice to know what you have to take in order to attend higher level classes) . We can show that a graph G has a topological ordering if and only if it has a topological ordering. A topological ordering is an ordering so the DAG elements in such a way that the edges point “forward”. The algorithm to find a topological ordering (text page 102) begins by finding a node that has no incoming edges. This way we know that every edge from this node will be pointing “forward”. Then we delete that node and find another node with no incoming edges. We repeat this process until we have added all of the nodes to our ordering. This algorithm runs in O(n+m) time if we are able to efficiently find the nodes with no incoming edges. This is achieved by maintaining a list of active nodes with no incoming edges and the number of edges each active node has going to other nodes. Using this we can reduce runtime from a formerly O(n^2) runtime.

I was a little confused on the O(n+m) run time. I mentioned this on my test, but I still get a little confused on how we determine whether to add or multiply runtimes.

I would give this section an 8/10. It was helpful and straightforward. The dependency concept is one I am comfortable and we definitely made a DAG similar to the one I described in the summary in 112.