141:
152:
530:
36:
542:
470:, replacing the queue of this breadth-first search algorithm with a stack will yield a depth-first search algorithm. For general graphs, replacing the stack of the iterative depth-first search implementation with a queue would also produce a breadth-first search algorithm, although a somewhat nonstandard one.
926:
of an infinite graph. In this context, a search method is described as being complete if it is guaranteed to find a goal state if one exists. Breadth-first search is complete, but depth-first search is not. When applied to infinite graphs represented implicitly, breadth-first search will eventually
205:
from the current position by applying all possible moves and use breadth-first search to find a win position for White. Implicit trees (such as game trees or other problem-solving trees) may be of infinite size; breadth-first search is guaranteed to find a solution node if one exists.
498:
attribute of each node is useful for accessing the nodes in a shortest path, for example by backtracking from the destination node up to the starting node, once the BFS has been run, and the predecessors nodes have been set.
878:
When working with graphs that are too large to store explicitly (or infinite), it is more practical to describe the complexity of breadth-first search in different terms: to find the nodes that are at distance
217:
avoids the latter drawback at the price of exploring the tree's top parts over and over again. On the other hand, both depth-first algorithms typically require far less extra memory than breadth-first search.
1585:
1185:
1794:
2456:
1659:
1389:
1101:
2487:
1723:
237:, repeated searches of vertices are often allowed, while in theoretical analysis of algorithms based on breadth-first search, precautions are typically taken to prevent repetitions.
213:(DFS), which explores the node branch as far as possible before backtracking and expanding other nodes, may get lost in an infinite branch and never make it to the solution node.
2746:
1221:
798:
When the number of vertices in the graph is known ahead of time, and additional data structures are used to determine which vertices have already been added to the queue, the
1488:
793:
619:
1679:
1429:
1328:
974:
1874:
839:
718:
1848:
1821:
1515:
1456:
1268:
1023:
747:
869:
679:
649:
1409:
1308:
1288:
1241:
1121:
1043:
994:
2480:
2308:
458:
it checks whether a vertex has been explored before enqueueing the vertex rather than delaying this check until the vertex is dequeued from the queue.
2739:
2473:
2847:
1972:
257:
214:
2429:
2209:
2151:
1936:
Serialization/Deserialization of a binary tree vs serialization in sorted order, allows the tree to be re-constructed in an efficient manner.
1889:
935:
An enumeration of the vertices of a graph is said to be a BFS ordering if it is the possible output of the application of BFS to this graph.
53:
2732:
2825:
2351:
2317:
1982:
241:
133:
2394:
2283:
119:
100:
2419:
72:
2058:
1520:
480:
Nodes can be labelled as explored by storing them in a set, or by an attribute on each node, depending on the implementation.
2912:
57:
1126:
79:
871:
is the number of vertices. This is in addition to the space required for the graph itself, which may vary depending on the
2830:
1987:
2902:
1923:
1728:
927:
find the goal state, but depth first search may get lost in parts of the graph that have no goal state and never return.
2665:
2635:
2620:
1917:
1590:
86:
2892:
910:
In the analysis of algorithms, the input to breadth-first search is assumed to be a finite graph, represented as an
2985:
2690:
2564:
2554:
2534:
2273:
872:
452:
444:
1336:
1048:
46:
2980:
2569:
68:
2935:
2950:
2233:
1684:
2897:
2869:
2708:
2670:
919:
234:
2776:
2940:
2907:
2788:
2514:
187:
145:
2927:
2884:
2574:
2544:
467:
183:
179:
175:
1893:
1190:
2332:
Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett
Learning. pp. 79–80.
2815:
2793:
2685:
2660:
2261:
2131:
1927:
2945:
2781:
2695:
2680:
2625:
1461:
93:
2961:
2842:
2713:
2615:
2610:
2524:
2400:
2372:
2180:
1967:
1911:
448:
436:
230:
210:
136:
Animated example of a breadth-first search. Black: explored, grey: queued to be explored later on
2917:
752:
569:
256:, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a
2864:
2805:
2675:
2519:
2425:
2390:
2347:
2313:
2299:
2279:
2215:
2205:
2147:
1664:
1414:
1313:
941:
2655:
2640:
2382:
2257:
2172:
2139:
2040:
1853:
915:
899:
805:
799:
684:
534:
222:
1826:
1799:
1493:
1434:
1246:
2768:
2755:
2630:
2104:
1977:
1951:
999:
723:
563:
253:
252:
programming language, but this was not published until 1972. It was reinvented in 1959 by
190:, is needed to keep track of the child nodes that were encountered but not yet explored.
140:
844:
654:
624:
2135:
2759:
2496:
2435:
2269:
1394:
1293:
1273:
1226:
1106:
1028:
979:
923:
918:, or similar representation. However, in the application of graph traversal methods in
911:
226:
2724:
1884:
Breadth-first search can be used to solve many problems in graph theory, for example:
151:
2974:
2859:
2645:
2600:
2123:
1899:
249:
194:
2404:
2184:
435:
This non-recursive implementation is similar to the non-recursive implementation of
17:
2595:
2559:
2529:
2303:
1944:
1931:
518:
The following is an example of the breadth-first tree obtained by running a BFS on
198:
545:
The breadth-first tree obtained when running BFS on the given map and starting in
2465:
186:
prior to moving on to the nodes at the next depth level. Extra memory, usually a
2810:
2549:
2143:
2083:
245:
156:
35:
2062:
2539:
2265:
2219:
529:
477:
queue contains the frontier along which the algorithm is currently searching.
2176:
2167:
Lee, C. Y. (1961). "An
Algorithm for Path Connections and Its Applications".
1957:
Implementing parallel algorithms for computing a graph's transitive closure.
2500:
2460:
2386:
546:
202:
178:
data structure for a node that satisfies a given property. It starts at the
171:
2369:
Theoretically
Efficient Parallel Graph Algorithms Can Be Fast and Scalable
2087:
132:
2059:"Graph500 benchmark specification (supercomputer performance evaluation)"
621:, since every vertex and every edge will be explored in the worst case.
2650:
2094:. See pp. 96–105 of the linked pdf file (internal numbering 2.47–2.56).
883:
from the start node (measured in number of edge traversals), BFS takes
541:
519:
2199:
229:
with a given start node (sometimes referred to as a 'search key'). In
2367:
Dhulipala, Laxman; Blelloch, Guy E.; Shun, Julian (August 21, 2019).
2109:
Proceedings of the
International Symposium on the Theory of Switching
2044:
2033:"Depth-First Iterative Deepening: An Optimal Admissible Tree Search"
2377:
2032:
1910:, with path length measured by number of edges (an advantage over
540:
528:
139:
2874:
2798:
2579:
2728:
2469:
2342:
Aziz, Adnan; Prakash, Amit (2010). "4. Algorithms on Graphs".
29:
2278:(2nd ed.). MIT Press and McGraw-Hill. pp. 531–539.
2457:
Open Data
Structures - Section 12.3.1 - Breadth-First Search
2854:
2837:
1580:{\displaystyle w\in V\setminus \{v_{1},\dots ,v_{i-1}\}}
1180:{\displaystyle v\in V\setminus \{v_{1},\dots ,v_{m}\}}
1856:
1829:
1802:
1731:
1687:
1667:
1593:
1523:
1496:
1464:
1437:
1417:
1397:
1339:
1316:
1296:
1276:
1249:
1229:
1193:
1129:
1109:
1051:
1031:
1002:
982:
944:
847:
808:
755:
726:
687:
657:
627:
572:
2926:
2883:
2767:
2588:
2507:
1789:{\displaystyle v_{i}\in N(v_{k})\setminus N(v_{j})}
60:. Unsourced material may be challenged and removed.
2234:"Stack-based graph traversal ≠depth first search"
1868:
1842:
1815:
1788:
1717:
1673:
1653:
1579:
1509:
1482:
1450:
1423:
1403:
1383:
1322:
1302:
1282:
1262:
1235:
1215:
1179:
1115:
1095:
1037:
1017:
988:
968:
863:
833:
787:
741:
712:
673:
643:
613:
2113:As cited by Cormen, Leiserson, Rivest, and Stein.
2006:that is, a node satisfying the specified property
1654:{\displaystyle \nu _{(v_{1},\dots ,v_{i-1})}(w)}
221:Breadth-first search can be generalized to both
2198:Cormen, Thomas H. "22.2 Breadth-first search".
681:is the number of edges in the graph. Note that
2421:The Art of Computer Programming Vol 1. 3rd ed.
2016:Cormen Thomas H.; et al. (2009). "22.3".
795:, depending on how sparse the input graph is.
2740:
2481:
2111:. Harvard University Press. pp. 285–292.
8:
2107:(1959). "The shortest path through a maze".
1574:
1536:
1384:{\displaystyle \sigma =(v_{1},\dots ,v_{n})}
1174:
1142:
1096:{\displaystyle \sigma =(v_{1},\dots ,v_{m})}
875:used by an implementation of the algorithm.
2747:
2733:
2725:
2488:
2474:
2466:
2309:Artificial Intelligence: A Modern Approach
1431:is said to be a BFS ordering (with source
502:Breadth-first search produces a so-called
2376:
2092:(in German), Konrad Zuse Internet Archive
1855:
1834:
1828:
1807:
1801:
1777:
1755:
1736:
1730:
1686:
1666:
1625:
1606:
1598:
1592:
1562:
1543:
1522:
1501:
1495:
1463:
1442:
1436:
1416:
1396:
1372:
1353:
1338:
1315:
1295:
1275:
1254:
1248:
1228:
1198:
1192:
1168:
1149:
1128:
1108:
1084:
1065:
1050:
1030:
1001:
981:
943:
902:" of the graph (the average out-degree).
856:
848:
846:
823:
815:
807:
776:
771:
762:
754:
725:
702:
694:
686:
666:
658:
656:
636:
628:
626:
603:
595:
587:
579:
571:
487:is usually interchangeable with the word
120:Learn how and when to remove this message
2169:IRE Transactions on Electronic Computers
248:, in his (rejected) Ph.D. thesis on the
150:
131:
27:Algorithm to search the nodes of a graph
1999:
1764:
1718:{\displaystyle 1\leq i<j<k\leq n}
1533:
1139:
2272:(2001) . "22.2 Breadth-first search".
1973:Iterative deepening depth-first search
295:links trace the shortest path back to
215:Iterative deepening depth-first search
182:and explores all nodes at the present
1391:be an enumeration of the vertices of
7:
2061:. Graph500.org, 2010. Archived from
537:with some connections between cities
58:adding citations to reliable sources
439:, but differs from it in two ways:
244:of graphs were invented in 1945 by
240:BFS and its application in finding
1983:Lexicographic breadth-first search
1317:
1103:be a list of distinct elements of
25:
2126:(2008). "Sorting and Searching".
1216:{\displaystyle \nu _{\sigma }(v)}
510:looks in the following example.
411:as explored 12
34:
2962:List of graph search algorithms
2312:(2nd ed.). Prentice Hall.
260:algorithm (published in 1961).
45:needs additional citations for
1783:
1770:
1761:
1748:
1681:is a BFS ordering if, for all
1648:
1642:
1637:
1599:
1378:
1346:
1210:
1204:
1090:
1058:
1012:
1006:
963:
951:
857:
849:
828:
824:
816:
812:
782:
772:
763:
759:
736:
730:
707:
703:
695:
691:
667:
659:
651:is the number of vertices and
637:
629:
608:
604:
596:
588:
580:
576:
1:
1988:Parallel breadth-first search
1483:{\displaystyle 1<i\leq n}
2144:10.1007/978-1-84800-070-4_4
2128:The Algorithm Design Manual
1796:, there exists a neighbor
1025:is the set of neighbors of
403:is not labeled as explored
3002:
2424:, Boston: Addison-Wesley,
2275:Introduction to Algorithms
2201:Introduction to algorithms
2018:Introduction to Algorithms
1661:is minimal. Equivalently,
788:{\displaystyle O(|V|^{2})}
614:{\displaystyle O(|V|+|E|)}
407:11 label
2959:
2704:
2418:Knuth, Donald E. (1997),
2344:Algorithms for Interviews
2130:. Springer. p. 480.
2031:Korf, Richard E. (1985).
558:Time and space complexity
321:be a queue 3 label
2177:10.1109/TEC.1961.5219222
1952:bipartiteness of a graph
2870:Monte Carlo tree search
2709:List of data structures
2387:10.1145/3210377.3210414
2037:Artificial Intelligence
1918:(Reverse) Cuthill–McKee
1674:{\displaystyle \sigma }
1424:{\displaystyle \sigma }
1323:{\displaystyle \infty }
996:vertices. Recall that
969:{\displaystyle G=(V,E)}
924:implicit representation
920:artificial intelligence
894:time and memory, where
455:(Last In First Out) and
352:.dequeue() 7
235:artificial intelligence
1870:
1869:{\displaystyle m<i}
1844:
1817:
1790:
1719:
1675:
1655:
1581:
1511:
1484:
1452:
1425:
1405:
1385:
1324:
1304:
1284:
1264:
1237:
1217:
1181:
1117:
1097:
1039:
1019:
990:
970:
865:
835:
834:{\displaystyle O(|V|)}
789:
743:
714:
713:{\displaystyle O(|E|)}
675:
645:
615:
549:
538:
160:
148:
146:Maze-solving algorithm
137:
69:"Breadth-first search"
2928:Minimum spanning tree
2262:Leiserson, Charles E.
1924:Ford–Fulkerson method
1871:
1845:
1843:{\displaystyle v_{j}}
1818:
1816:{\displaystyle v_{m}}
1791:
1720:
1676:
1656:
1582:
1512:
1510:{\displaystyle v_{i}}
1485:
1453:
1451:{\displaystyle v_{1}}
1426:
1406:
1386:
1325:
1305:
1285:
1265:
1263:{\displaystyle v_{i}}
1238:
1218:
1182:
1118:
1098:
1040:
1020:
991:
971:
866:
836:
790:
744:
715:
676:
646:
616:
544:
532:
522:cities starting from
209:In contrast, (plain)
154:
143:
135:
2913:Shortest path faster
2821:Breadth-first search
2816:Bidirectional search
2762:traversal algorithms
2606:Breadth-first search
1939:Construction of the
1854:
1827:
1800:
1729:
1685:
1665:
1591:
1521:
1494:
1462:
1435:
1415:
1395:
1337:
1314:
1294:
1274:
1247:
1227:
1191:
1127:
1107:
1049:
1029:
1018:{\displaystyle N(v)}
1000:
980:
942:
922:the input may be an
873:graph representation
845:
806:
802:can be expressed as
753:
742:{\displaystyle O(1)}
724:
685:
655:
625:
570:
566:can be expressed as
506:. You can see how a
419:13
325:as explored 4
242:connected components
164:Breadth-first search
54:improve this article
18:Breadth first search
2848:Iterative deepening
2696:Topological sorting
2626:Dynamic programming
2136:2008adm..book.....S
864:{\displaystyle |V|}
674:{\displaystyle |E|}
644:{\displaystyle |V|}
483:Note that the word
2843:Depth-first search
2714:List of algorithms
2621:Divide and conquer
2616:Depth-first search
2611:Brute-force search
2525:Binary search tree
2238:11011110.github.io
1968:Depth-first search
1926:for computing the
1912:depth-first search
1902:between two nodes
1894:Cheney's algorithm
1890:garbage collection
1866:
1840:
1813:
1786:
1715:
1671:
1651:
1577:
1507:
1480:
1448:
1421:
1411:. The enumeration
1401:
1381:
1320:
1300:
1280:
1260:
1233:
1213:
1177:
1113:
1093:
1035:
1015:
986:
966:
861:
831:
785:
739:
710:
671:
641:
611:
550:
539:
533:An example map of
508:breadth first tree
504:breadth first tree
449:First In First Out
437:depth-first search
291:: Goal state. The
231:state space search
211:depth-first search
193:For example, in a
161:
149:
138:
2986:Search algorithms
2968:
2967:
2865:Jump point search
2806:Best-first search
2722:
2721:
2520:Associative array
2431:978-0-201-89683-1
2266:Rivest, Ronald L.
2258:Cormen, Thomas H.
2211:978-81-203-4007-7
2153:978-1-84800-069-8
1404:{\displaystyle V}
1303:{\displaystyle i}
1283:{\displaystyle v}
1270:is a neighbor of
1236:{\displaystyle i}
1116:{\displaystyle V}
1038:{\displaystyle v}
989:{\displaystyle n}
976:be a graph with
720:may vary between
223:undirected graphs
130:
129:
122:
104:
16:(Redirected from
2993:
2981:Graph algorithms
2749:
2742:
2735:
2726:
2691:String-searching
2490:
2483:
2476:
2467:
2445:
2444:
2443:
2434:, archived from
2409:
2408:
2380:
2364:
2358:
2357:
2339:
2333:
2330:
2324:
2323:
2296:
2290:
2289:
2254:
2248:
2247:
2245:
2244:
2230:
2224:
2223:
2195:
2189:
2188:
2164:
2158:
2157:
2120:
2114:
2112:
2105:Moore, Edward F.
2101:
2095:
2093:
2080:
2074:
2073:
2071:
2070:
2055:
2049:
2048:
2045:10.7916/D8HQ46X1
2028:
2022:
2021:
2013:
2007:
2004:
1947:pattern matcher.
1941:failure function
1875:
1873:
1872:
1867:
1849:
1847:
1846:
1841:
1839:
1838:
1822:
1820:
1819:
1814:
1812:
1811:
1795:
1793:
1792:
1787:
1782:
1781:
1760:
1759:
1741:
1740:
1724:
1722:
1721:
1716:
1680:
1678:
1677:
1672:
1660:
1658:
1657:
1652:
1641:
1640:
1636:
1635:
1611:
1610:
1586:
1584:
1583:
1578:
1573:
1572:
1548:
1547:
1516:
1514:
1513:
1508:
1506:
1505:
1489:
1487:
1486:
1481:
1457:
1455:
1454:
1449:
1447:
1446:
1430:
1428:
1427:
1422:
1410:
1408:
1407:
1402:
1390:
1388:
1387:
1382:
1377:
1376:
1358:
1357:
1329:
1327:
1326:
1321:
1309:
1307:
1306:
1301:
1289:
1287:
1286:
1281:
1269:
1267:
1266:
1261:
1259:
1258:
1242:
1240:
1239:
1234:
1222:
1220:
1219:
1214:
1203:
1202:
1186:
1184:
1183:
1178:
1173:
1172:
1154:
1153:
1122:
1120:
1119:
1114:
1102:
1100:
1099:
1094:
1089:
1088:
1070:
1069:
1044:
1042:
1041:
1036:
1024:
1022:
1021:
1016:
995:
993:
992:
987:
975:
973:
972:
967:
916:adjacency matrix
900:branching factor
897:
893:
882:
870:
868:
867:
862:
860:
852:
840:
838:
837:
832:
827:
819:
800:space complexity
794:
792:
791:
786:
781:
780:
775:
766:
748:
746:
745:
740:
719:
717:
716:
711:
706:
698:
680:
678:
677:
672:
670:
662:
650:
648:
647:
642:
640:
632:
620:
618:
617:
612:
607:
599:
591:
583:
535:Southern Germany
465:
415:.parent :=
396:10
298:
285:
281:
274:
174:for searching a
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
3001:
3000:
2996:
2995:
2994:
2992:
2991:
2990:
2971:
2970:
2969:
2964:
2955:
2922:
2879:
2763:
2753:
2723:
2718:
2700:
2631:Graph traversal
2584:
2508:Data structures
2503:
2497:Data structures
2494:
2453:
2448:
2441:
2439:
2432:
2417:
2413:
2412:
2397:
2366:
2365:
2361:
2354:
2346:. p. 144.
2341:
2340:
2336:
2331:
2327:
2320:
2300:Russell, Stuart
2298:
2297:
2293:
2286:
2270:Stein, Clifford
2256:
2255:
2251:
2242:
2240:
2232:
2231:
2227:
2212:
2197:
2196:
2192:
2166:
2165:
2161:
2154:
2122:
2121:
2117:
2103:
2102:
2098:
2082:
2081:
2077:
2068:
2066:
2057:
2056:
2052:
2030:
2029:
2025:
2015:
2014:
2010:
2005:
2001:
1996:
1978:Level structure
1964:
1882:
1852:
1851:
1830:
1825:
1824:
1803:
1798:
1797:
1773:
1751:
1732:
1727:
1726:
1683:
1682:
1663:
1662:
1621:
1602:
1594:
1589:
1588:
1558:
1539:
1519:
1518:
1497:
1492:
1491:
1460:
1459:
1438:
1433:
1432:
1413:
1412:
1393:
1392:
1368:
1349:
1335:
1334:
1312:
1311:
1310:exists, and be
1292:
1291:
1272:
1271:
1250:
1245:
1244:
1225:
1224:
1194:
1189:
1188:
1164:
1145:
1125:
1124:
1105:
1104:
1080:
1061:
1047:
1046:
1027:
1026:
998:
997:
978:
977:
940:
939:
933:
908:
895:
884:
880:
843:
842:
804:
803:
770:
751:
750:
722:
721:
683:
682:
653:
652:
623:
622:
568:
567:
564:time complexity
560:
555:
516:
463:
451:) instead of a
433:
428:
388:.adjacentEdges(
363:8
296:
283:
279:
277:starting vertex
272:
266:
254:Edward F. Moore
227:directed graphs
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
2999:
2997:
2989:
2988:
2983:
2973:
2972:
2966:
2965:
2960:
2957:
2956:
2954:
2953:
2951:Reverse-delete
2948:
2943:
2938:
2932:
2930:
2924:
2923:
2921:
2920:
2915:
2910:
2905:
2903:Floyd–Warshall
2900:
2895:
2889:
2887:
2881:
2880:
2878:
2877:
2872:
2867:
2862:
2857:
2852:
2851:
2850:
2840:
2835:
2834:
2833:
2828:
2818:
2813:
2808:
2803:
2802:
2801:
2796:
2791:
2779:
2773:
2771:
2765:
2764:
2754:
2752:
2751:
2744:
2737:
2729:
2720:
2719:
2717:
2716:
2711:
2705:
2702:
2701:
2699:
2698:
2693:
2688:
2683:
2678:
2673:
2668:
2663:
2658:
2653:
2648:
2643:
2638:
2633:
2628:
2623:
2618:
2613:
2608:
2603:
2598:
2592:
2590:
2586:
2585:
2583:
2582:
2577:
2572:
2567:
2562:
2557:
2552:
2547:
2542:
2537:
2532:
2527:
2522:
2517:
2511:
2509:
2505:
2504:
2495:
2493:
2492:
2485:
2478:
2470:
2464:
2463:
2452:
2451:External links
2449:
2447:
2446:
2430:
2414:
2411:
2410:
2395:
2371:. p. 17.
2359:
2353:978-1453792995
2352:
2334:
2325:
2319:978-0137903955
2318:
2291:
2284:
2249:
2225:
2210:
2190:
2171:(3): 346–365.
2159:
2152:
2124:Skiena, Steven
2115:
2096:
2089:Der PlankalkĂĽl
2075:
2050:
2039:(27): 99–100.
2023:
2008:
1998:
1997:
1995:
1992:
1991:
1990:
1985:
1980:
1975:
1970:
1963:
1960:
1959:
1958:
1955:
1948:
1937:
1934:
1921:
1920:mesh numbering
1915:
1896:
1881:
1878:
1865:
1862:
1859:
1837:
1833:
1810:
1806:
1785:
1780:
1776:
1772:
1769:
1766:
1763:
1758:
1754:
1750:
1747:
1744:
1739:
1735:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1670:
1650:
1647:
1644:
1639:
1634:
1631:
1628:
1624:
1620:
1617:
1614:
1609:
1605:
1601:
1597:
1576:
1571:
1568:
1565:
1561:
1557:
1554:
1551:
1546:
1542:
1538:
1535:
1532:
1529:
1526:
1517:is the vertex
1504:
1500:
1479:
1476:
1473:
1470:
1467:
1458:) if, for all
1445:
1441:
1420:
1400:
1380:
1375:
1371:
1367:
1364:
1361:
1356:
1352:
1348:
1345:
1342:
1319:
1299:
1279:
1257:
1253:
1232:
1212:
1209:
1206:
1201:
1197:
1176:
1171:
1167:
1163:
1160:
1157:
1152:
1148:
1144:
1141:
1138:
1135:
1132:
1112:
1092:
1087:
1083:
1079:
1076:
1073:
1068:
1064:
1060:
1057:
1054:
1034:
1014:
1011:
1008:
1005:
985:
965:
962:
959:
956:
953:
950:
947:
932:
929:
912:adjacency list
907:
904:
859:
855:
851:
830:
826:
822:
818:
814:
811:
784:
779:
774:
769:
765:
761:
758:
738:
735:
732:
729:
709:
705:
701:
697:
693:
690:
669:
665:
661:
639:
635:
631:
610:
606:
602:
598:
594:
590:
586:
582:
578:
575:
559:
556:
554:
551:
515:
512:
460:
459:
456:
432:
429:
300:
265:
262:
201:may build the
128:
127:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2998:
2987:
2984:
2982:
2979:
2978:
2976:
2963:
2958:
2952:
2949:
2947:
2944:
2942:
2939:
2937:
2934:
2933:
2931:
2929:
2925:
2919:
2916:
2914:
2911:
2909:
2906:
2904:
2901:
2899:
2896:
2894:
2891:
2890:
2888:
2886:
2885:Shortest path
2882:
2876:
2873:
2871:
2868:
2866:
2863:
2861:
2860:Fringe search
2858:
2856:
2853:
2849:
2846:
2845:
2844:
2841:
2839:
2836:
2832:
2829:
2827:
2826:Lexicographic
2824:
2823:
2822:
2819:
2817:
2814:
2812:
2809:
2807:
2804:
2800:
2797:
2795:
2792:
2790:
2787:
2786:
2785:
2784:
2780:
2778:
2775:
2774:
2772:
2770:
2766:
2761:
2757:
2750:
2745:
2743:
2738:
2736:
2731:
2730:
2727:
2715:
2712:
2710:
2707:
2706:
2703:
2697:
2694:
2692:
2689:
2687:
2684:
2682:
2679:
2677:
2674:
2672:
2669:
2667:
2664:
2662:
2659:
2657:
2654:
2652:
2649:
2647:
2646:Hash function
2644:
2642:
2639:
2637:
2634:
2632:
2629:
2627:
2624:
2622:
2619:
2617:
2614:
2612:
2609:
2607:
2604:
2602:
2601:Binary search
2599:
2597:
2594:
2593:
2591:
2587:
2581:
2578:
2576:
2573:
2571:
2568:
2566:
2563:
2561:
2558:
2556:
2553:
2551:
2548:
2546:
2543:
2541:
2538:
2536:
2533:
2531:
2528:
2526:
2523:
2521:
2518:
2516:
2513:
2512:
2510:
2506:
2502:
2498:
2491:
2486:
2484:
2479:
2477:
2472:
2471:
2468:
2462:
2458:
2455:
2454:
2450:
2438:on 2008-09-04
2437:
2433:
2427:
2423:
2422:
2416:
2415:
2406:
2402:
2398:
2396:9781450357999
2392:
2388:
2384:
2379:
2374:
2370:
2363:
2360:
2355:
2349:
2345:
2338:
2335:
2329:
2326:
2321:
2315:
2311:
2310:
2305:
2304:Norvig, Peter
2301:
2295:
2292:
2287:
2285:0-262-03293-7
2281:
2277:
2276:
2271:
2267:
2263:
2259:
2253:
2250:
2239:
2235:
2229:
2226:
2221:
2217:
2213:
2207:
2203:
2202:
2194:
2191:
2186:
2182:
2178:
2174:
2170:
2163:
2160:
2155:
2149:
2145:
2141:
2137:
2133:
2129:
2125:
2119:
2116:
2110:
2106:
2100:
2097:
2091:
2090:
2085:
2079:
2076:
2065:on 2015-03-26
2064:
2060:
2054:
2051:
2046:
2042:
2038:
2034:
2027:
2024:
2019:
2012:
2009:
2003:
2000:
1993:
1989:
1986:
1984:
1981:
1979:
1976:
1974:
1971:
1969:
1966:
1965:
1961:
1956:
1953:
1949:
1946:
1942:
1938:
1935:
1933:
1929:
1925:
1922:
1919:
1916:
1913:
1909:
1905:
1901:
1900:shortest path
1897:
1895:
1891:
1887:
1886:
1885:
1879:
1877:
1863:
1860:
1857:
1835:
1831:
1808:
1804:
1778:
1774:
1767:
1756:
1752:
1745:
1742:
1737:
1733:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1668:
1645:
1632:
1629:
1626:
1622:
1618:
1615:
1612:
1607:
1603:
1595:
1569:
1566:
1563:
1559:
1555:
1552:
1549:
1544:
1540:
1530:
1527:
1524:
1502:
1498:
1477:
1474:
1471:
1468:
1465:
1443:
1439:
1418:
1398:
1373:
1369:
1365:
1362:
1359:
1354:
1350:
1343:
1340:
1331:
1297:
1277:
1255:
1251:
1230:
1223:be the least
1207:
1199:
1195:
1169:
1165:
1161:
1158:
1155:
1150:
1146:
1136:
1133:
1130:
1110:
1085:
1081:
1077:
1074:
1071:
1066:
1062:
1055:
1052:
1032:
1009:
1003:
983:
960:
957:
954:
948:
945:
936:
930:
928:
925:
921:
917:
913:
905:
903:
901:
891:
887:
876:
874:
853:
820:
809:
801:
796:
777:
767:
756:
733:
727:
699:
688:
663:
633:
600:
592:
584:
573:
565:
557:
552:
548:
543:
536:
531:
527:
525:
521:
513:
511:
509:
505:
500:
497:
492:
490:
486:
481:
478:
476:
471:
469:
457:
454:
450:
446:
442:
441:
440:
438:
430:
426:
422:
418:
414:
410:
406:
402:
399:
395:
391:
387:
384:
381:
377:
373:
369:
366:
362:
358:
355:
351:
347:
343:
340:is not empty
339:
336:
332:
328:
324:
320:
316:
312:
308:
304:
299:
294:
290:
286:
278:
270:
263:
261:
259:
255:
251:
247:
243:
238:
236:
232:
228:
224:
219:
216:
212:
207:
204:
200:
196:
195:chess endgame
191:
189:
185:
181:
177:
173:
169:
165:
158:
153:
147:
142:
134:
124:
121:
113:
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: –
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
2893:Bellman–Ford
2820:
2782:
2671:Root-finding
2605:
2596:Backtracking
2560:Segment tree
2530:Fenwick tree
2440:, retrieved
2436:the original
2420:
2368:
2362:
2343:
2337:
2328:
2307:
2294:
2274:
2252:
2241:. Retrieved
2237:
2228:
2200:
2193:
2168:
2162:
2127:
2118:
2108:
2099:
2088:
2084:Zuse, Konrad
2078:
2067:. Retrieved
2063:the original
2053:
2036:
2026:
2020:. MIT Press.
2017:
2011:
2002:
1945:Aho-Corasick
1940:
1932:flow network
1928:maximum flow
1907:
1903:
1898:Finding the
1883:
1880:Applications
1332:
1290:, if such a
937:
934:
931:BFS ordering
909:
906:Completeness
889:
885:
877:
797:
561:
523:
517:
507:
503:
501:
495:
493:
488:
484:
482:
479:
474:
472:
461:
434:
431:More details
424:
420:
416:
412:
408:
404:
400:
397:
393:
389:
385:
382:
379:
375:
371:
367:
364:
360:
359:is the goal
356:
353:
349:
345:
341:
337:
334:
330:
326:
322:
318:
314:
310:
306:
302:
292:
288:
287:
276:
268:
267:
258:wire routing
239:
220:
208:
199:chess engine
192:
167:
163:
162:
155:Top part of
116:
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
2811:Beam search
2777:α–β pruning
2550:Linked list
1330:otherwise.
374:edges from
370:9
344:6
317:2 let
246:Konrad Zuse
157:Tic-tac-toe
2975:Categories
2898:Dijkstra's
2686:Sweep line
2661:Randomized
2589:Algorithms
2540:Hash table
2501:algorithms
2442:2008-02-09
2378:1805.05208
2243:2020-06-10
2220:1006880283
2069:2015-03-15
1994:References
1850:such that
1587:such that
1243:such that
443:it uses a
333:) 5
271:: A graph
264:Pseudocode
250:PlankalkĂĽl
110:April 2012
80:newspapers
2941:Kruskal's
2936:BorĹŻvka's
2908:Johnson's
2681:Streaming
2666:Recursion
2461:Pat Morin
2306:(2003) .
1765:∖
1743:∈
1710:≤
1692:≤
1669:σ
1630:−
1616:…
1596:ν
1567:−
1553:…
1534:∖
1528:∈
1475:≤
1419:σ
1363:…
1341:σ
1318:∞
1200:σ
1196:ν
1159:…
1140:∖
1134:∈
1075:…
1053:σ
547:Frankfurt
524:Frankfurt
423:.enqueue(
348: :=
329:.enqueue(
303:procedure
203:game tree
180:tree root
172:algorithm
159:game tree
2831:Parallel
2405:44126609
2185:40700386
2086:(1972),
1962:See also
1950:Testing
1888:Copying
898:is the "
841:, where
553:Analysis
170:) is an
2676:Sorting
2651:Minimax
2132:Bibcode
1943:of the
514:Example
372:for all
144:BFS on
94:scholar
2946:Prim's
2769:Search
2656:Online
2641:Greedy
2570:String
2428:
2403:
2393:
2350:
2316:
2282:
2218:
2208:
2183:
2150:
1187:, let
1123:, for
1045:. Let
520:German
496:parent
489:vertex
365:return
293:parent
289:Output
275:and a
96:
89:
82:
75:
67:
2918:Yen's
2756:Graph
2565:Stack
2555:Queue
2535:Graph
2515:Array
2401:S2CID
2373:arXiv
2181:S2CID
1930:in a
1725:with
466:is a
453:stack
445:queue
335:while
269:Input
188:queue
184:depth
101:JSTOR
87:books
2875:SSS*
2799:SMA*
2794:LPA*
2789:IDA*
2760:tree
2758:and
2636:Fold
2580:Trie
2575:Tree
2545:Heap
2499:and
2426:ISBN
2391:ISBN
2348:ISBN
2314:ISBN
2280:ISBN
2216:OCLC
2206:ISBN
2148:ISBN
1906:and
1861:<
1704:<
1698:<
1469:<
1333:Let
938:Let
749:and
562:The
494:The
485:node
473:The
468:tree
405:then
361:then
331:root
323:root
311:root
305:BFS(
297:root
280:root
225:and
197:, a
176:tree
73:news
2383:doi
2173:doi
2140:doi
2041:doi
1823:of
462:If
378:to
301:1
282:of
233:in
168:BFS
56:by
2977::
2855:D*
2838:B*
2783:A*
2459:,
2399:.
2389:.
2381:.
2302:;
2268:;
2264:;
2260:;
2236:.
2214:.
2204:.
2179:.
2146:.
2138:.
2035:.
1892:,
1876:.
1490:,
914:,
526::
491:.
427:)
398:if
394:do
392:)
383:in
354:if
342:do
315:is
313:)
309:,
2748:e
2741:t
2734:v
2489:e
2482:t
2475:v
2407:.
2385::
2375::
2356:.
2322:.
2288:.
2246:.
2222:.
2187:.
2175::
2156:.
2142::
2134::
2072:.
2047:.
2043::
1954:.
1914:)
1908:v
1904:u
1864:i
1858:m
1836:j
1832:v
1809:m
1805:v
1784:)
1779:j
1775:v
1771:(
1768:N
1762:)
1757:k
1753:v
1749:(
1746:N
1738:i
1734:v
1713:n
1707:k
1701:j
1695:i
1689:1
1649:)
1646:w
1643:(
1638:)
1633:1
1627:i
1623:v
1619:,
1613:,
1608:1
1604:v
1600:(
1575:}
1570:1
1564:i
1560:v
1556:,
1550:,
1545:1
1541:v
1537:{
1531:V
1525:w
1503:i
1499:v
1478:n
1472:i
1466:1
1444:1
1440:v
1399:V
1379:)
1374:n
1370:v
1366:,
1360:,
1355:1
1351:v
1347:(
1344:=
1298:i
1278:v
1256:i
1252:v
1231:i
1211:)
1208:v
1205:(
1175:}
1170:m
1166:v
1162:,
1156:,
1151:1
1147:v
1143:{
1137:V
1131:v
1111:V
1091:)
1086:m
1082:v
1078:,
1072:,
1067:1
1063:v
1059:(
1056:=
1033:v
1013:)
1010:v
1007:(
1004:N
984:n
964:)
961:E
958:,
955:V
952:(
949:=
946:G
896:b
892:)
890:b
888:(
886:O
881:d
858:|
854:V
850:|
829:)
825:|
821:V
817:|
813:(
810:O
783:)
778:2
773:|
768:V
764:|
760:(
757:O
737:)
734:1
731:(
728:O
708:)
704:|
700:E
696:|
692:(
689:O
668:|
664:E
660:|
638:|
634:V
630:|
609:)
605:|
601:E
597:|
593:+
589:|
585:V
581:|
577:(
574:O
475:Q
464:G
447:(
425:w
421:Q
417:v
413:w
409:w
401:w
390:v
386:G
380:w
376:v
368:v
357:v
350:Q
346:v
338:Q
327:Q
319:Q
307:G
284:G
273:G
166:(
123:)
117:(
112:)
108:(
98:·
91:·
84:·
77:·
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
