You are viewing a free preview of this lesson.
Subscribe to unlock all 10 lessons in this course and every other course on LearningBro.
This lesson covers graphs — a versatile and powerful data structure used to model relationships between objects. Graphs are a key topic in the OCR A-Level Computer Science (H446) specification, section 1.4.
A graph G is defined as a set of vertices (nodes) V and a set of edges (connections) E:
G = (V, E)
Graphs differ from trees because they can contain cycles (paths that loop back), there is no hierarchy (no root), and any vertex can connect to any other vertex.
| Term | Definition |
|---|---|
| Vertex (Node) | A data point in the graph. |
| Edge (Arc) | A connection between two vertices. |
| Adjacent | Two vertices connected by an edge. |
| Degree | The number of edges connected to a vertex. |
| Path | A sequence of vertices connected by edges. |
| Cycle | A path that starts and ends at the same vertex. |
| Connected graph | A path exists between every pair of vertices. |
| Complete graph | Every vertex is connected to every other vertex. |
Subscribe to continue reading
Get full access to this lesson and all 10 lessons in this course.