unweighted graph
A graph whose edges carry no weights, so every edge counts the same.
In more detail
In an unweighted graph the shortest path is simply the one with fewest edges, which breadth-first search finds in O(V + E). Social networks, where every friendship counts the same, are usually modelled this way.
Related terms
- breadth-first search — A graph search that visits the start vertex, then all its neighbours, then all of theirs, spreading out in waves using a FIFO queue.
- weighted graph — A graph in which every edge carries a number, its weight, such as a distance, cost or travel time.
- hop — One step along an edge; a path's hop count is how many edges it crosses, ignoring any weights.
Taught in
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers