Graphs Flashcards

Question

Depth First Search

Answer 1

* Assumes an adjacency list * Cannot be used to find the minimum path * Applications 1. Topological sort 2. Finding connected components in an undirected graph 3. Finding SCC in a directed graph _Steps_ 1. Initialize all edges as undiscovered, and remove predecessors 2. Loop through all of nodes, starting depth first search on each node 3. For each node 4. Mark that node as discovered 5. Mark "time" of discovery 6. Process node 7. Loop throughh vertex's adjacent nodes 8. If not discovered 9. Update predecessor 10. Perform dfs on that node (recursively) 11. After loop 12. Increment time again 13. Update finish time **_Complexity_** Time Average ⇔ Worst: O( |V| + |E| ) Space O(V) \*Linear in the size of the graph

Answer 2

_In-degree_ * The number of incoming edges a vertex has in a directed graph _Out-degree_ * The number of outgoing edges a vertex has in a directed graph

Answer 3

|V| = number of vertices |E| = number of edges * The number of vertices in set V and number of edges in set E

Answer 4

* A modification of Dijkstra's that considers an additional heuristic * Only used to find paths to one location * Heuristic should be 'admissible' (should never overestimate the true distance) in order to return a guaranteed shortest distance * Instead of "distance\_to", we use different terminology * f(n) = g(n) + h(n) * f(n) =\> total estimated cost * g(n) =\> equivalent to distance\_to n * h(n) =\> heuristic from n to target _Steps_ 1. Create visited set 2. Initialize g(n) of all nodes as infinity 3. Initialize f(n) of all nodes to infinity 4. Initialize parents of all nodes to None 5. Update g(source) to be 0 6. Updated f(source) of source to be its heuristic 7. Add source to pq 8. While queue is not empty 9. Remove vertex v from pq with lowest f(n) 10. Mark as visited 11. If vertex is target, return 12. For neighbors u of v 13. If u not in visited 14. Relax edge v to u 15. If g(v) + edge(v, u) \< g(u) 16. Change parent of u to v 17. Add/update priority of u with f(u) (new cost plus heuristic) 18. Keep going until goal found (or queue empty) **_Complexity_** Time Average ⇔ Worst: O( |E| + |V|\*log |V| ) Average ⇔ Worst: O( (|E| + |V|) \* log |V| ) Space O(V) \*First time complexity assumes fibonacci heap (constant decrease-key) \*Second time complexity assumes binary heap (log delete-min and descrease-key) \*Real complexity depends on the heuristic used, so just used Dijkastra's as an upper bound

Answer 5

_Unweighted Graph_ * Cells should store boolean values to indicate the presence of an edge from i to j _Weighted Graph_ * Cells should store number values (integer or floats) to represent the weight * You can store None or a dummy weight to represent a missing edge * Common dummy weights are -inf/inf or 0 * Optionally, you can store edge objects, which can contain information beyond a simple weight

Answer 6

* Also called a digraph * edges are ordered pairs, (x, y) * edges (x, y) != edge (y, x) * Bidirectional relationships require two edges * _Ex:_ the internet, instragram following

Answer 7

* A graph where nodes can be connected with more than one edge * Put another way, multiple edges can run parallel between the same vertices

Answer 8

* The number of edges a vertex has * lkl * lklk * klkl * klkl * lkl * klkl * klkl * klkl * klklj

Answer 9

* Neighbors of vertex v are all of its adjacent vertices

Answer 10

_In a directed graph with loops_ * v² _In a directed graph without loops_ * v(v - 1) _In an undirected graph with loops_ * v(v + 1) / 2 _In an undirected graph without loops_ * v(v - 1) / 2

Answer 11

* In an undirected graph, a cycle occurs when 1. There is a neighbor of v that has been visited already, but isn't a parent of v 2. V is its own neighbor (loop) * Can use BFS or DFS, but DFS makes it easier to describe the cycle _Steps_ 1. Use DFS 2. When exploring neighbors u of v 3. If u has been visited, but isn't a parent of v 4. Or u is v (loop) 5. Then a cycle exists, return True

Answer 12

* Single source shortest paths algorithm * Used on weighted, directed graphs * Indicates if negative weight cycle is found (returns boolean, raises error) * Negative weights in a undirected graph will appear as cycles * Effective but slow * Does not require vertices to be marked as visited * \* The Bellman Drinks VEEVV+VEEVA: * Visit Every Edge or Vertex V times, and Visit Every Edge or Vertex Again **Steps** 1. Initalize distance\_to all vertices to inf 2. Initalize parent of all vertices to null 3. Initialize distance\_to source to 0 4. Create a loop of length |V|-1 5. In each iteration, loop through and relax edges 6. Or loop through vertices and relax their adjacent edges 7. You can stop outer loop if relaxation doesn't change tree 8. To detect negative weight cycles, loop through graph again 9. If edge weigts change, cycle must exist * Return False or raise error **_Complexity_** Time Best: O(|V| + |E|) ♦ Average ⇔ Worst: O(|V| \* |E|) Space O(1) \*Best case: |V| to initialize distances/parents; |E| if you stop early and only relax edges twice (stop after second iteration because no changes were made)

Answer 13

* A vertex whose removal would create more connected components in the graph than there were before

Answer 14

* In any graph, the sum of the degree (or the neighbors) of all the vertices is: * 2\*|E| in an undirected graph * |E| in a directed graph

Answer 15

* Vertices are adjacent if they share an edge

Answer 16

* All-pairs shortest paths * Works with negative and positive edges, but no negative edge weight cycles * Returns a table of weights, cannot get back paths * \* be**K**ause **I**t's **J**une, m**IJ** l**IK**s the **K**a**J**e **Steps** 1. Initialize 2-d dist array, size |V|\*|V|, to inf in every cell 2. Loop through edges, populating dist matrix with distances from u-v 3. Loop through vertices, make distance to itself 0 (along the diagonal) 4. Create triple nested loop, k, i, j to V 5. If dist[i][j] \> dist[i][k] + dist[k][j] 6. Then dist[i][j] = dist[i][k] + dist[k][j] **_Complexity_** Time Average ⇔ Worst: O( |V|³) Space O( |V|²) \*Running time dominated by triple nested loop

Answer 17

* Term applies to undirected graphs * There a exists a path from any vertex to any other vertex

Answer 18

* A graph in which edges have a "weight" associated with them * Weights can be used to represent many things, included capacity of a wire, the traffic along a route, etc. * Meaning of weights is based on what you're modeling

Answer 19

* In directed graph, a cycle occurs when 1. A neighbor has been visited and is on the path 2. V is its own neighbor (loop) _Steps_ 1. Use DFS while recording path 2. When exploring neighbors u of vertex v 3. If u is in the path 4. Or u is v (loop) 5. Or u has a discovery time but doesn't have a finish time 6. Then cycle exists, return True

Answer 20

* Also known as a DAG * It's a directed graph with no cycles

Answer 21

* Expects a DAG * Provides a linear ordering of vertices * Produces a partially ordered set, elements are ordered w.r.t. some, but not all other elements * Ordering is not necessarily unique _Steps:_ 1. Loop through all vertices, running DFS 2. For each frame of DFS 3. Record start time 4. After visiting all of that vertex's neighbors (after completing for loop) 5. Push to stack 6. Record finishing time 7. At very end, pop and print 8. Or sort by finishing time in decreasing order (latest comes first) **_Complexity_** TimeV Best⇔ Average ⇔ Worst: O(|V| + |E|) Space O(|V|) \*Linear in the size of the graph

Answer 22

* Represent some relationship between vertices * _Ex:_ Facebook edges represent friendship

Answer 23

* Applies to shortest weighted path * Special procedure that can be performed in linear time (normal graphs might require Dijkstra's or Bellman Ford, etc.) * Negative edge weights allowed (no cycles tho) * Similar to edge relaxation in pathfinding algorithms **Steps** 1. Initialize dist\_to source to 0 2. Initialize dist\_to all other vertices to inf 3. Perform topological sort 4. Loop through vertices in topological order 5. Use edge relaxation at each vertex, along incoming edges * If dist[v] + edge(v, u) \< dist[u], etc. * or distance to from s to v is minimum of distances from s to u₁- u_n (incoming edges to v) and minimum of edges to v

Answer 24

* A graph without weights * Unweighted graphs can be thought of a special case of weighted graph in which all edges have same weight * Normally assume weight is "1 unit"

Answer 25

Term has 2 meanings 1. If two edges share a vertex, they are incident 2. If an edge is connected to a vertex, then they are incident

Answer 26

* Used to find Minimum Spanning Tree (or forest) * Can get individual trees from forest by finding connected components before or after algo * Requires a Union Find data structure **Steps** 1. Create empty MST set 2. Use make-set on each vertex 3. Create list of edges 4. Sort list of edges by weight 5. Iterate through edges (in increasing order) 6. For each edge 7. If find(u) != find(v) (if they aren't in the same set) 8. Add edge to MST set 9. Union u and v 10. Keep going until for loop ends **_Complexity_** Time Average ⇔ Worst: O(E log V) Space O(|V| +|E|) \*Sorting dominated running time \*O(E log E) ⇒ O(E log V) because V² = O(E) (because you have at most V² edges

Answer 27

* Finding the shortest path from every other vertex to one vertex * Not done very often * Basically the same as single source * Reverse edge directions and treat destination as source

Answer 28

* Usually done on a adjacency list representation * Start with a vertex, and explore its neighbors * Algorithm can be tweaked used to find the minimum path * Applications * Guaranteed shortest path (path with fewest edges between vertices) * Spanning tree * In unweigted graphs, all spanning trees are "minimum spanning trees" _Steps_ 1. Create an empty set of "visited" nodes 2. Create an empty queue 3. Add starting vertex to queue 4. Add vertex to visited set 5. While queue isn't empty 6. Dequeue and process vertex v 7. Loop through v's adjacent vertices 8. If adjacent vertex is not in "visited" set 9. Add to visited set 10. And enqueue **_Complexity_** Time Average ⇔ Worst: O( |V| + |E| ) Space O(V) \*Linear in the size of the graph

Answer 29

* A set of vertices and edges * Usually implemented with an adjacency matrix or an adjacency list * G = (V, E)

Answer 30

* A graph where one edge can connect more than two nodes at once

Answer 31

* A cycle with no smaller cycles

Answer 32

* A graph where edges don't have orientation * edges are unordered pairs, {x, y} * edge (x, y) is the same as edge (y, x) * Ex: facebook friendships