Algorithms - Graph Theory & Shortest Path Algorithms Flashcards

Question 1

What is a Graph in Computer Science?

Accepted Answer

A graph is a non-linear data structure consisting of a finite set of vertices (or nodes) and a set of edges (or arcs) connecting pairs of vertices. It's formally represented as $G = (V, E)$, where $V$ is the set of vertices and $E$ is the set of edges.

Question 2

Distinguish between a Directed and an Undirected Graph.

Accepted Answer

An **Undirected Graph** has edges that are bidirectional, meaning if an edge connects vertex A to vertex B, it also connects B to A. An **Directed Graph** (or Digraph) has edges with a specific direction, meaning an edge from A to B does not imply an edge from B to A.

Question 3

What is a Weighted Graph?

Accepted Answer

A **Weighted Graph** is a graph where each edge has an associated numerical value, called a weight or cost. These weights typically represent distances, costs, times, or capacities, and are crucial for algorithms like shortest path.

Question 4

What are the common terms for the components of a graph?

Accepted Answer

The fundamental components are:
- **Vertex (Node)**: A point or entity in the graph.
- **Edge (Arc)**: A connection between two vertices.
- **Path**: A sequence of distinct vertices where each adjacent pair is connected by an edge.
- **Cycle**: A path that starts and ends at the same vertex.

Question 5

Explain Adjacency Matrix representation for a graph.

Accepted Answer

An **Adjacency Matrix** is a square matrix of size $V 	imes V$ (where $V$ is the number of vertices). If there is an edge from vertex $i$ to vertex $j$, the entry $A[i][j]$ is 1 (or the weight of the edge); otherwise, it's 0 (or infinity for no edge in weighted graphs).

**Space Complexity**: $O(V^2)$.
**Time Complexity (Check edge)**: $O(1)$.
**Time Complexity (Find neighbors)**: $O(V)$.

Question 6

Explain Adjacency List representation for a graph.

Accepted Answer

An **Adjacency List** is an array of lists where the size of the array is $V$. Each index $i$ in the array stores a list of all vertices adjacent to vertex $i$. For weighted graphs, the list stores pairs of (neighbor, weight).

**Space Complexity**: $O(V+E)$ (where $E$ is the number of edges).
**Time Complexity (Check edge)**: $O(deg(v))$ for vertex $v$.
**Time Complexity (Find neighbors)**: $O(deg(v))$ for vertex $v$.

Question 7

When would you prefer an Adjacency Matrix over an Adjacency List?

Accepted Answer

An Adjacency Matrix is preferred for **dense graphs** (where $E$ is close to $V^2$) because it offers $O(1)$ edge lookup. It's also simpler for some algorithms that require quick access to any $A[i][j]$ entry, such as Floyd-Warshall.

Question 8

When would you prefer an Adjacency List over an Adjacency Matrix?

Accepted Answer

An Adjacency List is preferred for **sparse graphs** (where $E$ is much smaller than $V^2$) due to its lower space complexity $O(V+E)$ compared to $O(V^2)$. It's also more efficient for iterating over neighbors of a vertex, which is common in BFS and DFS.

Question 9

What is Breadth-First Search (BFS)?

Accepted Answer

BFS is a graph traversal algorithm that explores a graph level by level. It starts at a source vertex, visits all its immediate neighbors, then all their unvisited neighbors, and so on. It uses a `queue` data structure to manage vertices to visit.

**Time Complexity**: $O(V+E)$.
**Use Cases**: Finding the shortest path in an unweighted graph, finding connected components, network broadcasting.

Question 10

What is Depth-First Search (DFS)?

Accepted Answer

DFS is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It starts at a source vertex, explores one of its neighbors, then that neighbor's neighbor, and so on, until it hits a dead end. It uses a `stack` (or recursion) to manage vertices.

**Time Complexity**: $O(V+E)$.
**Use Cases**: Finding connected components, topological sorting, detecting cycles, pathfinding.

Question 11

What is the 'Shortest Path Problem'?

Accepted Answer

The Shortest Path Problem involves finding a path between two vertices (or a single source to all other vertices, or all pairs of vertices) in a graph such that the sum of the weights of its constituent edges is minimized. This is critical in navigation, network routing, and logistics.

Question 12

Explain Dijkstra's Algorithm.

