A graph allows us to encode pairwise relationships among a set of nodes. Each graph has both a set of nodes and a set of edges. Each edge connects two nodes. For a directed graph, it is important to note the direction of the edge in a ordered pair with the first node listed being the node that points to the second node listed. There are many examples of graphs. We can use graphs to model a transportation network, with nodes representing stops and edges representing direct routes between stops. Generally these are undirected graphs, but a directed graph is certainly conceivable. We can use graphs to model communication networks, with edges representing physical links between computer nodes. We can use graphs to model the World Wide Web with nodes representing web pages and edges representing hyperlinks. Since not all pages link back to every page that links to them, these graphs are directed. We can use graphs to model social networks, with nodes representing people and edges representing friendships or relationships. We can also use directed graphs to model dependency networks, like the prerequisites for taking a college course.

A path in an undirected graph is the sequence of nodes needed to get from one node to another. A “simple” path does not repeat any nodes, while a “cycle” ends where it began. A path in a directed graph is similar to a path in an undirected graph: we just need to make sure that we keep the directionality of the edges in mind. A “connected” undirected graph occurs when there is a path from every node to every other node. A “strongly connected” directed graph occurs when there is a path from every node to every other node, keeping in mind that the path must respect the directionality of the edges. The “distance” between any two nodes is the shortest path required to get from one node to the other. An “tree” is an undirected graph with no cycles. This allows us to represent a hierarchy.

Readability: 7/10

The s-t connectivity problem asks if there is a path from node s to node t. Two algorithms for answering this problem are breadth-first search and depth-first search. Breadth first search puts node s in the first layer, and every node that has an edge with s goes in the second layer. Every new node that has an edge with a node in the second layer goes in the third layer, and this continues until no new nodes are found. The distance between nodes s and t is how many layers away they are. Breadth first search also gives us a tree rooted at s. Any nodes in the tree that have edges but are not in a parent-child relationship are at most one layer way. We can call all the nodes in these layers a connected component.

Depth-First search follows edges from s until it reaches a dead end. It then backtracks to a node with an unexplored edge and continues on that path until it reaches a dead end at which point it backtracks again. If we eventually get to t then we know there is a path from s to t.

Readability: 7/10

A graph can either be represented with an adjacency matrix or an adjacency list. For more sparsely linked graphs, an adjacency list makes sense because we often need to look at all nodes connected to a particular node. While this is O(n) for both the matrix and the list, if a we assume a sparsely linked graph, the list requires less actual steps. Because both Breadth First Search and Depth First Search need to process a set of elements, we can maintain these elements in a linked list. We can use the linked list as a either a queue (first in first out) or a stack (last in first out). For Breadth First Search, we can have an array that tells if a node has already been seen or “discovered”. For Breadth First Search, we can use either queues or stacks to get O(m+n) (Where n is the number of nodes and m is the number of edges). For Depth First Search, we add all nodes adjacent to our current node to the stack, and then chose one path to follow. The stack works well because we only backtrack after all paths at the current node have been looked at. While these algorithms run on O(n+m) time, they do not necessarily find all nodes because they might not be part of the connected component, so finding connected components in O(n+m) as well.

Readability: 7/10

A bipartite graph is one in which the set of nodes can be partitioned into two sets such that every edge has a node in one set and a node in the other. If a graph is bipartite, then it has no odd length cycles. To test for bipartiteness, we can perform a Breadth First Search and assign every odd numbered layer to one group and every even numbered layer to the other group. We can then test each edge to make sure that it has one node in the odd group and one node in the even group. The whole process will be O(n+m) because it is a Breadth First Search plus some O(m) which will just increase in the coefficient on m and we do not need to worry about coefficients. If we show the graph is not bipartite, then there must be an odd length cycle.

Readability: 7/10

To represent a directed graph, we give each node two lists of neighbors. One list contains the nodes to which it has edges and one the nodes from which it has edges. Breadth First Search is similar to the undirected graph, but it only tells us if there is a path from the seed node to another found node, and not the other way around. To accomplish the opposite, we can reverse every edge and perform the algorithm again. Depth first search also works similar to the case for an undirected graph. If there is a path from one node to another, and also a path back, then the nodes are considered mutually reachable. If all nodes are mutually reachable, the directed graph is strongly connected. If nodes a and b are mutually reachable and nodes b and c are mutually reachable, then nodes a and c are mutually reachable as well.

Readability: 6/10

A directed graph with no cycles is called a Directed Acyclic Graph. We can use a DAG to represent dependencies or precedence relationships. A topological ordering of a DAG is an ordering of nodes in which each edge points forward along the list. Therefore, the first node must have no edge pointing to it. Some facts about DAG's: if a graph has a topological ordering, then it is a DAG, and if a graph is a DAG, then it must have a topological ordering. The compute the topological ordering of a DAG, we find a node with no incoming edges, delete it from the graph, and add it to the topological ordering. We recursively find nodes with no incoming edges, and add each of those to the topological ordering in the order they were found. We can achieve a running time of O(n+m) for this algorithm if we also keep track of nodes that have not yet been deleted (active nodes). For each node, we keep track of the number of incoming edges that it has from active nodes, and we keep track of all the active nodes that do not share an edge with an active node. This way, we can subtract the number of edges from each node incident to the one deleted, which makes it faster to find the next node with no incoming edges.

Readability: 7/10