EntCSExplore. Visualise. Understand.

Everything on the site.

Big-O notationAlgorithms · Count the steps in real loops, then compare n, n log n, n² and 2ⁿ on a live chart.RecursionAlgorithms · Watch frames push and pop on the call stack for factorial and Fibonacci.BFS vs DFSAlgorithms · A queue against a stack: draw a graph and see which order each search visits it in.Sorting algorithmsAlgorithms · Seven sorts on the same input, with comparison, swap and write counts side by side.Binary searchAlgorithms · Halve the range, probe the middle, repeat: with lo, mid and hi drawn on the array.Sets, relations and functionsDiscrete maths · Shade any set expression on a Venn diagram and test a relation for its properties.Proof by inductionDiscrete maths · Four worked proofs revealed one step at a time, and a broken one to diagnose.CombinatoricsDiscrete maths · An exact nPr and nCr calculator, and a Pascal’s triangle that shows its own addition rule.Boolean algebraDiscrete maths · The laws, De Morgan, and normal forms, with a truth-table generator built in.Finite-state machinesTheory · Build a DFA in a table, see it drawn, and run strings through it one symbol at a time.Domain theoryTheory · Why recursion needs least fixed points, and how CPOs, Scott continuity and powerdomains supply them.Truth table generatorTools · Expression in, truth table out: with DNF, CNF, a minimal form and LaTeX.Graph traversal visualiserTools · Draw a graph, then animate BFS, DFS and Dijkstra with the frontier shown.Recursion tree visualiserTools · Paste a recursive function or a recurrence and see its call tree and call count.Gradient descentML maths · Drag the starting point, set the learning rate, and watch it converge or blow up.Vectors and embeddingsML maths · Bend the plane with a 2×2 matrix and measure how close toy word vectors are.Softmax and cross-entropyML maths · Edit the logits and watch the probabilities, the loss and the gradient update live.AttentionML maths · Q, K and V for three tokens, a live score heatmap, and the weighted sum of values.Formatting a CS paper in LaTeXLaTeX · Page limits, \documentclass, front matter, theorem environments and the bibliography.Camera-ready checklistLaTeX · Fonts embedded, PDF/A, copyright form, source bundle, and why final versions get rejected.LaTeX templatesLaTeX · Where the official classes live, plus a minimal article template you can copy.AlgorithmsSection · Step-through visualisations of sorting, searching, recursion, graph traversal and Big-O growth, each with pseudocode that highlights the line being run.Discrete mathsSection · Sets, relations and functions, proof by induction, counting, and Boolean algebra, explained with worked examples and small interactive checkers.TheorySection · Finite-state machines, automata and the mathematical semantics of programming languages, explained from first principles.ML mathsSection · Gradient descent, vectors and embeddings, softmax and cross-entropy, and attention, each with a formula, a worked numeric example and a live version.ToolsSection · A truth-table generator with CNF, DNF and LaTeX output, a graph-traversal visualiser for BFS, DFS and Dijkstra, and a recursion-tree visualiser.LaTeXSection · How to format a CS conference or workshop paper in LaTeX, a camera-ready checklist, and a minimal template you can adapt.
Algorithms

BFS vs DFS: breadth-first and depth-first search

Breadth-first search explores a graph in rings, nearest vertices first. Depth-first search follows one path as far as it can, then backs up. The only difference in the code is a queue versus a stack, but it changes what each search is good for.

Interactive: Graph-traversal visualiser (BFS and DFS on a drawable graph)Updated

Both algorithms answer the same basic question, “which vertices can I reach from here?”, and both take time proportional to the size of the graph. They visit vertices in very different orders, though, and that order is what makes BFS the tool for shortest paths in unweighted graphs and DFS the tool for cycles, orderings and structure.

Graphs in one paragraph

A graph is a set of vertices (also called nodes) joined by edges. Edges may be undirected (a road you can drive both ways) or directed (a one-way street, or “page A links to page B”). Programs usually store a graph as an adjacency list: for each vertex, the list of its neighbours. That takes space proportional to V+EV + E, the number of vertices plus the number of edges.

Try both on the same graph

Pick BFS or DFS and press play. Vertices turn amber when they are discovered and green when they are finished. The panel on the right shows the frontier: the queue for BFS, the call stack for DFS. Use “Add vertex” and “Add edge” to build your own graph; the run restarts whenever you change something.

Graph traversal visualiserDraw your own graph or start from a preset, then pick an algorithm and a start vertex.

Drag vertices to move them. Click a vertex or edge to edit it.
  • Current vertex
  • Discovered / in the frontier
  • Finished (settled)
  • Edge skipped
