<\/span><\/h3>\nMain Idea:<\/strong> DFS is a systematic method of visiting the vertices of a graph. Its general step requires that if we are currently visiting vertex \u2018u\u2019, then we next visit a vertex adjacent to \u2018u\u2019 which has not yet been visited. If no such vertex exists then we return to the vertex visited just before u, and the search is repeated until every vertex in that component of the graph has been visited.<\/p>\nDFS uses a strategy that searches \u201cdeeper\u201d in the graph whenever possible, unlike BFS which discovers all vertices at distance \u2018k\u2019 from the source before discovering any vertices at distance k+1.<\/p>\n
The predecessor subgraph produced by DFS may be composed of several trees, because the search may be repeated from several sources. This predecessor subgraph forms a depth-first forest depth-first forest \u2018E\u2019 composed of several depth-first trees and the edges in \u2018E\u2019 are called tree edges. On the other hand the predecessor subgraph of BFS forms a tree.<\/p>\n
Besides creating a depth first forest, depth first search also timestamps each vertex.<\/p>\n
<\/span>Each vertex has two timestamps:<\/strong><\/span><\/h4>\n\n- The first timestamp d[v] records when v is discovered (and grayed).<\/li>\n
- The second timestamp f[v] records when the search finishes examining v\u2019s adjacency list (and blackens v).<\/li>\n<\/ol>\n
The procedure DFS below records when it discovers vertex u in the variable d[u]and when it finishes vertex u in the variable f [u]. These timestamps are integers between 1 and 2|v|, since, there is one discovery event and one finishing event for each of the |v| vertices. For every vertex v,<\/p>\n
d[v]<f[v]<\/p>\n
<\/span> Application of Depth First Search<\/strong><\/span><\/h4>\n\n- We can determine the articulation point through depth first search.<\/li>\n
- We can determine bridges through depth-first search.<\/li>\n
- We can determine number of connected components through depth first search.<\/li>\n
- We can also determine cycle.<\/li>\n<\/ol>\n
<\/span> Breadth-First Search<\/strong><\/span><\/h3>\n\n- Input: Graph G = (V, E), either directed or undirected, and source vertex s \u2208 V.<\/li>\n
- Output:(a) d[v] = distance (smallest number of edges, or shortest path) from s to v, for all v \u2208 V. d[v] = \u221e if v is not reachable from s.
\n(b) p[v] = u such that (u, v) is last edge on shortest path s to v. u is v\u2019s predecessor.
\n(c) Builds breadth-first tree with root s that contains all reachable vertices<\/li>\n<\/ul>\n<\/span> Definitions:<\/strong><\/span><\/h4>\n\n- Path between vertices u and v: Sequence of vertices (v1, v2,. . . , vk) such that u = v1 and v = vk, and (vi , vi +1) \u2208 E, for all 1 \u2264 i \u2264 k \u2013 1.<\/li>\n
- Length of the path: Number of edges in the path.<\/li>\n
- Path is simple if no vertex is repeated.<\/li>\n
- Expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier.
\n(a) A vertex is \u201cdiscovered\u201d the first time it is encountered during the search.
\n(b) A vertex is \u201cfinished\u201d if all vertices adjacent to it have been discovered.<\/li>\n<\/ul>\n\n- Colors the vertices to keep track of progress.
\n(a) White \u2013 Undiscovered.
\n(b) Gray \u2013 Discovered but not finished.
\n(c) Black \u2013 Finished.<\/li>\n<\/ul>\n\n- Colors are required only to reason about the algorithm. Can be implemented without colors.<\/li>\n<\/ul>\n
<\/span>Applications of Breadth First Search<\/strong><\/span><\/h4>\n\n- To test if a graph is bipartite.<\/li>\n
- Cycle detection in undirected graph.<\/li>\n
- To find if there is a path between two vertices.<\/li>\n
- Finding all nodes within one connected components<\/li>\n
- Number of connected components.<\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"
When we characterize the running time of a graph algorithm on a given graph G = (V, E), we usually<\/p>\n","protected":false},"author":1,"featured_media":6276,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1831,3],"tags":[1841,1842,1852,1853],"class_list":["post-6250","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithms","category-cs-it","tag-breadth-first-search","tag-depth-first-search-dfs","tag-dfs-and-bfs","tag-dfs-and-bfs-difference"],"_links":{"self":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6250","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/comments?post=6250"}],"version-history":[{"count":0,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/posts\/6250\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media\/6276"}],"wp:attachment":[{"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/media?parent=6250"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/categories?post=6250"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.madeeasy.in\/study\/wp-json\/wp\/v2\/tags?post=6250"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}