# How Graphs and Graph algorithms are treated Flashcards

1
Q

For the class, what are the black box algorithms available for me? Are we allowed to change or modify?

A

A graph theory problem is a form of reduction. You are given some problem to solve, and the challenge is to solve that problem by using one of the graph algorithms we study this semester. In other words, you reduce your problem to a graph problem such that a known algorithm can solve it for you.

Algorithms:
- DFS
- BFS
- Dijkstra’s
- Belman-Ford
- Floyd-Warshall
- SCC
- Kruskal’s
- Prim’s
- Ford-Fulkerson
- Edmond’s-Karp
- 2-SAT

Not allowed to change ore modify the blackbox graph algorithm

2
Q

When answering for the designing an algorithm for graphs, what do you need to cover per section? Algorithm, justification, runtime?

A

Algorithm:
- NO PSEUDOCODE - use words

What changes you may need for the input

What black box you will feed your input to

What changes you may need for the output

Repeat with more black boxes as needed

Justification:
- Explain how your problem is solved by the black boxes used

• Explain how changing the inputs and/or outputs gets what you want

Analyze the runtime:
- Must be presented in Big O notation

• Can explain/analyze in words
• Can use known black box runtime without explanation. Must include run time analysis for any pre/post processing, as well as any modifications to the black box (if permitted by the problem)
• Again, if we give you a run time, you must meet that for full credit. If we do not specify a run time, faster (and correct) in Big O notation are worth more credit
3
Q

Explain how DFS is treated. What is the subroutine?

A

outputs connected components, topological sort on a DAG.

example)
vertex: [A, B, C, D, E, F, G, H]

pre: [2, 1, 12, 3, 4, 13, 5, 8]

post: [11, 16, 15, 10, 7, 14, 6, 9]

prev: [B, 0, B, A, D, C, E, D]

visited: [True, True, True, True, True, True, True, True]

For undirected graphs:
ccnum: [1, 1, 1, 2, 2, 3, 4, 4]

determines the connected components of a graph

(using alphabetical ordering again for simplicity). the connected component numbers are the pieces the graph is split into, and the array ccnum for DFS returns what numbered piece each vertex is in

Only use ccnum for undirected graphs

Explore is the subroutine

4
Q

Explain how BFS is treated

A

performs a breadth-first search of the graph from a starting vertex, provides dist array.

5
Q

Explain how Dijkstra’s algorithm is treated

A

find the shortest distance from a source vertex to all other vertices and a path can be recovered backtracking over the prev labels

6
Q

Which 2 algorithms can be used to compute the shortest path when weights are allowed to be negative?

A

Bellman-Ford

Floyd-Warshall

7
Q

Explain how SCC algorithm is treated

A

outputs the strongly connected components, and the metagraph of connected components.

8
Q

Which algorithms are used to find the MST?

A

Kruskal’s and Prim’s

9
Q

Which algorithms are used to find the max-flow of networks?

A

Ford-Fulkerson

Edmond’s-Karp

10
Q

Explain how 2-SAT algorithm is treated

A

takes a CNF with all clauses of size ≤ 2 and returns a satisfying assignment if it exists

11
Q

What are the assumptions about graphs in this class?

A
• simple graphs unless the problem states otherwise
(no multi-edges or self-loops present)
• connected or disconnected
• undirected or directed
• When working with MSTs we assume the graph is both connected and undirected
• When working with flow networks we assume the graph is both connected and directed.
• we use adjacency lists for graphs in the class
-> An array of vertices that are pointers to linked lists of adjacent vertices
-> So each element in the list represents an edge to another vertex.

Assume ALL graphs in this class (input or your own) are labeled in such a way that they can be found by an index into the array.

Prefer to work with
We assume n = number of vertices and m = number of edges. We prefer O(n), O(m), O(n+m)

12
Q

Runtime for Traversing, reversing, copying, subgraphing, or otherwise working with a full graph:

A

O(n+m)

13
Q

Runtime for Checking, reading, or removing one vertex

A

O(1)

14
Q

Runtime for Iterating, checking, reading, removing, or otherwise working on all vertices (or subset):

A

O(n)

15
Q

Runtime for Checking, reading, or removing one edge

A

O(n) or O(m)

One is usually more correct than the other depending on what you are doing, but for the sake of simplicity, we will accept either when a single edge is involved

16
Q

Runtime Iterating, checking, reading, removing, or otherwise working on all edges (or subset)

A

O(n+m)

If you are working on all edges, you will need to check all vertices for its edges

17
Q

When you KNOW the graph is connected, either because we tell you or it is an MST or Max Flow problem where being connected is a given

A

We simplify O(n+m) to O(m)

18
Q

What is the ccnum in a DFS output?

A

“ccnum” is an array returned by DFS which tells us the connected component number of every vertex. “cc” is a counter used within DFS to determine which connected component number the algorithm is on and should currently set the vertices to. The “cc” counter only moves up one if there are more vertices left to visit after fully exploring from a particular vertex.

We don’t utilize connected component numbers in directed graphs

19
Q

What is the explore function in DFS?

A

TLDR: Explore will get you the list of vertices that s can reach in the visited array. This is specific to Explore without any additional details

Background: Explore and DFS often gets used interchangeably in other material. However, this class allows explore (a subroutine of DFS) to be used as a black box on its own

you should use Explore to check if something is reachable from s. Using DFS requires additional steps that many students forget and end up being penalized for. DFS has many other uses, but Explore is the best algorithm for checking if s can reach certain vertices.

Note:If you simply say, “I run DFS from s and find all vertices reachable by s,” this will likely get you a lack of details penalty, or a “should have used explore” penalty. This is because without additional work, DFS has no output that tells you what vertex was visited from s.

20
Q

A

DFS is an algorithm for traversing or searching tree or graph data structures. It starts at the root or an arbitrary node of a graph and explores as far as possible along each branch before backtracking

Input: G = (V, E)

Output: ccnum[]

a topological sort on a DAG (Directed Acyclic Graph).

it takes O(1) to access the first or last vertex of the topological sorting.

Graphs that use DFS:
- Unweighted graphs
- Undirected/Directed graphs
- DAGs

21
Q

A

Explore is used by DFS as a sub-routine.

Very simply, it outlines how to get from one vertex to another along a path in a graph or a tree.

A key point to Explore is that we only move to the next available neighbor only when we have fully explored the current vertex and its adjacencies.

When to use: It is the best algorithm for checking if start vertex v can reach certain vertices in G.

Input:
- G = (V, E)
- Start vertex v in V

Output:
- visited [] (which is set to TRUE for all vertices reachable from v.)

- ccnum array (ccnum[])
- previously visited array (visited[])
- An array of vertices before a given vertex
- Used by Explore and required for DFS.

Graphs that can use Explore
- unweighted graphs
- directed/undirected graphs
- DAGs

Runtime: O(n+m)

22
Q

BFS: describe, input, output, when to use it

A

algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph) and explores the neighbor nodes at the present depth before moving on to nodes at the next depth level.

Input:
-G = (V, E)
- Start vertex v in V

Output:
dist[]
- For all vertices u reachable from the starting vertex v, dist[u] is the shortest path distance from v to u. If no such path exists, infinity otherwise.

prev[]
-Vertex preceding u in the shortest path from v to reachable vertex u.

Unweighted graphs
Undirected/Directed graphs

Runtime: O(n+m)

23
Q

Dijkstra’s algorithm: describe, input, output, when to use it

A

Dijkstra’s algorithm is used to find the shortest distance from a source vertex to all other vertices. A path can be recovered by backtracking over all of the pre-labels.

Input:
- G = (V, E)
- Start vertex v in V

Output:
- dist[]
Shortest distance between vertex v and reachable vertex u or infinity otherwise if not reachable.

- prev[]
Vertex preceding u in the shortest path from v to reachable vertex u

Graphs that can use Dijkstra’s:
- Weighted graphs
- Undirected/Directed graphs
- NO negative weights

Runtime: O(m+n log n)
Or if Strongly connected O(m log n)

24
Q

Bellman-Ford: describe, input, output, when to use it

A

Bellman-Ford is used to derive the shortest path from s to all vertices in V. It does not find a path between all pairs of vertices in V. To do this, we would have to run BF |V| times. Negative weights are allowed

Input:
- G = (V, E)
- Start vertex s

Output:
- The shortest path from vertex s to all other vertices.

- Detect negative weight cycles. We can compare T[n, *] to T[n - 1, *].

• We can only find negative weight cycles that can be reached from starting vertex s

Can use with:
- Weighted graphs
- Undirected/Directed graphs
- CAN HAVE negative weights

Runtime: O(nm)

25
Q

Floyd-Warshall: describe, input, output, when to use it

A

FW is primarily used to find the shortest path from ALL nodes to all other nodes where negative weights are allowed.

Input:
- G = (V, E)

