Graph Traversal Techniques

Flashcards covering key concepts and definitions related to Depth First Search and Breadth First Search algorithms in graph theory.

Depth First Search (DFS)

A graph traversal algorithm that explores as far as possible along each branch before backtracking.

Breadth First Search (BFS)

A graph traversal algorithm that explores all neighbors at the present depth prior to moving on to nodes at the next depth level.

Visited List

A list that keeps track of the nodes that have already been visited during a traversal.

Stack

A data structure used in Depth First Search to keep track of the vertices to visit next.

Queue

A data structure used in Breadth First Search to hold the vertices to be visited in a FIFO order.

Graph with 5 vertices

A graphical representation with five nodes where edges can connect any pair of vertices.

Adjacent Vertex

A vertex that is directly connected to another vertex by an edge.

Traversal Completion

The point in the algorithm where all reachable vertices have been visited and there are no more nodes to explore.

Unvisited Adjacent Vertex

A vertex connected to the current vertex that has not yet been visited in the traversal process.

Last Element in Traversal

The final vertex visited before concluding the graph traversal.