graph
A set of vertices (points) connected by edges (links), used to model networks such as roads, friendships or dependencies.
In more detail
Unlike a tree, a graph may contain cycles and need not have a root. Edges can be one-way (directed) or two-way (undirected), and can carry weights such as distances. Graphs are stored as an adjacency list or an adjacency matrix.
Related terms
- vertex — One point in a graph, such as a city on a road map or a person in a social network; also called a node.
- edge — A connection between two vertices of a graph, or between a parent and child in a tree.
- directed graph — A graph whose edges are one-way: an edge from A to B does not imply an edge from B to A.
- weighted graph — A graph in which every edge carries a number, its weight, such as a distance, cost or travel time.
- adjacency list — A graph representation that stores, for each vertex, a list of its neighbours, typically as a dict of lists in Python.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Representing A Graph: Matrix Or Adjacency List — Algorithms & Data Structures for Working Engineers
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers