«Փնտրում դեպի լայնություն»–ի խմբագրումների տարբերություն

Առանց խմբագրման ամփոփման
(հեռացվել է Կատեգորիա:Ալգորիթմներ ՀոթՔաթ գործիքով)
 
Ալգորիթմը ստեղծվել է ուշ [[1950]]-ականներին [[Էդվարդ Մուր|Է․Ֆ․ Մուրի]] կողմից, ով օգտագործել է լաբիրինթից կարճագույն ճանապարհը գտնելու համար,<ref name="skiena">{{cite book |first=Steven |last=Skiena |authorlink=Steven Skiena |title=The Algorithm Design Manual |publisher=Springer |year=2008 |page=480 |doi=10.1007/978-1-84800-070-4_4}}</ref> և իրարից անկախ բացահայտվել է Լիի կողմից, որպես լարի երթուղայնացման ալգորիթմ (հրատարակվել է 1961)։<ref>{{cite conference |title=A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) |first1=Charles E. |last1=Leiserson |authorlink1=Charles E. Leiserson |first2=Tao B. |last2=Schardl |conference=ACM Symp. on Parallelism in Algorithms and Architectures |year=2010 |url=http://supertech.csail.mit.edu/papers/pbfs.pdf}}</ref><ref>{{cite news |title=An Algorithm for Path Connections and Its Applications |first1=C. Y. |last1=Lee |journal=IRE Transactions on Electronic Computers |year=1961 |url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5219222}}</ref>
== Pseudocode ==
 
'''Մուտք''': Գրաֆ և գրաֆի սկզբնական գագաթը
 
'''Ելք''': Բոլոր գագթնորը հասանելի են այն արմատից, որը բացահայտված է։
 
Փնտրում դեպի լայնության ոչ-ռեկուրսիվ ներկայացումը
 
 
<source lang="java" line="1">
Breadth-First-Search(Graph, root):
 
for each node n in Graph:
n.distance = INFINITY
n.parent = NIL
 
create empty queue Q
 
root.distance = 0
Q.enqueue(root)
 
while Q is not empty:
current = Q.dequeue()
for each node n that is adjacent to current:
if n.distance == INFINITY:
n.distance = current.distance + 1
n.parent = current
Q.enqueue(n)
</source>
 
== Ծանոթագրություններ ==
505

edits