Differences
This shows you the differences between two versions of the page.
| courses:cs211:winter2018:journals:holmesr:section_3.5 [2018/02/06 02:41] – created holmesr | courses:cs211:winter2018:journals:holmesr:section_3.5 [2018/02/06 04:37] (current) – holmesr | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ====== Section 3.5 Connectivity in Directed Graphs ====== | ====== Section 3.5 Connectivity in Directed Graphs ====== | ||
| + | |||
| + | First, directed graphs require two adjacency lists in order to be properly represented since an edge may go from node //u// to node //v// but not return from //v// to //u//. One lists represents the edges that leave a node and the nodes that those edges connect to, and the other list represents the edges which lead to a node and from which node they come. They are called the //from list// and the //to list//, respectively. | ||
| + | |||
| + | The graph search algorithms BFS and DFS perform almost the same with directed graphs as they do with undirected graphs. The major difference being that they use a node's //from list// to traverse through the nodes which the current node has an edge from itself to them. It is important to note that in a directed graph, a node //n// can have a path to node //r//, but node //r// is not required to have a path back to node //n//. The graph traversals are discovering nodes to which //n// has a path; these paths are not necessarily reciprocated. | ||
| + | |||
| + | It is interesting that these traversals are finding all the nodes to which node //n// has a path, but to find all the nodes with paths to //n//, the same traversal can be run on an identical graph with the directions of the edges reversed. This leads into a discussion of strong connectivity and mutual reachability. | ||
| + | |||
| + | A graph is strongly connected if all nodes u and v which have paths (u,v) also have paths (v,u). In other words, if all nodes are mutually reachable to one another. An interesting property of mutual reachability is that if two nodes are mutually reachable and a third node is mutually reachable to one of those two, then it is mutually reachable to the other also. | ||
| + | |||
| + | The strong component is an analog to the connected component in an undirected graph. The strong component in a graph G is the set of nodes //n// which are mutually reachable from the nodes //s//. The a set of nodes is a strong component if that set is returned by a BFS started at node //n// on graph G and also returned by a BFS started at node //n// on a graph G< | ||
