Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Software Engineering > Graph Algorithms > Flashcards

Graph Algorithms Flashcards

1
Q

What kinds of graphs are there?

A

Directed or undirected, weighted or unweighted, connected or unconnected.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the graph black boxes?

A
  1. BFS
  2. DFS (+Explore)
  3. Dijkstra’s
  4. Topological Sort
  5. Kruskal
  6. Prim
  7. Strongly Connected Components
  8. 2SAT
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What are the max flow black boxes?

A
  1. Build residual network
  2. Ford-Fulkerson
  3. Edmonds-Karp
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What are the steps to solve any graph problem?

A
  1. Determine the black box
  2. Munge the input and output, almost never modify the black box
  3. State the steps of the algorithm (no pseudocode)
  4. Prove the correctness
  5. Analyze the runtime
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is BFS?

A

Gives single source shortest path from s to all vertices.

Input:

  • G = (V, E), directed or undirected
  • s start vertex, s in V

Output:

  • dist[u] shortest distance from s to u if there’s a path, inf otherwise
  • prev[v] previous node along path to v

Runtime: O(n+m)

Dist is the number of edges from s to u, not the edge weights.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is DFS?

A

Explores all vertices. Calls Explore on all unexplored vertices.

Input:
- G = (V, E), directed or undirected

Output:

  • prev[z] previous node along visitation path to z
  • pre[z] pre number of vertex z along visitation path
  • post[z] post number of vertex z along visitation path
  • ccnum[z] connected component number of z

