Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2018:journals:lesherr:home:chapter3 [2018/02/05 00:02] – [Section 5] lesherr | courses:cs211:winter2018:journals:lesherr:home:chapter3 [2018/02/05 00:19] (current) – [Section 6: Directed Acyclic Graphs and Topological Ordering] lesherr |
|---|
| ===== Section 5: Connectivity in Directed Graphs ===== | ===== Section 5: Connectivity in Directed Graphs ===== |
| 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. | 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 ===== | ===== 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. |
| |
| |
| |
| |
