C++UCS301
Graphs & ApplicationsC++17

Graph Fundamentals

Graphs consist of vertices and edges and may be directed, undirected, weighted, cyclic, connected, or sparse.

Open this in the visual lab

What to understand

  • Core terminology
  • Degree and paths
  • Connected components
  • Directed versus undirected models

Remember this

  1. 1Model vertices and edges precisely
  2. 2A tree is a connected acyclic graph
  3. 3Edge direction changes reachability

Detailed notes

A graph models entities as vertices and relationships as edges. Direction represents asymmetric relationships, weights quantify cost or capacity, and paths describe sequences of reachable relationships.

Connectivity, cycles, degree, components, and reachability depend on whether the graph is directed. A tree is the special undirected case that is connected and acyclic, giving exactly one simple path between every pair.

How it works

  1. 1Define what one vertex and one edge represent.
  2. 2Decide direction, weight, multiplicity, and self-loop rules.
  3. 3Identify whether the graph may be disconnected.
  4. 4Match terminology and algorithm assumptions to the chosen model.

Where it is used

  • Transport, communication, and social networks
  • Dependencies and prerequisite systems
  • Resource flow and infrastructure planning

Common mistakes

  • Forgetting to add both directions for an undirected edge
  • Using degree terminology incorrectly on directed graphs
  • Applying a connected-graph result without checking components

Implementation perspective

This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.

Exam & viva

Open a prompt when you are ready to check your answer.