Runtime: O(n+m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

How do directed, undirected and connected, strongly connected relate?

A
  • An undirected graph cannot have strongly connected components (or it’s meaningless), only connected components
  • A directed graph can have both connected and strongly connected components, but usually strongly connected components are more meaningful
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is Explore?

A

Explores all nodes reachable from a given start vertex.

Input:

  • G = (V, E), directed or undirected
  • s start vertex, s in V

Output:

  • visited[u] is set to true for all nodes reachable from s
  • Any other data structure that DFS provides (pre, post)

Runtime: O(m) if part of DFS, O(n+m) if run by itself

If you are allowed to modify DFS, it’s likely in here.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is topological sort?

A

Provides a possible ordering of vertices in a DAG such that, for each edge, the source vertex always comes before the end vertex.

Input:
- G = (V, E), DAG (doesn’t need to be a DAG when used in SCC)

Output:
- topo[i]: the vertex number of the i’th vertex in topological order from left to right, source to sink (in descending post order)

Runtime: O(n+m)

Uses DFS on the DAG and sorts by post order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the SCC algorithm?

A

Computes the strongly connected components in a directed graph and creates a metagraph.

Input:
- G = (V, E), directed, but not necessarily a DAG

Output:

  • G^SCC = (V^SCC, E^SCC) metagraph (DAG), with each SCC forming a vertex
  • ccnum[.] comes from DFS underneath (use it to figure out which SCC a vertex in the original graph is in)
  • V^SCC will look like 1, 2, 3, 4 which are CC nums
  • E^SCC will look like (1, 2), (2, 3), etc.

Runtime: O(n+m)

Runs with two DFSs

  1. Reverse the edges and run DFS to find a source SCC which is the highest post num. This is a sink SCC in the original graph.
  2. Sort V by highest to lowest post-order number in the original graph
  3. Run DFS again using sorted V, now highest post-order num will be source, lowest will be sink
  4. Gather up vertices, create new metanodes, connect them using original graph
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the 2SAT algorithm?

A

TODO

Runtime: O(n+m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is Kruskal’s algorithm?

A

TODO

An algorithm for getting an MST. Greedily searches for the next lowest weight edge which connects two unconnected vertices.

Runtime: O(m log n) or O(m log m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is Prim’s algorithm?

A

TODO

An algorithm for getting an MST. Greedily searches for the next lowest weight edge that connects an explored vertex to an unexplored vertex.

Runtime: O(m log n) or O(m log m)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is Ford-Fulkerson?

A

An algorithm for solving max flow problems. A container for an explore algorithm which can be either DFS (default) or BFS (Edmonds-Karp).

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

What is Edmonds-Karp?

A

An algorithm for solving max flow problems. A specialization of Ford-Fulkerson that uses BFS.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What is 2SAT?

A

TODO

An algorithm for solving a series of clauses of two boolean variables using graph theory. Uses SCC under the hood. Is in P, while kSAT (k=3+) is in NP.

Procedure:

  1. Iteratively simplify the inputs such that there are no clauses with single variables
  2. Construct a graph mapping dependencies
  3. Run SCC algorithm
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What are the seven ways of solving graph problems (and one way recommended not to)?

A
  1. Change an edge weight to make it get picked at a certain time (first, last, never)
  2. Reverse the graph and run algorithm to determine pathing to a vertex instead of from it
  3. (Directed) Get SCCs to get more info about graph
  4. (Directed) Get SCCs to determine pathing, connectivity, cycles, etc.
  5. (Directed, acyclic) Get a DAG, topo sort it, go down the ordering and look for info
  6. Encode as 2SAT and solve
  7. Run an algorithm from multiple sources/reversed (but not all)

Do NOT Explore from every vertex—that’s brute force

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Unless otherwise specified, what can you assume about MST problems?

A

The graph is undirected, connected

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What are the MST properties?

A
  1. Cut property: A cut is a set of edges that separate a graph into two components. The cut property states that, for any cut, if any edge in the cut has a weight smaller than all other edges in the cut, then it must be in the MST.
  2. Cycle property: The cycle property states that, for any cycle in a graph, the highest weighted edge must not be in the MST because it would never make sense to include it.
  3. n-1 property: An MST always has n-1 edges.
  4. Minimum-cost edge property: If the minimum cost edge is unique, then this edge must be in the MST.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

What assumptions does Ford-Fulkerson make?

A

Assumes integer capacities.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What assumptions does Edmonds-Karp make?

A

None

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the runtime of Ford-Fulkerson?

A

O(mC) (pseudo-polynomial)

23
Q

What is the runtime of Edmonds-Karp?

A

O(nm^2)

24
Q

What is the runtime of BFS, DFS, Explore?

A

O(n+m) (linear)

25
Q

What is the runtime of Dijkstra’s algorithm?

A

O(log n) * O(n+m) = O((n+m) log n)

26
Q

What assumptions does Dijkstra’s algorithm make?

A

Edges must have non-negative weights.

27
Q

What are the ways of solving flow problems?

A
  1. Turn a graph into a flow network
  2. Update capacities to fit the problem
  3. Add nodes or edges to divert flow
  4. Add more capacity from s (infinite)
  5. Add more constraints
  6. Find a max flow, then create a residual network and work with it
28
Q

What is the runtime of creating a residual network?

A

O(n+m)

29
Q

How do you know if there’s a feasible max flow?

A

G has a feasible flow if G’ (the graph with s’, t’-encoded demands) has a saturating flow.

30
Q

How do you solve max feasible flow?

A
  1. Encode a graph G’ with s’ -> v having the demand into v, v -> t’ having the demand out of v, including the original s and t. Run max flow on that. If it has a saturating flow, then G has a feasible flow.
  2. Encode a graph G’ with c’(e) = c(e) - d(e) and run max flow.
31
Q

What is Bellman-Ford?

A

Single-source shortest path DP algorithm. Can handle negative weights and detect cycles.

32
Q

What is Floyd-Warshall?

A

All-pairs shortest path DP algorithm. Can handle negative weights and detect cycles.

33
Q

What is the runtime of Bellman-Ford?

A

O(nm)

34
Q

What is the runtime of Floyd-Warshall?

A

O(n^3)

35
Q

What is the runtime of the SCC algorithm?

A

O(n+m)

36
Q

What is the runtime of the 2SAT algorithm?

A

O(n+m)

37
Q

How would you compare Prim and Kruskal in terms of usefulness?

A
  1. Prim provides a path as part of the MST output
  2. Prim is easier to do by hand
  3. Kruskal provides edge information

Generally use Kruskal unless you need the paths.

38
Q

What are the max flow analogous problems?

A
  1. Max flow with demands (feasible flow)
  2. Image segmentation
  3. Bipartite matching
  4. Min-cut
39
Q

What are the steps of the min-cut problem?

A
  1. Run max flow
  2. Create a residual network
  3. Run Explore, L is all reachable vertices, R = V - L
  4. Calculate capacity
40
Q

What are the inputs in image segmentation?

A
  • G = (V, E) undirected graph
  • F_i: probability of foreground for this pixel
  • B_i: probability of background for this pixel
  • P_ij: separation penalty between ij
41
Q

What is the runtime of image segmentation?

A

O(mC) (FF) or O(nm^2) (EK) since underlying it is max flow

42
Q

What is the runtime of SCC?

A

O(n+m)

43
Q

What is the runtime of Prim?

A

O(m log n) or O(m log m)

44
Q

What is the runtime of Kruskal?

A

O(m log n) or O(m log m)

45
Q

What does image segmentation produce?

A

A partitionining of the pixels into foreground and background such that the overall weight is minimized.

46
Q

What is the weight in image segmentation?

A

w = {sum(b_i) for i in f} + {sum(f_i) for i in b} + P_ij, we’re trying to minimize it with a min-st cut.

47
Q

What is Dijkstra’s algorithm?

A

Computes shortest weighted path from a start vertex to all other vertices.

Input:

  • G = (V, E), directed or undirected, positive edge weights
  • s start vertex

Output:

  • dist[v]: distance from s to v, inf if no path
  • prev[z]: parent index of z

Runtime: O((n+m) log n)

48
Q

What is required for an MST algorithm?

A

A weighted, connected graph

49
Q

What is required for max flow?

A

A weighted, directed graph

50
Q

What is required for topological sort?

A

A directed, acyclic graph

51
Q

How are features encoded in image segmentations?

A
  • Foreground pixel probabilities are from s’ to v
  • Background pixel probabilities are from v to t’
  • Separation penalties are undirected edges encoded as bidirectional edges each with weight P_ij
52
Q

How are features encoded in feasible max flow?

A

In step 1, computing feasibility:

  • Incoming demands are from s’ to v (s has none)
  • Outgoing demands are from v to t’ (t has none)

In step 2, computing max flow:
- Demand is subtracted from capacity and then max flow used directly

53
Q

What are the steps in the SCC algorithm?

A

Runs with two DFSs

  1. Reverse the edges and run DFS to find a source SCC which is the highest post num. This is a sink SCC in the original graph.
  2. Run Explore on the original graph from the known sink SCC vertex and rip out all vertices in visited.
  3. Add that SCC and edges to G^SCC as a meta-node.
  4. Repeat until all nodes have been ripped out.

Software Engineering (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions