15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 12 of 12 in the free DSA Basics course · 6 lessons
You will read, store, and explore graphs: collections of connected items. The path covers graph terminology, adjacency lists and matrices, Breadth First Search, Depth First Search, disconnected groups, and weighted edges.
The lessons move from graph language to storage, traversal, repeated traversal, and weighted edges. Vertices and edges must be defined before they can be stored, and an algorithm needs a representation to inspect neighbors.
There are no required prior roadmap lessons.
You should be comfortable with:
A, B, and C.Use this undirected graph throughout the path:
A, B, C, D, EA-B, A-C, B-D, C-DE has no edges.A, B, C, and D form one connected group. E is isolated, so the full graph is disconnected.
An adjacency-list representation is:
1A: [B, C]
2B: [A, D]
3C: [A, D]
4D: [B, C]
5E: []Because the graph is undirected, every edge appears in both directions. For example, A-B means B appears in A’s list and A appears in B’s list.
Starting at A, BFS visits by edge-distance layers:
1[A] → [B, C] → [D]The traversal does not reach E. With the shown neighbor order, DFS can discover vertices in this order:
1A, B, D, CTo cover the whole graph, start another traversal at unvisited E. That reveals two connected components:
1{A, B, C, D}
2{E}If A-B has weight 4, store that number on the edge, such as:
1A: [(B, 4), (C, 1)]The weight is a cost of using the edge. Edge count measures how many edges a path uses. Weight does not change which vertices are neighbors.
Graph Terminology and Types gives names for the parts of the running example: vertices, edges, neighbors, degree, direction, connectivity, self-loops, and parallel edges.
Adjacency List and Matrix converts that vocabulary into data structures. You will store the same graph as lists of neighbors and as a table of connections.
Breadth First Search uses an adjacency representation, a queue, and a visited structure to explore reachable vertices in increasing numbers of edges from a start vertex.
Depth First Search uses the same graph representation and visited idea. It explores one route as far as possible before backtracking.
Connected Components builds on traversal. Scan every vertex and begin another DFS whenever you find an unvisited one, such as E.
Intro to Weighted Graphs attaches numeric costs to edges. You will represent those costs and separate total path weight from the number of edges in a path.
Begin with Graph Terminology and Types because later decisions depend on the graph’s type. An undirected edge such as A-B has two-way meaning, so both the representation and traversal treat A and B as neighbors. A directed graph requires a different interpretation. A weighted graph needs extra edge data.
Adjacency List and Matrix gives traversal algorithms a way to ask, “Which vertices are adjacent to this vertex?” For the running example, the list for A answers B and C. An adjacency list lets an algorithm iterate through neighbors. An adjacency matrix stores one row and column per vertex and makes checking one possible edge direct, while storing entries for every vertex pair.
Breadth First Search uses a queue. It completes the nearby layer before moving farther away. Depth First Search marks a vertex and follows an unvisited neighbor immediately. It returns when it has no unvisited neighbor left. Both need a visited structure because the cycle through A, B, D, and C could otherwise cause repeated work or non-terminating exploration.
A single BFS or DFS from A only describes what is reachable from A. Connected Components continues the scan after that first traversal. Since E remains unvisited, it starts a second traversal and receives a different component identifier.
Intro to Weighted Graphs keeps the graph structure and attaches a cost to each edge. An edge can connect A to B and carry a cost such as 4. BFS layers measure edge count: B is one edge from A. BFS layers do not generally measure lowest total cost once weights are present.
Draw the running example from its vertex and edge list. Name each vertex and edge. Verify that E is isolated and that the graph is undirected and disconnected.
Write its adjacency list. Check every undirected edge appears from both endpoints. Then create an adjacency matrix using vertex order A, B, C, D, E.
Trace Breadth First Search from A. Keep a queue and visited set. Record each vertex’s layer and confirm that E is never discovered.
Trace Depth First Search from A using the listed neighbor order. Mark each vertex before exploring its neighbors, and note where backtracking occurs.
Scan vertices from A through E for Connected Components. Run DFS from the first unvisited vertex, assign one component identifier to A, B, C, and D, then assign another to E.
Add weights to the edges, for example A-B: 4, A-C: 1, B-D: 2, and C-D: 7. Rewrite the adjacency list with (neighbor, weight) entries. Compare a path’s edge count with its total weight, and do not use BFS layer number as its weighted cost.