===== Chapter 3: Graphs ===== ==== 3.1 - Basic Definitions and Applications ==== A graph is made up of nodes and edges. A directed graph consists of a set of nodes and a set of directed edges. Most graphs are undirected. Applications of graphs include transportation networks, communication networks, information networks, social networks, and dependency networks. A path traversing a graph is simple if all its vertices are distinct from one another. A cycle is a series of nodes that cycles back to where it began. In a directed graph, the path or cycle must respect the directionality of edges. An undirected graph is connected if there is a path for every pair of nodes. The distance between two nodes is the minimum number of edges in the path. A tree is an undirected graph not containing a cycle. Relationships between adjacent nodes are define by ancestor or descendant. A leaf is a node with no descendants. Every n-node tree has exactly n-1 edges. Let G be an undirected graph on n nodes. Any two of the following statements implies the third: - G is connected - G does not contain a cycle - G has n-1 edges ==== 3.2 - Graph Connectivity and Graph Traversal ==== === Breadth-First Search === Explored outward from root adding one ‘layer’ at a time. The root and all nodes joined to the root make up the first later. For each j >= 1, layer L(j) produced by BFS consists of all nodes at distance j from root (s). There is a path from s to t iff t appears in some layer. Let T be a BFS tree, let x and y be nodes in T belonging to layers L(i) and L(j) respectively, and let (x,y) be an edge of G. Then i and j differ by at most 1. The set produced at the end of the algorithm is precisely the connected component containing the starting node. The actual path is recovered by finding the targeted node then tracing back to the starting node. === Depth-First Search === In depth-first search, begin at the root and follow the leading edge until a dead end. Backtrack until you find a node with an unexplored neighbor. This is best implemented recursively. For a given recursive call DFS(u), all nodes that are marked “Explored” between the invocation and end of this recursive call are descendants of u in T. Let x and y be nodes in T, and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other. === The Set of All Connected Components === For any two nodes s and t in a graph, their connected components are either identical or disjoint. An algorithm, either BFS or DFS, visits each node, connecting it properly. ==== 3.3 - Implementing Graph Traversal Using Queues and Stacks ==== A graph is represented by adjacency matrix or adjacency list. To build a graph, sets of nodes and edges are needed. An adjacency matrix is represented as an n x n matrix (n = set of nodes). This matrix allows for O(1) time when checking for given edges. The downside: representation takes O(n^2) space and inefficiency of finding incident edges. An adjacency list is better for sparse graphs (graphs with less than n^2 edges). There is a record for each node v, containing a list of nodes to which v has edges. The adjacency list uses O(m+n) space (m = set of edges, n = set of nodes). Queue is first-in, first-out order. Elements are placed at the end of the linked list. Stack is last-in, first-out order. Elements are placed at the beginning of the linked list. The BFS algorithm runs in time O(m+n) if the graph is given by the adjacency list representation. The DFS algorithm visits each node using a reverse adjacency list. It runs in time O(m+n) if the graph is given by the adjacency list representation. === Discussion === The breadth-first and depth-first search algorithms are pretty straight forward and have predictable run times. However, I was expecting an algorithm that would allow for O(n log n) access time using recursion to skip branches. This would only be implemented on an ordered tree though. In our situation using DFS and BFS, the time stays linear (which is acceptable). ==== 3.4 - Testing Bipartiteness: An application of Breadth-First Search ==== A bipartite graph is one where the node set V can be partitioned into sets X and Y in such a way that every edge has one end in X and the other end in Y. If a graph is bipartite, then it cannot contain an odd cycle. We can test a graph for bipartiteness by choosing some node s and coloring it red. The neighbors of s must be colored blue and, in turn, we must make the neighbors of blue nodes red. We continue this process until we have visited every node, similar to the BFS algorithm. Let G be a connected graph. Let L(1), L(2),… be the layers produced by BFS starting at node s. Then one of the following must be true: * There is no edge of G joining two nodes of the same layer. This graph is bipartite. * There is an edge of G joining two nodes of the same layer. This graph is not bipartite. ==== 3.5 - Connectivity in Directed Graphs ==== A directed graph in adjacency list representation has two associated lists for each node: nodes to which it has edges and nodes from which it has edges. A graph is strongly connected (or mutually agreeable) if, for every two nodes u and v, there is a path from u to v and a path from v to u. If u and v are mutually reachable, and v and w are mutually reachable, then u and w are mutually reachable. For any two nodes s and t in a directed graph, their strong components are either identical or disjointed. It is possible to compute the strong components for all nodes in a total time of O(m+n). ==== 3.6 - Directed Acyclic Graphs and Topological Ordering ==== If a directed graph has no cycles it is a directed acyclic graph (DAG). They can be used to encode precedence relations or dependencies in a natural way. A topological ordering of graph G is an ordering of its nodes as v(1), v(2), …, v(n) so that for every edge (v(i), v(j), we have i < j. All edges point forward in the ordering. If G has a topological ordering, then G is a DAG (and vice versa). In every DAG G, there is a node v with no incoming edges. This is the beginning of our algorithm. Then, recursively compute the topological ordering of G-{v} and append the order. The run time of this algorithm is O(n^2). === Discussion === With the expansion of the BFS and DFS applications, there is more of an understanding of how algorithm design follow strict patterns and rules are used to analyze increasingly complex structures. In previous courses, the tree structure was fairly unexplored but now is seen as a very complex and tricky structure. I am worried that directed and undirected graphs might become more complicated in future sections but have not had too much trouble with them too far.