Think together · Start with a story
There are roads between the school, library, and park. The girl notices that a route can loop around, so a family-tree style drawing cannot show everything.
Break down the process
- PointsThree places
- EdgesRoads between places
- RelationshipsConnections to explore
A graph uses vertices to represent objects and edges to represent relationships.
01“Graph” does not mean a picture here
In data structures, a graph is a collection of connected objects, not necessarily a chart or drawing.
02A very simple graph
A graph can have just a few objects and connections between them.
03What are vertices and edges?
Vertex
Represents an object, such as a city, user, or web page.
Edge
Represents a connection between objects, such as a road, friendship, or link.
04Can a graph have direction?
Yes.
Undirected graph
A and B are connected, with no direction.
Directed graph
A → B and B → A can represent different relationships.
05Can a graph have cycles?
Yes.
This forms a cycle. Unlike trees, general graphs can have cycles.
06Must every point in a graph be connected?
No.
A graph can contain parts with no path connecting them. These parts can form different connected components.
07What real-world problems can be modeled as graphs?
City roads
Cities are vertices; roads are edges.
Social networks
Users are vertices; relationships are edges.
The internet
Devices or networks are vertices; connections are edges.
Web links
Web pages are vertices; hyperlinks are directed edges.
08How do programs store graphs?
Common methods include:
- Adjacency matrix
- Adjacency list
- Edge list
Different representations suit different sizes and operations.
What you have learned
- A graph is made of vertices and edges.
- A graph can represent general relationships between connected objects.
- A graph can be directed or undirected.
- A graph can have cycles and may be disconnected.
- Graphs can be stored using adjacency lists, adjacency matrices, and other representations.
Next: What Is the Difference Between Trees and Graphs?
Your turn to try
If there is a one-way road from school to the park, can you assume you can travel back from the park to school?
Ready? Open to see the explanation
No. A directed edge allows travel only in its specified direction. You would need a separate edge in the opposite direction.