Skip to content

Update breadth-first-search.md #50

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 4 commits into from
Oct 5, 2016
Merged

Update breadth-first-search.md #50

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
4 commits
Select commit Hold shift + click to select a range
3b02e34
Update breadth-first-search.md
PAVBAN95 Oct 4, 2016
931b82b
U
PAVBAN95 Oct 4, 2016
b0b5d8b
Update breadth-first-search.md
PAVBAN95 Oct 4, 2016
f6827ea
fixed typo
PAVBAN95 Oct 4, 2016
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
3 changes: 2 additions & 1 deletion src/graph/breadth-first-search.md
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -1,7 +1,7 @@
<!--?title Breadth First Search -->

# Breadth-first search
Breadth first search is one of the basic and essential algorithms on graphs.
Breadth first search is one of the basic and essential searching algorithms on graphs.

As a result of how the algorithm works, the path found by breadth first search to any node is the shortest path to that node i.e
the path that contains the smallest number of edges in unweighted graphs.
Expand Down Expand Up @@ -97,5 +97,6 @@ manner:
* [SPOJ: AKBAR](http://spoj.com/problems/AKBAR)
* [SPOJ: NAKANJ](http://www.spoj.com/problems/NAKANJ/)
* [SPOJ: WATER](http://www.spoj.com/problems/WATER)
* [SPOJ: MICE AND MAZE](http://www.spoj.com/problems/MICEMAZE/)


2 changes: 1 addition & 1 deletion src/string/z-function.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -7,7 +7,7 @@ In other words, $z[i]$ is the length of the longest common prefix between $s$ an

**Note.** In this article, to avoid ambiguity, we assume $0$-based indexes; that is: the first character of $s$ has index $0$ and the last one has index $n-1$.

The first element of Z-functions, $z[0]$, is generally not well defined. In this article we will assume it is zero (although it doesn't change anything in the algorithm implementation).
The first element of Z-function, $z[0]$, is generally not well defined. In this article we will assume it is zero (although it doesn't change anything in the algorithm implementation).

This article presents an algorithm for calculating the Z-function in $O(n)$ time, as well as various of its applications.

Expand Down