Accepted Answer

Dijkstra's Algorithm finds the single-source shortest paths from a given source vertex to all other vertices in a graph with **non-negative edge weights**. It uses a `priority queue` to greedily select the unvisited vertex with the smallest known distance.

**Time Complexity**: $O(E \log V)$ or $O(E + V \log V)$ with a Fibonacci heap.
**Limitations**: Does not work with negative edge weights.
**Use Cases**: GPS navigation, network routing protocols (e.g., OSPF).

Question 13

Explain Bellman-Ford Algorithm.

Accepted Answer

Bellman-Ford Algorithm finds the single-source shortest paths from a given source vertex to all other vertices in a graph that **can have negative edge weights**. It works by repeatedly relaxing all edges $V-1$ times. It can also detect negative cycles.

**Time Complexity**: $O(VE)$.
**Advantages**: Handles negative edge weights, detects negative cycles.
**Limitations**: Slower than Dijkstra's for graphs without negative weights.
**Use Cases**: Routing protocols like RIP (Routing Information Protocol), detecting arbitrage opportunities.

Question 14

How does Bellman-Ford detect a negative cycle?

Accepted Answer

After $V-1$ iterations, if we can still relax any edge (i.e., find a shorter path to a vertex), it implies the existence of a negative cycle reachable from the source vertex. If a negative cycle exists, shortest paths are undefined because one could traverse the cycle infinitely to decrease the path length.

Question 15

Explain Floyd-Warshall Algorithm.

Accepted Answer

Floyd-Warshall Algorithm finds the **all-pairs shortest paths** in a weighted graph with positive or negative edge weights (but no negative cycles). It uses dynamic programming, iteratively considering all vertices as intermediate nodes in paths between all pairs of vertices.

**Time Complexity**: $O(V^3)$.
**Advantages**: Finds shortest paths between all pairs, handles negative weights.
**Limitations**: Does not work with negative cycles, higher complexity than single-source algorithms.
**Use Cases**: Finding all-pairs shortest paths in dense graphs, transitive closure, detecting cycles.

Question 16

When would you use Dijkstra's vs. Bellman-Ford?

Accepted Answer

Use **Dijkstra's** when all edge weights are non-negative, as it's generally faster ($O(E \log V)$). Use **Bellman-Ford** when the graph might contain negative edge weights, or if you need to detect negative cycles, despite its higher time complexity ($O(VE)$).

Question 17

When would you use Floyd-Warshall?

Accepted Answer

Use **Floyd-Warshall** when you need to find the shortest paths between *all pairs* of vertices in a graph. It's suitable for graphs with negative edge weights (but no negative cycles) and when $V$ is relatively small, given its $O(V^3)$ complexity.

Question 18

What is a 'connected component' in an undirected graph?

Accepted Answer

A **connected component** of an undirected graph is a subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the supergraph. A graph can have one or more connected components.

Question 19

What is a 'strongly connected component' (SCC) in a directed graph?

Accepted Answer

A **strongly connected component (SCC)** of a directed graph is a maximal subgraph such that for every pair of vertices $(u, v)$ in the subgraph, there is a path from $u$ to $v$ and a path from $v$ to $u$. Algorithms like Kosaraju's or Tarjan's can find SCCs.

Question 20

What is Topological Sorting?

Accepted Answer

Topological sorting is a linear ordering of vertices in a **directed acyclic graph (DAG)** such that for every directed edge $u 	o v$, vertex $u$ comes before vertex $v$ in the ordering. It's not unique for all DAGs. DFS is commonly used to implement it.

**Use Cases**: Task scheduling, course prerequisite ordering, build systems.

Question 21

What is the time complexity of finding the shortest path in an unweighted graph?

Accepted Answer

For an unweighted graph, the shortest path (in terms of number of edges) can be found using **Breadth-First Search (BFS)**. The time complexity for BFS is $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges.

Algorithms - Graph Theory & Shortest Path Algorithms

Cards in this deck

Related Flashcard Sets

JLPT N2 - Upper-Intermediate Japanese Kanji, Grammar & Expressions

CompTIA Network+ (N10-008) - Networking Fundamentals & Subnetting

HSK 4 - Intermediate Chinese Vocabulary & Grammar

CompTIA Network+ (N10-008) - Networking Fundamentals & Protocols