Edit the graph as text

One edge per line: A B 4 joins A and B with weight 4 (weight optional, default 1). A line with one name adds a lone vertex.

Pseudocode

    Frontier

    Visit order

    In this visualiser neighbours are always taken in alphabetical order, so every run is repeatable. Real programs use whatever order their adjacency lists happen to have, and the visit order changes with it. The set of reachable vertices does not.

    Breadth-first search: a queue

    BFS keeps a queue of discovered vertices waiting to be processed. It takes the vertex at the front, looks at its neighbours, and adds any it has not seen before to the back. Because the queue is first in, first out, every vertex at distance 1 from the start is processed before any vertex at distance 2, and so on: the search spreads out in layers.

    That layering is the key fact about BFS. The first time BFS discovers a vertex, it has found a path to it with the fewest possible edges. Recording each vertex’s parent as you discover it therefore gives a shortest-path tree, and you can recover the shortest route to any vertex by following parents back to the start.

    Worked example: BFS from A on the starting graph

    The graph has edges A–B, A–C, B–D, B–E, C–F, C–G, E–H and E–F.

    DequeueNew neighbours enqueuedQueue afterwards
    AB, CB C
    BD, EC D E
    CF, GD E F G
    DnoneE F G
    EH (F is already discovered)F G H
    F, G, Hnoneempty

    Visit order: A, B, C, D, E, F, G, H. A is at distance 0; B and C at 1; D, E, F and G at 2; H at 3.

    Depth-first search: a stack

    DFS dives. From the current vertex it moves to the first undiscovered neighbour and continues from there, only coming back when it reaches a vertex with nothing new around it. It is most naturally written recursively, with the call stack doing the remembering; an explicit stack works too.

    On the same graph DFS from A visits A, B, D, then backs up to B and goes to E, then F, then from F to C, from C to G, and finally back up to E for H: A, B, D, E, F, C, G, H. Notice that it reaches C through a long detour. DFS does not find shortest paths.

    What it does provide is structure. Each vertex has a moment it is discovered and a later moment it is finished, and those intervals nest like parentheses. That property, studied in Tarjan’s 1972 paper, is behind many classic linear-time algorithms:

    • Cycle detection. In a directed graph, meeting a vertex that is discovered but not yet finished means you have found a cycle.
    • Topological sorting. Listing vertices in reverse order of finishing time gives an order in which every edge points forwards, for example an order in which to build software modules or take prerequisite courses.
    • Connected and strongly connected components, bridges and articulation points.
    • Maze generation and solving, and backtracking search in general.

    BFS vs DFS at a glance

    Breadth-first searchDepth-first search
    FrontierQueue (first in, first out)Stack or recursion (last in, first out)
    OrderBy distance from the start, layer by layerAlong one path as deep as possible, then backtrack
    TimeO(V+E)O(V + E) with adjacency listsO(V+E)O(V + E) with adjacency lists
    Extra memoryProportional to the widest layerProportional to the longest path explored
    Shortest paths (unweighted)?YesNo
    Typical usesFewest hops, social-network “degrees of separation”, web crawling by distance, level-order traversalCycles, topological order, components, puzzles and backtracking

    Both run in O(V+E)O(V + E) time because each vertex is enqueued or entered once and each edge is examined a constant number of times (twice in an undirected graph, once from each end). With an adjacency matrix instead of lists, finding a vertex’s neighbours costs O(V)O(V), and both searches become O(V2)O(V^2).

    Pitfalls

    • Mark vertices when you discover them, not when you dequeue them. If BFS only marks a vertex once it leaves the queue, the same vertex can be enqueued many times, which wastes time and memory.
    • Deep recursion. Recursive DFS on a long path can overflow the call stack. For large graphs use an explicit stack.
    • Disconnected graphs. A single search only reaches one component. To cover everything, start a new search from each vertex that is still undiscovered.
    • Weighted edges. BFS counts edges, not distances. When edges have lengths, use Dijkstra’s algorithm, which is BFS with the queue replaced by a priority queue.
    Going further The full graph traversal visualiser adds Dijkstra’s shortest-path algorithm, weighted and directed presets, and a text editor for edge lists.

    References

    1. R. E. Tarjan, “Depth-first search and linear graph algorithms”, SIAM Journal on Computing 1(2), 1972. doi:10.1137/0201010
    2. E. F. Moore, “The shortest path through a maze”, Proceedings of the International Symposium on the Theory of Switching, Harvard University Press, 1959. An early description of breadth-first search.
    3. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022. Chapter 20 covers elementary graph algorithms.
    4. “Breadth-first search”, Wikipedia.