Graphs Instant Match

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/34

encourage image

There's no tags or description

Looks like no tags are added yet.

35 Terms

1
New cards

Minimum hops (unweighted edges)

Breadth-First Search (BFS)

2
New cards

Cheapest path with non-negative edge weights

Dijkstra's Algorithm

3
New cards

Cheapest path with arbitrary edge weights (including negative weights)

Bellman-Ford Algorithm

4
New cards

All-pairs shortest paths

Floyd-Warshall Algorithm

5
New cards

Maximum total throughput from s→ts \rightarrow t

Ford-Fulkerson or Edmonds-Karp Algorithm

6
New cards

Connect all nodes with the minimum total cost

Kruskal's or Prim's Algorithm (Minimum Spanning Tree)

7
New cards

Maximize the bottleneck capacity on a single path

Maximum Spanning Tree + Breadth-First Search (BFS)

8
New cards

Order items or tasks by dependencies

Topological Sort

9
New cards

Find mutual reachability groups in a directed graph

Strongly Connected Components (SCC)

10
New cards

Detect whether a cycle exists in a graph

Depth-First Search (DFS) checking for back edges

11
New cards

Identify connected components or groups in an undirected graph

Depth-First Search (DFS) or Breadth-First Search (BFS)

12
New cards

Detect the presence of any negative cycle

Bellman-Ford or Floyd-Warshall Algorithm

13
New cards

Minimum number of hops / edges between two nodes — no weights

Breadth-First Search

14
New cards

Shortest weighted path — all edge weights are positive or zero

Dijkstra's Algorithm

15
New cards

Shortest weighted path — some edge weights may be negative

Bellman-Ford

16
New cards

Shortest path between EVERY pair of nodes (all-pairs)

Floyd-Warshall

17
New cards

Can node A reach node B? Is any path possible?

Breadth-First Search

18
New cards

Find all connected components — how many groups of connected nodes?

Depth-First Search (on undirected graph)


SCC (Directed Graph)

19
New cards

Find groups where EVERY node can reach every other node — directed graph

SCC

20
New cards

Does this directed graph have a cycle? Is it a valid DAG?

Depth-First Search

21
New cards

Order tasks so that all dependencies come first (scheduling / prerequisites)

Topological Sort

22
New cards

Find the longest/shortest path through a DAG

Topological Sort combined with Dynamic Programming

23
New cards

Maximize total flow from source s to sink t — integer edge capacities

Ford-Fulkerson

24
New cards

Maximize total flow from source s to sink t — any capacities or large values

Edmonds-Karp

25
New cards

Maximum bipartite matching — pair up two groups optimally

Edmonds-Karp (after building a flow network from the bipartite graph)

26
New cards

Find all maximal groups of mutual reachability in a directed graph

Strongly Connected Components

27
New cards

Simplify a directed cyclic graph into a DAG for further algorithm application

Strongly Connected Components

28
New cards

Find the source SCC — the group that can reach all other SCCs

Strongly Connected Components

29
New cards

Find the sink SCC — the group that no edge leaves

Strongly Connected Components

30
New cards

Detect if a negative cycle exists reachable from a specific source s

Bellman-Ford

31
New cards

Detect if ANY negative cycle exists anywhere in the entire graph

Floyd-Warshall

32
New cards

Widest single path from s to t — maximize the minimum edge weight along the route

Kruskal's Algorithm (with negated weights) followed by Breadth-First Search

33
New cards

Shortest path in a DAG — can handle any edge weights including negative

Topological Sort followed by edge relaxation in topological order

34
New cards

Shortest distance from ANY one of multiple source nodes to all other nodes

Dijkstra's Algorithm or Breadth-First Search with a virtual super-source node

35
New cards

Apply a DAG algorithm to a graph that has cycles

Strongly Connected Components followed by the DAG algorithm on the metagraph