Index
Basic Definitions
Breadth-First Search (BFS)
Depth-First Search (DFS)
Basic Definitions
Graph is a data structure that contains a vertex set V = the set of its vertices/nodes and an edge set E = the set of its edges. In a directed graph (or digraph), edges are directed, and a vertex is allowed to have an edge directed to itself. While in a undirected graph, things are opposite.
In a directed graph, an edge (u, v) is incident from or leaves vertex u and is incident to or enters vertex v. In an undirected graph, an edge (u, v) is incident on vertex u and v. (u, v) means v is adjacent to u.
The degree of a vertex in an undirected graph is the number of edges incident on it. A vertex with degree 0 is called isolated. In a directed graph, the out-degree of a vertex is the number of edges leaving it, and the in-degree of a vertex is the number of edges entering it.
Breadth-First Search (BFS)
BFS traverses the graph level by level, consequently showing a shortest path from the starting node to any of its reachable nodes, assuming edges are unweighted.
Example: Solving a Pocket Cube (2x2x2)
The configuration graph for PC is an undirected graph with vertices that represent all possible states of the PC and edges that represent all possible moves. It is proved that at most 11 moves are needed to go from one state to any other state. (The number for 3x3x3 Rubik’s Cube is 20). In order to solve the problem, we can construct a 11-level (or a diameter of 11) graph that spans out from the vertex that represents the solved state, then use BFS.
BFS in C++