Output:
- The shortest path from all vertices to all other vertices

- We can detect negative weight cycles by checking the diagonals (T[n, i, i]).

Graphs that can use FW:
- Weighted graphs
- Undirected/Directed graphs
- CAN HAVE negative weights

runtime: O(n^3)

26
Q

SCC algorithm: describe, input, output, when to use it

A

The SCC algorithm is used to determine the strongly connected components as well as the meta-graph of connected components in a given directed graph

Input:
- G = (V, E)

Output:
- meta-graph (DAG) that contains the connected components

• Topological sorting of the meta-graph
• With a source SCC first and a sink SCC last

- ccnum[] - strongly connected components produced from the 1st DFS run

Graphs that can use SCC:
- directed graphs

Runtime: O(n+m)

27
Q

Kruskal’s Algorithm: describe, input, output, when to use it

A

Kruskal’s is one of the two algorithms used to find the Minimum Spanning Tree (MST) discussed in class.

Input:
- Connected, Undirected Graph G = (V, E) with edge weights w_e

Output:

• An MST defined by the edges E

Graphs that can use Kruskal’s:

• Connected
• Undirected
• Weighted

Runtime:
- O(m log n)

28
Q

2SAT algorithm: describe, input, output, when to use it

A

The 2-SAT problem is to determine whether there exists an assignment to variables of a given Boolean formula in 2-CNF (conjunctive normal form) such that the formula evaluates to true. The algorithm for solving 2-SAT uses graph theory by constructing an implication graph and then checking for the existence of a path that satisfies the conditions.

Input:
- A Boolean formula in 2-CNF is represented as a set of clauses where each clause is a disjunction of exactly two literals.

Output:
- A Boolean value indicates whether the given 2-CNF formula is satisfiable. If it is satisfiable, the algorithm may also provide a satisfying assignment of variables

Graphs that can use 2-SAT:
- Directed graphs
The implication graph is inherently directed since each implication (¬x → y) has a direction.

Runtime: O(m + n) - m is the number of clauses in the 2-CNF formula, n is the number of literal or variables.

• This runtime stems from the linear runtime of SCC finding algorithms and the construction of the implication graph
29
Q

Ford-Fulkerson: describe, input, output, when to use it

A

A greedy algorithm to find max flow on networks. The algorithm continually sends flow along paths from the source (starting node) to the sink (end node), provided there is available capacity on all edges involved. This flow continues until no further augmenting paths with available capacity are detected.

Input:
- G = (V, E)
- Flow capacity c
- Source node s
- Sink node t

Output:
- Max flow

- Can trivially create the final residual network with G
- Max flow of G

We run FF on the flow network to - get the maximum flow.

We use this to construct the residual graph.

Graphs that can use FF:
- Directed graphs with capacity of edges

Runtime:
- O(C * m)
- C is the maximum flow in the network m is the number of edge

30
Q

Edmond’s-Karp: describe, input, output, when to use it

A

The Edmonds-Karp (EK) algorithm is utilized to determine the maximum flow in a network. This is analogous to the Ford-Fulkerson method but with one distinct difference: the order of search for finding an augmenting path must involve the shortest path with available capacity (BFS for G where all edge weights equal 1).

Input:
- G = (V, E)
- Flow capacity c
- Source node s
- Sink node t

Output:
- Max flow

- Can trivially create the final residual network with G
- Max flow of G

We run EK on the flow network to get the maximum flow.

We use this to construct the residual graph.

Graphs that can use EK:
- Directed graphs with capacity of edges

Runtime:
- O(nm^2)
- n is the number of vertices
- m^2 is the number of edges

31
Q

Why use Edmond’s-Karp over FF?

A
• Edmonds-Karp uses BFS in the residual graph to find an augmenting path. This guarantees that the path found is always the shortest (in terms of the number of edges). This is crucial because, in Ford-Fulkerson, the use of DFS can lead to long unyieldly path traversals in dense graphs (graphs where the number of edges is close to the maximum possible number of edges), where DFS can get “stuck” exploring a deep path that becomes very inefficient
• The explicit use of BFS for the selection of augmenting paths prevents the possibility of an infinite loop occurring due to constantly decreasing flow augmentation. Therefore, unlike the Ford-Fulkerson algorithm, Edmonds-Karp always terminates.
• Edmonds-Karp algorithm, with its worst-case runtime of O(nm^2), offers an improvement over Ford-Fulkerson because its time complexity is dependent on the number of vertices (n) and edges (m), rather than the maximum flow in the graph (C)