Wk 5/6 : Graphs, MST's, Kruskal, Primm, BFS, DFS

Question 1

What is a path?

Answer 1

A

Question 2

What is a cycle?

Answer 2

.

Question 3

What is a subgraph?

Answer 3

.

Question 4

What is degree?

Answer 4

.

Question 5

What is min/max degree?

Answer 5

.

Question 6

What is the max # of edges in an undirected graph?

Answer 6

.

Question 7

What are connected components?

Answer 7

Can get from anyone node to another?

Question 8

What is the definition of the shortest path of a weighted graph??

Answer 8

.

Question 9

What is a tree? A rooted tree?

Answer 9

.

Question 10

What is a spanning tree?

Answer 10

.

Question 11

What is an acyclic graph?

Answer 11

.

Question 12

What is a bipartite graph?

Answer 12

.

Question 13

How do we store a graph? 2 options….

Answer 13

.

Question 14

When would we choose to use an adjacency-list representation over an adjacency-matrix representation of a graph? Why? What are the positives and negatives of each one?

Answer 14

When a graph is sparse, the adjacency list makes more sense (|V|^2&raquo_space; E.

If a graph is dense, or we need to quickly tell if there is an edge in between 2 vertices. (for ex. all pairs shortest paths)

Matrices use asympotically more memory than adj-lists, which use only Theta (E+V). But it provides a quick way to know if an edge is in the graph. It is also simpler and makes sense for small grapsh

Lists are easy to add data to, like weight functions and other variants.

Question 15

Which algorithms lean heavily on BFS?

Answer 15

Primm, Dijkstra

Question 16

What does BFS do in English?

Answer 16

Systematically explores the edges of G to find every vertex that is reachable from s.

Keeps track of the levels that each node is from s as it continually expands the frontier from s.

Creates a BFS tree that from s to any node reachable from s, hs the simple path which is the smallest number of edges.

Question 17

What does BFS use to keep track along the way, and what are the meanings…

Answer 17

Colors, white, grey, black.

white is undiscovered
grey is discovered, unprocessed.
black is processed.

grey can be next to whites and blacks. Blacks will not be next to whites.

Also keeps track of predecessors, ancestors….if u is on simple path from s to v, then u is an ancestor of v.

Question 18

What attributes of a node are stored in BFS?

Answer 18

u.d = distance from s.
u.pi = predecessor/parent
u.color = color.
( another )

Question 19

How do we know that BFS finds the shortest path from s to v?

Answer 19

[INSERT] see proof in book….

Question 20

How does DFS work in words?

Answer 20

searches all edges out of the current node until they’ve all been explored, then backtracks to the previous. process continues until we’ve discovered everything that’s discoverable from the source, then if there are still undiscovered vertices it makes additional calls.

Question 21

How is the tree created by predecessors in DFS different from that created in BFS?

Answer 21

you can actually have multiple independent trees with DFS. Really its a DF forest. Every vertex will end up in its own tree and these trees are disjoint.

Question 22

How is the coloring scheme of DFS similar to BFS? How does DFS coloring relate to d and f values.

Answer 22

Both use white - > gray - > black. d values are timestamps for discovery. f values are timestamps for being finished. a node is white when d is infinity. it is gray in between d and f and black after f.

Question 23

What is the definition of a minimum spanning tree? How many does a graph have?

Answer 23

connected, undirected graph with weight in amount of wire needed to connect each node.

we want the acyclic subset that connects all.

that’s a spanning tree, the one with minimum weight is the MST.

Could have more than one MST, but only one MST weight.

Question 24

What three things define a tree?

Answer 24

Connected, Acyclic, Undirected.

Question 25

What makes a tree into a forest?

Answer 25

It has disconnected parts.

Question 26

What makes an edge a safe edge wrt MST creation?

Answer 26

We start with A which is a subset of a MST. If we can add the edge {u,v} to A and still be a subset of a MST, then its safe.

Question 27

What is the difference between a cut, a light edge, and an edge “respecting” the cut?

Answer 27

A cut is (S, V-S). If an edge has one endpoint in S and the other in V-S, it crosses the cut.

If a sub-graph A has no edges that cross the cut, it respects it.

A light edge is one that crosses a cut and it’s weight is the minimum of any other edge crossing the cut (there can be more than one)

Question 28

What is the fundamental difference in Kruskal and Primm’s MST algorithms? More specifically, what is the generic MST and how do they each differ from it?

Answer 28

They use different techniques from the generic MST algorithm on how they determine if an edge is safe or not.

In Kruskal, the set A is a forest whose vertices are all those of the given graph. The safe edge that is added is a least weight edge that connects two distinct components.

In Prim, the set A forms a single tree. The safe edge that is added is a least weight edge that connects the tree to a vertex that is not in the tree.

While Kruskal is a forest with edges slowly added and doesn’t become a tree until the end, Prim is a tree the entire time.

Kruskal maintains a sorted list of all the edges, picking them up one at a time

Question 29

What is the definition of a greedy algorithm? Which algorithms that we’ve used does it work for?

Answer 29

At each decision make smallest cost decision at that place.

Works well for MST’s and is used by

Question 30

How does Greedy Algorithm work in MST? Where is the cost of the G.A.?

Answer 30

sort edges, check whether smallest is a cycle, then take it. continue until no more are left.

Cost is in the union’s, ie changing all the pointers.

Question 31

What algorithms are Greedy Algorithms?

Answer 31

Really, MST is the one where it happens to be advantageous overall to use G.A.

Question 32

What sub-structures are used in Greedy MST?

Answer 32

Make-set
Find-set
Union

Question 33

Why is Kruskal a greedy algorithm, and why do we know it works? What concept do we use to prove both of these?

Answer 33

Using the concept of a cut, when we cut smartly, with the MST respected by the cut, the lightest edge that crosses the cut HAS to be part of the MST, so each step we’re adding the lightest edge, the best one for this step which is the greedy part.

Question 34

What are the analogies of for Primm and Kruskal

Answer 34

Primm’s analogy is the club. I start with a club and dudes not in the club. Each dude outside the club, either knows someone inside, or doesn’t. His cost is how much he will pay the dude inside the club to let him in, to keep down corruption, we want the minimum payments to get in. We prioritize the least cost guy to get in. Once he’s in, everyone outside adjusts their cost to get in. (this new guy may let them get in for cheaper). Once everyone is in, the club is complete.

Kruskal, just looks down at the graph. He sees the shortest edges in order, he picks them up in order, and if they don’t make a cycle in the MST, then he adds them to the forest. There are scattered edges everywhere until the MST is finalizing.

Question 35

Why would I use Primm instead of Kruskal?

Answer 35

Intially, both of them run in O(m lg n) time, with Primm using ordinary binary heaps.

If we change Prim to use Fibonacci heaps, we can improve to O(m + n lg n). This is an improvement if n is much smaller than m.

Question 36

What is the definition of a graph traversal?

Answer 36

Moving from one point to another along the edges and knowing how many layers, or steps from the start to the end takes. The minimum # of edges from s to v.

Determines is a graph is connected (unconnected nodes still exist when we’re done with algorithm)

Can determine whether or not the graph has a cycle. (could help discover whether graph is bipartite…odd cycles are never bipartite)

If graph is unweighted, this is the shortest path.

Question 37

What is the naïve complexity of a graph traversal, and how do BFS and DFS improve on that?

Answer 37

Naively, you look at every vertex,

Question 38

How do we find the diameter using BFS?

Answer 38

Run BFS once. Take farthest node from my point….Run BFS again. farthest node from there is the other end.

Relies on fact that every node is either very far or very close to the ends of the diameter.

Question 39

What is the fundamental difference between BFS and DFS?

Answer 39

The Datastructure that they use. BFS uses a FIFO structure, while DFS uses a LIFO structure.

Other than that, they’re essentially the same thing, in terms of exploring nodes, coloring grey, black, white.

DFS stores a time of discovery as well and can determine cycles via knowing whether the graph contains edges that are back edges.

BFS uses the concept of a frontier, and/or fire spreading through the graph.

Question 40

How many times will we have to call DFS for connected vs. non-connected graphs?

Answer 40

If graph is connected, its called only once. If unconnected, might have to call it more than once.

Question 41

How do we determine if the cross-edges in a DFS are cross or back edges?

Answer 41

We use the time stamps and look at “inner walls” of d values.

Question 42

What is significant of a directed, acyclic graph? where would we want to use these?

Answer 42

A graph can be very dense and still not contain cycles. I can be almost complete…. We would want to use DAG’s in process graphs, and then use topological sort to determine what things to do in what order, ala the getting dressed analogy.

Question 43

Where is the datastructure for DFS maintained?

Answer 43

On the OS stack with the recursive calls of DFS-visit