# How Graphs and Graph algorithms are treated Flashcards

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

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

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

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

Explain how DFS is treated. What is the subroutine?

outputs connected components, topological sort on a DAG.

You also have access to the prev, pre and post arrays.

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

Explain how BFS is treated

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

Explain how Dijkstra’s algorithm is treated

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

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

Bellman-Ford

Floyd-Warshall

Explain how SCC algorithm is treated

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

Which algorithms are used to find the MST?

Kruskal’s and Prim’s

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

Ford-Fulkerson

Edmond’s-Karp

Explain how 2-SAT algorithm is treated

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

What are the assumptions about graphs in this class?

- 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)

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

O(n+m)

Runtime for Checking, reading, or removing one vertex

O(1)

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

O(n)

Runtime for Checking, reading, or removing one edge

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