Checkpoint 9.27.1.
- weight
- Shows that there is a cost to go from one vertex to another
- 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
- In a directed graph, a path that starts and ends at the same vertex.
- depth first search (DFS)
- A search type where the goal is to create the deepest tree first, without any branches.
- 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.
- vertex
- Also called a “node” this is a fundamental part of a graph. It can have a “key”. This may also have additional information. We will call this additional information the “payload”.
- spanning tree
- An acyclic subset of edges that connects all the vertices.
- path
- A sequence of vertices that are connected by edges.
- 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.
- edge cost
- The weight associated with an arc in a graph.
- edge
- An “arc” connects two vertices to show that there is a relationship between them and it may be one-way or two-way.
- directed graph
- A graph in which all the edges are one-way.
- 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.
Drag the word on the left to its corresponding definition (Note not all words in the glossary are here)
Look at your glossary
