Problem Solving with Algorithms and Data Structures using C++: The PreTeXt Interactive Edition

Glossary Glossary

acyclic graph.

A graph with no cycles.

adjacency list.

A list implementation where we keep a master list of all the vertices in the Graph object and then each vertex object in the graph maintains a list of the other vertices that it is connected to.

adjacency matrix.

A matrix implementation where each of the rows and columns represent a vertex in the graph, and where if two vertices are connected by an edge, they are considered adjacent.

adjacent.

When two vertices are connected by an edge.

breadth first search (BFS).

A search that proceeds to look through the edges in a graph to find all the vertices in that graph for which there is a path from the starting point.

cycle.

A cycle in a directed graph is a path that starts and ends at the same vertex.

cyclic graph.

A graph with at least one cycle in it.

depth first forest.

The result of the groups of trees produced by a depth first search algorithm.

depth first search (DFS).

A search type where the goal is to create the deepest depth first tree, without any branches.

digraph.

see directed graph.

directed acyclic graph (DAG).

A directed acyclic graph, which is a directed graph with no cycles.

directed graph.

A graph in which all the edges are one-way.

edge cost.

The weight associated with an arc in a graph.

edge.

An edge (also called an “arc”) connects two vertices to show that there is a relationship between them. Edges may be one-way or two-way.

parenthesis property.

All the children of a particular node in the depth first tree have a later discovery time and an earlier finish time than their parent.

path.

A path in a graph is a sequence of vertices that are connected by edges.

shortest path.

The most succinct passage from one edge to another.

spanning tree.

An acyclic subset of edges that connects all the vertices.

strongly connected components (SCC).

The largest subset of vertices \(C \subset V\) such that for every pair of vertices \(v,w \in C\) we have a path from \(v\) to \(w\) and a path from \(w\) to \(v\text{.}\)

topological sorting.

A topological sort takes a directed acyclic graph and produces a linear ordering of all its vertices such that if the graph G contains an edge (v,w) then the vertex v comes before the vertex w in the ordering.

uncontrolled flooding.

Each message starts with a time to live (ttl) value set to some number greater than or equal to the number of edges between the broadcast host and its most distant listener. Each router gets a copy of the message and passes the message on to all of its neighboring routers. When the message is passed on the ttl is decreased. Each router continues to send copies of the message to all its neighbors until the ttl value reaches 0.

vertex.

A vertex (also called a “node”) is a fundamental part of a graph. It can have a name (also called a “Key”). A vertex may also have additional information also called a (“payload”).

weight.

Shows that there is a cost to go from one vertex to another.