UVA Data Science: Advanced Algorithms for Graph Searching

A set of vocabulary flashcards derived from the lecture notes on graph searching algorithms in data science, focusing on essential concepts and terminology.

Graph Traversal

The process of visiting all the nodes and edges in a graph in a systematic way.

Breadth-First Search (BFS)

A graph traversal algorithm that explores all neighbors of a node before moving on to the next level nodes.

Edge

A connection between two vertices in a graph.

Vertex

A node in a graph.

Shortest Path Problem

The task of finding the shortest path from a source vertex to a destination vertex in a graph.

Dijkstra's Algorithm

An algorithm used to find the shortest path from a single source vertex to all others in a weighted graph with non-negative edge weights.

Priority Queue

A data structure that allows for efficient retrieval of the minimum (or maximum) element, used in Dijkstra's Algorithm.

Heuristic

A strategy or method used to make decisions or solve problems more quickly when classic methods are too slow.

A* Search

A search algorithm that finds the cheapest path from the start to the goal by combining the cost to reach the node and an estimated cost to reach the goal.

Greedy Best-First Search

A search algorithm that prioritizes exploring vertices that appear closest to the goal based only on heuristic estimates.

Brute-Force Search

An exhaustive search that explores all possible candidates for the solution without aiming for efficiency improvements.

Complexity of BFS

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Use Cases for BFS

Common applications include social networking, web crawling, and finding the shortest path in unweighted graphs.

Exhaustive Search

A problem-solving technique that systematically enumerates all possible candidates for the solution.

Optimal Solution

The best possible solution to a problem, typically the shortest path in pathfinding algorithms.

Visited Map

A record of which nodes have been visited during the traversal of a graph.

Queue

A data structure that follows the First-In-First-Out (FIFO) principle, commonly used to manage nodes in BFS.

Backtracking

A method used in algorithms to backtrack to find the shortest path by revisiting previously explored nodes.

Pathfinding Algorithm

Any algorithm used to find a path from a starting point to a goal point, often used in navigation and games.

Cost Weight

A numerical value assigned to an edge in a graph that represents the cost of traveling along that path.