Data Structures & Algorithms Graphs & Advanced Structures Syllabus

Graphs & Advanced Structures syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Graphs & Advanced Structures in Data Structures & Algorithms, not a summary of it.

1. 1

   Graph Representation

   2 topics

   • Graph Types
   • Representations
2. 2

   Graph Traversal

   3 topics

   • Breadth-First Search
   • Depth-First Search
   • Topological Sorting
3. 3

   Shortest Path Algorithms

   4 topics

   • Dijkstra's Algorithm
   • Bellman-Ford Algorithm
   • Floyd-Warshall Algorithm
   • A* Search
4. 4

   Minimum Spanning Trees

   2 topics

   • Kruskal's Algorithm
   • Prim's Algorithm
5. 5

   Disjoint Set Union

   3 topics

   • Union-Find Structure
   • Optimizations
   • Applications
6. 6

   Advanced Graph Topics

   3 topics

   • Strongly Connected Components
   • Articulation Points and Bridges
   • Network Flow Basics

Graphs & Advanced Structures flashcards for Data Structures & Algorithms

24 of 56 cards from the Graphs & Advanced Structures deck — real questions with worked answers.

1. What distinguishes a directed graph from an undirected graph?

   In a directed graph, each edge $(u,v)$ has an orientation from $u$ to $v$, so adjacency is not symmetric. In an undirected graph, an edge $\{u,v\}$ has no direction and connects both endpoints equally.

2. Define a weighted graph and give the standard notation for an edge weight.

   A weighted graph assigns a numeric value to each edge, written $w(u,v)$ (or $w(e)$). Weights model costs, distances, or capacities.

3. What is the maximum number of edges in a simple undirected graph with $n$ vertices, and in a simple directed graph?

   Undirected: $\binom{n}{2} = \frac{n(n-1)}{2}$. Directed (no self-loops): $n(n-1)$.

4. Define a complete graph $K_n$ and state its edge count.

   A complete graph $K_n$ has an edge between every pair of distinct vertices. It has $\frac{n(n-1)}{2}$ edges.

5. What is a bipartite graph, and what property characterizes it in terms of cycles?

   A bipartite graph's vertices split into two disjoint sets with all edges going between the sets. A graph is bipartite if and only if it contains no odd-length cycle.

6. Define a tree in graph terms and give its edge count for $n$ vertices.

   A tree is a connected, acyclic undirected graph. A tree on $n$ vertices has exactly $n-1$ edges.

7. What is a DAG?

   A Directed Acyclic Graph: a directed graph with no directed cycles. DAGs admit a topological ordering.

8. When is a graph called dense versus sparse?

   Dense: $|E|$ is close to $|V|^{2}$ (i.e., $|E| = \Theta(V^{2})$). Sparse: $|E|$ is close to $|V|$ (i.e., $|E| = O(V)$).

9. Compare space complexity of an adjacency matrix versus an adjacency list.

   Adjacency matrix: $O(V^{2})$ space. Adjacency list: $O(V + E)$ space. Lists are preferred for sparse graphs; matrices for dense graphs.

10. How long does it take to check whether edge $(u,v)$ exists in an adjacency matrix versus an adjacency list?

    Adjacency matrix: $O(1)$. Adjacency list: $O(\deg(u))$ in the worst case.

11. What is the time to iterate over all neighbors of a vertex $u$ in each representation?

    Adjacency list: $O(\deg(u))$. Adjacency matrix: $O(V)$, since the entire row must be scanned.

12. State the Handshaking Lemma for undirected graphs.

    The sum of all vertex degrees equals twice the number of edges: $$\sum_{v \in V} \deg(v) = 2|E|.$$

13. What data structure does BFS use, and what order does it explore vertices?

    BFS uses a FIFO queue and explores vertices in order of increasing distance (level by level) from the source.

14. State the time and space complexity of BFS on a graph with adjacency lists.

    Time: $O(V + E)$. Space: $O(V)$ for the queue and visited/distance arrays.

15. What problem does BFS solve optimally, and under what edge-weight condition?

    BFS finds shortest paths (fewest edges) from a source in an unweighted graph, or equivalently when all edge weights are equal.

16. What data structure underlies DFS, and how can it be implemented?

    DFS uses a LIFO stack, implemented either with explicit recursion (call stack) or an explicit stack.

17. State the time and space complexity of DFS with adjacency lists.

    Time: $O(V + E)$. Space: $O(V)$ for the recursion stack and visited array.

18. In DFS, what are tree edges, back edges, forward edges, and cross edges?

    Tree edge: to an unvisited vertex. Back edge: to an ancestor (indicates a cycle). Forward edge: to a descendant already finished. Cross edge: between unrelated subtrees. In undirected DFS only tree and back edges occur.

19. How does DFS detect a cycle in a directed graph?

    A directed graph has a cycle if and only if DFS encounters a back edge—an edge to a vertex currently on the recursion stack (in the 'gray'/in-progress state).

20. Define a topological sort of a DAG.

    A linear ordering of vertices such that for every directed edge $(u,v)$, $u$ appears before $v$. It exists if and only if the graph is a DAG.

21. Describe Kahn's algorithm for topological sorting.

    Repeatedly remove a vertex with in-degree $0$, append it to the order, and decrement the in-degree of its neighbors. Uses a queue of zero-in-degree vertices; runs in $O(V + E)$. If vertices remain with nonzero in-degree, a cycle exists.

22. How does DFS produce a topological order?

    Run DFS and push each vertex onto a stack when it finishes (post-order). The reversed finish order is a valid topological sort. Runs in $O(V + E)$.

23. What problem does Dijkstra's algorithm solve, and what is its key edge-weight restriction?

    Single-source shortest paths in a graph with non-negative edge weights. It fails if any edge weight is negative.

24. State Dijkstra's running time with a binary heap and with a Fibonacci heap.

    Binary heap: $O((V + E)\log V)$. Fibonacci heap: $O(E + V\log V)$.

See more Graphs & Advanced Structures flashcards →

Planning Graphs & Advanced Structures for Data Structures & Algorithms

Graphs & Advanced Structures (Data Structures & Algorithms) FAQ