| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:lesherr:home:chapter3 [2018/02/04 23:47] – [Section 4] lesherr | courses:cs211:winter2018:journals:lesherr:home:chapter3 [2018/02/05 00:19] (current) – [Section 6: Directed Acyclic Graphs and Topological Ordering] lesherr |
|---|
| In this chapter, we see that BFS and DFS essentially only differ in that one uses a queue and the other uses a stack. There are two main ways of representing graphs: as adjacency matrices, and as adjacency lists. Graphs have two main inputs, which are nodes and edges. When discussing the run time of algorithms that deal with graphs, we denote run times using the edges and nodes. Adjacency matrices are nxn matrices where a 1 denotes an edge between a row/column, and a 0 means there is no edge. This representation allows is to check in constant time whether a particular edge exists in the graph. However this representation takes O(n^2) space, and takes O(n) to see find all edges incident to a particular node. Adjacency lists word better for 'sparse graphs', which have fewer than n^2 edges. In adjacency lists, there is an array of lists that contain all the edges for each node. Adjacency lists take up O(m+n) space, take O(degree(u)) to see if an edge exists, and takes O(m) to find all the edges incident to a node. 'A queue is a set from which we extract elements in first-in, first-out (FIFO) order (select elements in the same order in which they were added. A stack is a set from which we extract elements in last-in, first-out (LIFO) order (select elements in the opposite order in which they were added). In both structures, you select the first element in the list, however in queues you add to the end of the list and in stacks you add to the front of the list. The adjacency list structure is ideal for the BFS algorithm, as for each node visited you want to see what nodes it is connected to. 'The BFS algorithm runs in O(m+n) if the graph is given by the adjacency list representation.' For the BFS either a queue or a stack can be used. For the DFS, you use a stack to maintain the set of nodes, which maintains its recursive structure. 'The DFS algorithm runs in O(m+n) if the graph is represented by an adjacency matrix.' This section was quite easy to traverse and understand. I would give it an 8/10. | In this chapter, we see that BFS and DFS essentially only differ in that one uses a queue and the other uses a stack. There are two main ways of representing graphs: as adjacency matrices, and as adjacency lists. Graphs have two main inputs, which are nodes and edges. When discussing the run time of algorithms that deal with graphs, we denote run times using the edges and nodes. Adjacency matrices are nxn matrices where a 1 denotes an edge between a row/column, and a 0 means there is no edge. This representation allows is to check in constant time whether a particular edge exists in the graph. However this representation takes O(n^2) space, and takes O(n) to see find all edges incident to a particular node. Adjacency lists word better for 'sparse graphs', which have fewer than n^2 edges. In adjacency lists, there is an array of lists that contain all the edges for each node. Adjacency lists take up O(m+n) space, take O(degree(u)) to see if an edge exists, and takes O(m) to find all the edges incident to a node. 'A queue is a set from which we extract elements in first-in, first-out (FIFO) order (select elements in the same order in which they were added. A stack is a set from which we extract elements in last-in, first-out (LIFO) order (select elements in the opposite order in which they were added). In both structures, you select the first element in the list, however in queues you add to the end of the list and in stacks you add to the front of the list. The adjacency list structure is ideal for the BFS algorithm, as for each node visited you want to see what nodes it is connected to. 'The BFS algorithm runs in O(m+n) if the graph is given by the adjacency list representation.' For the BFS either a queue or a stack can be used. For the DFS, you use a stack to maintain the set of nodes, which maintains its recursive structure. 'The DFS algorithm runs in O(m+n) if the graph is represented by an adjacency matrix.' This section was quite easy to traverse and understand. I would give it an 8/10. |
| ===== Section 4: Testing Bipartiteness: An Application of Breadth-First Search ===== | ===== Section 4: Testing Bipartiteness: An Application of Breadth-First Search ===== |
| 'A bipartite graph is a graph where the node set can be partitioned into sets X and Y in such a way that ever edge has one end in X and the other end in Y.' A way to restate this is a graph that can have its nodes split into two colored groups where no node in one group has an edge to another node in that group. Every edge of the graph should have a node of one color on one end and a node of a different color on the other end. One characteristic of a bipartite graph is that it cannot contain an odd cycle. A BFS of an algorithm must have 1 of the following two characteristics: 'there is no edge of G joining two nodes of the same layer', or 'there is an edge of G joining two nodes in the same layer'. If the first condition is true, then the graph can be colored in such a way that the definition of bipartiteness is true, however if the second condition is true then the graph has an odd length cycle and therefore is not bipartite. I have prior experience with graphs and conditions for bipartite graphs, so this section was very easy to understand. I'd give it a 9/10. | 'A bipartite graph is a graph where the node set can be partitioned into sets X and Y in such a way that ever edge has one end in X and the other end in Y.' A way to restate this is a graph that can have its nodes split into two colored groups where no node in one group has an edge to another node in that group. Every edge of the graph should have a node of one color on one end and a node of a different color on the other end. One characteristic of a bipartite graph is that it cannot contain an odd cycle. A BFS of an algorithm must have 1 of the following two characteristics: 'there is no edge of G joining two nodes of the same layer', or 'there is an edge of G joining two nodes in the same layer'. If the first condition is true, then the graph can be colored in such a way that the definition of bipartiteness is true, however if the second condition is true then the graph has an odd length cycle and therefore is not bipartite. I have prior experience with graphs and conditions for bipartite graphs, so this section was very easy to understand. Talking about in class before reading this section also made it very easy to follow and understand. I'd give it a 9/10. |
| ===== Section 5 ===== | ===== Section 5: Connectivity in Directed Graphs ===== |
| ===== Section 6 ===== | Previously, we have only been considering undirected graphs, where each edge has no particular orientation. In a directed graph, an edge does have direction and goes from one node u to a node v. 'The relationship between u and v is asymmetric, which changes the structure of the graph.' To represent an undirected graph, we use an adjacency list, where each node has a list of nodes to which it has edges, and a list of nodes from which it has edges. Thus the algorithm can go one step forward or one step backward from a particular node. BFS and DFS are the exact same for directed graphs as they were for undirected graphs. BFS has a running time of O(m+n) once again. However, for directed graphs it is possible to have a path from s to t and no path from t to s. You can also find a set of nodes with paths to s by creating a graph of reversed edges, and finding the paths from s to nodes in that graph. A directed graph is strongly connected if for every two nodes u and v, there is path from u to v and a path from v to u. This can also be restated as a graph that every pair of nodes is mutually reachable. 'If u and v are mutually reachable, and v and b are mutually reachable, then u and w are mutually reachable. The strong component of a graph is the set of all v such that s and v are mutually reachable. For any two nodes s and t in a directed graph, their strong components are either identical or disjoint. It is possible to compute the strong components for all nodes in a total time of O(m+n). This section was easy to understand. I would give it an 8/10. |
| | ===== Section 6: Directed Acyclic Graphs and Topological Ordering ===== |
| | 'If an undirected graph has no cycles, then it has an extremely simple structure: each of its connected components is a tree.' A directed graph with no cycles is called a directed acyclic graph (DAG). DAGs are very common in computer science, since lots of dependency structures are acyclic. DAGs are useful to encode precedence relations or dependencies in a natural way. Business position heirarchies can be represented very accurately with directed acyclic graphs (i.e. who reports to whom, who is the boss of who). A topological ordering of a graph is an ordering of nodes so that every edge points forward in the ordering from a node of lower numbering to a node of higher numbering. 'If a graph has a topological ordering, then G is a DAG.' 'In every DAG, there is a node with no incoming edges.' The total running time of this algorithm is O(n^2). However, it can be improved to be O(m+n) with a more efficient algorithm. This section was a little more difficult to understand. Once it is gone over in class, it should be more easy to understand. I'd give this section a 7/10. |
| |
| |
| |
| |
