Graph Search: Difference between revisions
Jump to navigation
Jump to search
| Line 3: | Line 3: | ||
=Overview= | =Overview= | ||
Searching a graph is a fundamental problem in computer science. It means systematically following the edges of a graph so we visit all the vertices of that graph. Techniques for searching a graph lie at the heart of the field of graph algorithms. There are many methods to search graphs, and the most known and used are [[#Breadth-First_Search|breadth-first search]] and [[#Depth-First_Search|depth-first search]]. | |||
Both breadth-first search and depth-first search algorithms are very efficient, in that they walk the entire graph in linear time of the number of vertices and edges O(n + m). | Both breadth-first search and depth-first search algorithms are very efficient, in that they walk the entire graph in linear time of the number of vertices and edges O(n + m). | ||
Revision as of 22:58, 1 October 2021
Internal
Overview
Searching a graph is a fundamental problem in computer science. It means systematically following the edges of a graph so we visit all the vertices of that graph. Techniques for searching a graph lie at the heart of the field of graph algorithms. There are many methods to search graphs, and the most known and used are breadth-first search and depth-first search.
Both breadth-first search and depth-first search algorithms are very efficient, in that they walk the entire graph in linear time of the number of vertices and edges O(n + m).