Graphs Flashcards
Trees
“We say that an undirected graph is a tree if it is connected and does not contain a cycle. In a strong sense, trees are the simplest kind of connected graph: deleting any edge from a tree will disconnect it.
Rooted trees are fundamental objects in computer science, because they encode the notion of a hierarchy
(3.1) Every n-node tree has exactly n − 1 edges.”
Breadth-first search
“we explore outward from s in all possible directions, adding nodes one “layer” at a time. Thus we start with s and include all nodes that are joined by an edge to s—this is the first layer of the search. We then include all additional nodes that are joined by an edge to any node in the first layer—this is the second layer.
Instead of all these distinct lists, we can implement the algorithm using a single list L that we maintain as a queue.
it produces, in a very natural way, a tree T rooted at s on the set of nodes reachable from s.
Running time
The above implementation of the BFS algorithm runs in time O(m + n) (i.e., linear in the input size), if the graph is given by the adjacency list representation.
Depth-first search
“You’d start from s and try the first edge leading out of it, to a node v. You’d then follow the first edge leading out of v, and continue in this way until you reached a “dead end”—a node for which you had already explored all its neighbors. You’d then backtrack until you got to a node with an unexplored neighbor, and resume from there.
t can also be viewed as almost identical to BFS, with the difference that it maintains the nodes to be processed in a stack, rather than in a queue. Essentially, the recursive structure of DFS can be viewed as pushing nodes onto a stack for later processing, while moving on to more freshly discovered nodes.
Running time
(3.13) The above implementation of the DFS algorithm runs in time O(m + n) (i.e., linear in the input size), if the graph is given by the adjacency list representation.”
QUEUE
A queue is a set from which we extract elements in first-in, first-out (FIFO) order: we select elements in the same order in which they were added. Both queues and stacks can be easily implemented via a doubly linked list. In a queue a new element is added to the end of the list as the last element,
STACK
A stack is a set from which we extract elements in last-in, first-out (LIFO) order: each time we select an element, we choose the one that was added most recently. Both queues and stacks can be easily implemented via a doubly linked list. while in a stack a new element is placed in the first position on the list.
Finding the Set of All Connected Components
We start with an arbitrary node s, and we use BFS (or DFS) to generate its connected component. We then find a node v (if any) that was not visited by the search from s and iterate, using BFS (or DFS) starting from v to generate its connected component—which, by (3.8), will be disjoint from the component of s.
Representing directed graphs
Now, instead of each node having a single list of neighbors, each node has two lists associated with it: one list consists of nodes to which it has edges, and a second list consists of nodes from which it has edges.
Directed Acyclic Graphs
“If an undirected graph has no cycles, then it has an extremely simple structure: each of its connected components is a tree.
DAGs are a verycommon structurein computer science, because many kinds of dependency networks of the type we discussed in Section 3.1 are acyclic. Thus DAGs can be used to encodeprecedencerelations ordependenciesin a natural way.”
Topological ordering
“Specifically, for a directed graph G, we say that a topological ordering of G is an ordering of its nodes as v1, v2, . . . , vn so that for every edge (vi, vj), we have i < j. In other words, all edges point “forward” in the ordering.
A topological ordering on tasks provides an order in which they can be safely performed; when we come to the task vj, all the tasks that are required to precede it have already been done.
(3.18) If G has a topological ordering, then G is a DAG.
(3.20) If G is a DAG, then G has a topological ordering.
(3.19) In every DAG G, there is a node v with no incoming edges.
Algorithm:
The key to this lies in finding a way to get started:
(3.19) In every DAG G, there is a node v with no incoming edges.
In fact, the existence of such a node v is all we need to produce a topological ordering of G by induction.
To bound the running time of this algorithm, we note that identifying a node v with no incoming edges, and deleting it from G, can be done in O(n) time. Since the algorithm runs for n iterations, the total running time is O(n2)
In fact, we can achieve a running time of O(m + n) using the same high- level algorithm—iteratively deleting nodes with no incoming edges”
