A correlation matrix thresholded into a graph, a settlement network, or a dependency graph among risk-factor models are all instances of the same object: a graph, , a set of vertices and a set of edges connecting pairs of them. This short topic — deliberately brief, matching this unit's profile Stage 4 framing — builds the representational and traversal vocabulary every graph algorithm in Topic 5 and Topic 7 is built on: adjacency lists vs. matrices as the two ways to store a graph, breadth-first search (BFS) and depth-first search (DFS) as the two fundamental traversal strategies, and topological sort and strongly connected components (SCCs) as the two classical decomposition tools for directed graphs.
By the end of this topic you should be able to:
- choose between adjacency-list and adjacency-matrix representation based on graph density and the operations needed;
- implement BFS and state its shortest-path-in-edges guarantee on unweighted graphs;
- implement DFS and use discovery/finish times to classify edges;
- compute a topological ordering of a DAG via DFS finish times, and explain why it requires acyclicity;
- describe, at a conceptual level, how strongly connected components decompose a directed graph.
In this lesson
- Contents
- The big picture
The full lesson is for members.
Read the full lessonNew to SelfMadeQuant.com? See membership options or explore the curriculum.