Section 34.15 Vocabulary
- adjacency list
- A graph representation where for each vertex we maintain a list of adjacent vertices.
- adjacency map
- A graph representation where for each vertex we maintain a map of adjacent vertices.
- adjacency matrix
- A two-dimensional table indicating whether an edge exists between pairs of vertices.
- breadth-first search (BFS)
- A traversal that explores all neighbors at one depth before moving to the next depth.
- depth-first search (DFS)
- A traversal that follows one path as far as possible before backtracking.
- Dijkstra’s algorithm
- An algorithm for finding shortest paths from a source vertex in graphs with nonnegative edge weights.
- directed graph
- A graph whose edges have direction, going from one vertex to another.
- edges
- The connections between vertices in a graph.
- graph
- A data structure made of vertices and edges that represent relationships.
- implicit graphs
- Graphs where neighbors are generated by rules instead of being stored explicitly.
- iterative deepening
- A search strategy that repeatedly runs depth-limited DFS with increasing depth limits.
- logical representation (graph)
- A conceptual model of a graph focused on vertices and edges rather than storage details.
- loop (graph)
- An edge that starts and ends at the same vertex.
- minimum spanning tree
- A spanning tree of a weighted graph with the smallest possible total edge weight.
- nodes (graph)
- Another name for vertices, the points in a graph.
- parallel edges
- Multiple edges that connect the same pair of vertices.
- path
- A sequence of vertices where consecutive vertices are connected by edges.
- Prim’s algorithm
- A greedy algorithm that builds a minimum spanning tree by repeatedly adding the cheapest connecting edge.
- search tree
- A tree formed by recording how a graph search discovers vertices.
- simple path
- A path that does not repeat vertices.
- topological sorting
- A linear ordering of vertices in a directed acyclic graph so each edge points forward in the order.
- undirected graph
- A graph whose edges have no direction and can be traversed either way.
- unweighted graph
- A graph where edges are treated equally and do not carry numeric weights.
- vertices (graph)
- The points or nodes in a graph.
- weighted graph
- A graph whose edges have associated numeric weights or costs.
You have attempted of activities on this page.
