Brainscape's Knowledge GenomeTM

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


See full index

Algorithms & Data Structures > Graphs > Flashcards

Graphs Flashcards

1
Q

Weakly Connected

A
  • Term applies to directed graphs
  • A graph that isn’t strongly connected, but would be would be connected if it were undirected
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Greedy Algorithm

A
  • An algorithm that involves making the “optimal decision” at each step
  • The “optimal decision” depends on the context of problem
    • Shortest distance
    • Earliest time, etc.
  • Ex: Dijkstra’s algorithm
    • Relaxing edges is greedy
    • For each edge, you compare current distance, to distance through vertex v, and choose minimum
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Simple Path

A
  • A path with no cycles
  • Also, a path with no repeated vertices
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Strongly Connected Graph

A
  • Term applies to directed graphs
  • There exists a path from any vertex to any other vertex
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Adjacency Matrix

A
  • An implementation of a graph using a 2D matrix edges
  • Width and height of matrix is |V|
  • Cells represent edges, and the indices of the cells (the rows/cols) represent vertices
  • Running time is good, but space complexity is poor
  • Especially useful for dense graphs or when |V|2 (size of matrix) is really small
  • Cannot be used to represent a graph with parallel edges

Complexity

Time

Checking for an edge: O( 1 )
Iterating over the graph: O( v2 )
Getting all the neighbors: O( v )

Space

O(V2)

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

Shortest Path Problems

A
  • Problems involving finding the shortest paths between vertices in a graph
  • Refers to weighted graphs (directed or undirected)
  • Variations
    • Single Source Shortest Path
    • All Pairs Shortest Path
    • Single Destination Shortest Paths
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Tree

A
  • Connected acyclic graph
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Spanning Tree

A
  • Applies to undirected graphs
  • A tree within graph that contains all vertices
  • A graph can have multiple spanning trees
  • The set of vertices in both graph and tree are the same
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Paranthesis Theorum

A
  • When performing DFS on a graph, the discovery and finishing times never overlap
  • Consider ud, uf, and vd, vf
    • Either disjoint [ud, uf], [vf, vf]
      • Neither is a descendent of the other
    • Or u nested in v [ud, vd, vf, uf]
      • V is a descendent of U
    • Or v nested in u [vd, ud, uf, vf]
      • U is a descendent of V
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Simple Graph

A
  • a graph that does not contain loops or parallel edges
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Strongly Connected Component

SCC

A
  • strongly connected subgraph in a directed graph
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Minimum Spanning Tree

A
  • A spanning tree of a graph that has a total weight no higher than any other spanning tree in the graph
  • A graph can have multiple minimum spanning trees
  • Applies to weighted, undirected graphs
    • A MST of an unweighted graph is just any spanning tree
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Adjacency List

A
  • An implementation of a graph using an array of linked lists of vertices
  • Each element in array represents a vertex, and stores a list all edges adjacent to that vertex
  • In weighted graph, nodes of list at each index also store weights (from that index to vertex)
  • The list stored at each index can also (optionally) be an array, a binary tree or some other data structure

Complexity

Time

Checking for an edge: O( V ) / O ( deg(v) ) / O( lg(V) )
Iterating over all edges: O( V + E )
Getting all the neighbors: O( V )

Space

O( V + E )

* O( deg(v) ) basically means “it depends”
* O( lg(V) ) is achievable is elements are sorted, perhaps in a BST, and you use binary search

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

Transpose

A
  • Reversing the direction of every edge in a directed graph
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Kosaraju’s Algorithm

A
  • Used to find strongly connected components in a directed graph
  • Runs DFS twice

Steps

  1. Run DFS over all vertices
  2. Use stack to organize nodes by decreasing finish time (similar to topological sort)
  3. Transpose graph
  4. Pop vertices, run DFS on each
  5. Vertices reachable from this second run comprise individual scc’s (strongly connected components)

Complexity

Time

Average ⇔ Worst: O(V + E)

Space

O(V + E)

*Linear in the size of the graph

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

Reachable

A
  • If a path exists from one vertex to another, it is reachable
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Relaxing an edge

A
  • Term used in shortest path algorithms
  • The process of continually improving the distance estimation to some vertex through different edges
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Adjacency Matrix

Directed vs Undirected Graph

A
  • In an undirected graph, matrix will be symmetrical across diagonal
  • Therefore, you should only keep one half (usually the top half)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Single Source Shortest Path

A
  • Finding the shortest weighted path between one vertex and evey other vertex
  • Or finding the shortest weighted path between one vertex to another vertex

Algorithms

  • Dijkstra’s
  • A*
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

All Pairs Shortest Paths

A
  • Finding the shortest weighted path from every vertex to every other vertex

Algorithms

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

Dijkstra’s Algorithm

A
  • Single source shortest path
  • Used on weighted graphs (directed or undirected)
  • Graph cannot contain negative edges

Steps

  1. Assign every node a tentative distance-to value of infinity
  2. Assign every node a parent of None
  3. Give source distance of 0
  4. Add source to the priority queue
  5. While queue is not empty
  6. Remove min-distance vertex v from priority queue
  7. Add source to seen set
  8. For each neighbor u of vertex v
  9. If u not in seen set (if u is still in pq)
  10. Relax edge from v to u
  11. If the distance-to v + edge(v, u) is less than current distance-to u
  12. Update distance-to u
  13. Change u’s parent to v
  14. Add u with priority to pq (or update priority of u in pq with new distance)
  15. Stop upon finding destination, or when queue is 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)

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

Prim’s Algorithm

A
  • Used to find Minimum Spanning Tree
  • Very similar to Dijkstra’s
  • * Dijkstra PRIME: for every vertex, Priority Is My Edge
  • key of priority queue is a vertex’s edge, rather than distance from source
  • Basically add smallest edges one by one until tree is formed

Steps

  1. Initialize key (associated edge) of every vertex to infinity
  2. Initialize parent of every vertex to None
  3. Initialize key of source as 0
  4. Add source to pq
  5. While size of tree is < |V|
  6. Remove min element
  7. Add vertex and edge to MST
  8. For each neighbor u of v
  9. If u not in MST
  10. If edge(v, u) < key(u)
  11. Make v parent of u
  12. Update key(u) in PQ
  13. Keep going until PQ is empty, or until size(MST) = |V|

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)

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

Loop

A
  • An edge from a vertex to itself
24
Q

Adjacency List

Directed vs Undirected Graphs

A

Undirected Graphs

  • Must store edges twice

Directed graph

  • When representing a digraph with an adjacency list, the lists stored at each index can be implemented in different ways

3 Options

  1. Store list of outgoing edges
  2. Store list of incoming edges
  3. Store both in two separate lists
25
Q

Depth First Search

A
  • 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

26
Q

In-degree / Out-degree

A

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
27
Q

Number of Edges/Vertices (Notation)

A

|V| = number of vertices

|E| = number of edges

  • The number of vertices in set V and number of edges in set E
28
Q

A* Pathfinding

A
  • 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

29
Q

Adjacency Matrix

Weighted vs Unweighted Graph

A

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
30
Q

Directed Graph

A
  • 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
31
Q

Multigraph

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

Degree

A
  • The number of edges a vertex has
  • lkl
  • lklk
  • klkl
  • klkl
  • lkl
  • klkl
  • klkl
  • klkl
  • klklj
33
Q

Neighbors

A
  • Neighbors of vertex v are all of its adjacent vertices
34
Q

Maximum Number of Edges

A

In a directed graph with loops

  • v2

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
35
Q

Cycle Detection in an Undirected Graph

A
  • 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
36
Q

Bellman Ford

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

37
Q

Cut Vertex

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

Handshaking Lemma

A
  • 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
39
Q

Adjacent

A
  • Vertices are adjacent if they share an edge
40
Q

Floyd–Warshall

A
  • 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
  • * beKause It’s June, mIJ lIKs the KaJe

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

Space

O( |V|2 )

*Running time dominated by triple nested loop

41
Q

Connected Graph

A
  • Term applies to undirected graphs
  • There a exists a path from any vertex to any other vertex
42
Q

Weighted Graph

A
  • 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
43
Q

Cycle Detection in a Directed Graph

A
  • 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
44
Q

Directed Acyclic Graphs

A
  • Also known as a DAG
  • It’s a directed graph with no cycles
45
Q

Topological Sort

A
  • 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

46
Q

Edges

A
  • Represent some relationship between vertices
  • Ex: Facebook edges represent friendship
47
Q

Shortest Paths in a DAG

A
  • 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 u1 - un (incoming edges to v) and minimum of edges to v
48
Q

Unweighted Graph

A
  • 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”
49
Q

Incident

A

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
50
Q

Kruskal’s Algorithm

A
  • 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 V2 = O(E) (because you have at most V2 edges

51
Q

Single Destination Shortest Paths

A
  • 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
52
Q

Breadth First Search

A
  • 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

53
Q

Graph:

Definition

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

Hypergraph

A
  • A graph where one edge can connect more than two nodes at once
55
Q

Simple Cycle

A
  • A cycle with no smaller cycles
56
Q

Undirected Graph

A
  • 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

Algorithms & Data Structures (11 decks)

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