Graphs and Network Algorithms
Modeling relationships with graphs
Graph fundamentals
A graph consists of vertices and edges. Graphs may be directed or undirected, weighted or unweighted. Many real-world systems can be modeled this way, including road networks, social networks, dependency graphs, and recommendation systems.
Common graph terms
Traversal methods
Breadth-first search
- Explores level by level
- Useful for shortest path in unweighted graphs
Depth-first search
- Explores deeply before backtracking
- Useful for connectivity, cycles, and topological ideas
Which traversal is typically used to find shortest paths in an unweighted graph?
BFS expands outward by distance and finds shortest paths in unweighted graphs.
Correct answer: BFS
What does a weighted graph represent?
Weights model real-world trade-offs.
Correct answer: A graph where edges have numerical costs such as distance, time, or capacity.
Shortest paths and optimization
Shortest-path algorithms help determine minimal cost routes, while minimum spanning tree algorithms connect all vertices with minimal total edge weight. These ideas are central in logistics, communications, and infrastructure planning.
Which graph concept is most associated with finding a route that starts and ends at the same vertex?
A cycle is a path that returns to its starting point.
Correct answer: Cycle
Why are graphs useful in computer science?
Many problems are naturally relational rather than linear.
Correct answer: They model complex relationships and connections between entities.
Graph thinking
If something has entities and relationships, consider whether a graph model will make the problem easier to express and solve.