HomeConceptsComputer ScienceAlgorithms and Search

Computer Science · Algorithms and Search

Frontier and Visited State on Graphs

Simulation loading

Open Model Lab is preparing the live lab, controls, and graph surface for this concept.

Wrap-up

What you learned

Recommended next: Open concept testCheck whether the core ideas are ready without leaving this concept.
Read next: Sorting and Algorithmic Trade-offsCompare graph-traversal bookkeeping with visible list work

Key takeaway

Frontier means discovered and waiting to be expanded.
Visited means the node's neighbors have already been checked.
Repeat edges become safe skips only when the visited set is tracked honestly.

Common misconception

Frontier and visited are not two names for the same set; they mark different stages of graph-search work.

A frontier node has already been discovered, but its neighbors may not have been checked yet.

Keep frontier and visited separate when cycles appear

Keep this idea moving

Open the next concept, route, or track only when you want the current model to widen into a larger branch.

Compare graph-traversal bookkeeping with visible list workAlgorithms and Search

Sorting and Algorithmic Trade-offs

Watch sorting as visible work on a live list so input order, comparisons, and writes stay concrete instead of collapsing into one final answer.

Return to the ordered-search case after the graph branchAlgorithms and Search

Binary Search / Halving the Search Space

Keep an ordered list, the low-mid-high markers, and the shrinking interval visible together so binary search feels visual instead of procedural.

Next in Branch-first searchAlgorithms and Search

Depth-First Search and Backtracking Paths

Keep the stack frontier, current depth, and branch order visible together so depth-first search feels like disciplined backtracking instead of random wandering.

Stay with this concept

Review, test, or free-play here when you want one more same-concept pass.

Recommended nextOpen concept testCheck whether the core ideas are ready without leaving this concept.

More practice optionsReview on the bench · Worked examples

Practice optionReview on the benchReplay the guided setup with the key controls and graphs in sight.
Practice optionWorked examplesCompare against solved walkthroughs after you try the setup yourself.
Practice optionFree play on the benchExperiment freely with the live controls before moving to another concept.

Reference and support

Use these calmer sections when you want a fuller explanation, examples, or accessibility support after the guided flow.

Return here when you want the slower reference pass.

Open reference and support

Equation snapshotSearch bookkeeping · Repeat-skip countShow 2 equations

Keep the update rule and repeat-skip count close to the graph state.

Search bookkeeping
$V_{n e x t} = V \cup {u}, F_{n e x t} = F \cup N_{n e w} (u)$
Expanding the current node adds it to visited, while only newly discovered neighbors join the waiting frontier.
Repeat-skip count
$R = C - D$
Counts neighbor checks that point to already handled work instead of producing a new discovery.

Why it behaves this way

Explanation

On a graph with cycles, frontier and visited state answer different questions. The frontier shows discovered nodes still waiting to be expanded. The visited state shows nodes whose neighborhoods have already been checked.

That separation turns a loop from a trap into a bookkeeping event. When an edge points back to a visited node, the search records a repeat skip instead of reopening that node, while the remaining frontier keeps the run moving forward.

Key ideas

01Frontier means discovered and waiting, not finished.

02Visited means expanded already, so an edge back to that node becomes a repeat skip instead of new work.

03Cycles stay manageable when the current node, waiting frontier, and finished visited set stay visually separate.

Worked examples

Open examples when you want to see the same idea walked through step by step.

Frozen walkthrough

Step through the frozen example

Frozen walkthrough

Use the bridge-cycle graph to name what is waiting, what is finished, and what should happen when an edge points backward.

Supporter unlocks saved study tools, exact-state sharing, and the richer review surfaces that support this guided flow.

View plans

Frozen valuesUsing frozen parameters

On the bridge-cycle graph, how can you tell whether a node belongs in the frontier, the visited set, or neither?

G

Graph layout

Bridge cycle

F

Traversal mode

claimed but waiting

V

Target node

already expanded

1. Find the waiting work

A node belongs in the frontier after it has been discovered from an edge, but before the search has checked all of its own neighbors.

2. Mark finished expansions

A node belongs in visited only after its neighborhood has been used, so future edges back to it should not create new frontier work.

3. Read the repeat edge

When the bridge-cycle graph points back to visited work, count that edge as a repeat skip and leave the still-waiting frontier in place.

Frontier-versus-visited rule

Frontier = discovered and waiting; visited = expanded and safe to skip when seen again.

The moment a backward edge appears, this distinction explains why the traversal keeps progressing instead of reopening the cycle.

Quick test

Loading saved test state.

Accessibility

Open the text-first descriptions when you need the simulation and graph translated into words.

The simulation shows one labeled graph. The current node, frontier nodes, and visited nodes are highlighted differently so you can tell what is being processed now, what is waiting next, and what is already expanded.

A readout card reports the traversal mode, current node, frontier size, visited count, and target, while a cue panel shows the frontier order and the current node's neighbor list.

Graph summary

One graph compares visited count with frontier size, a second tracks current depth against deepest reached depth, and a third compares new discoveries with repeat skips.

Together they show why cyclic graph traversal needs frontier and visited state to play different roles.

Bench tools and share links

Keep stable concept links and exact-state sharing tucked away until you actually need to relaunch or share the bench.

Try this setup

Jump to a named bench state or copy the one you are looking at now. Shared links reopen the same controls, graph, overlays, and compare context.

Current bench

Bridge cycle BFS preset

This bench is currently showing one of the concept's authored presets.

Open default bench

Featured setups

Bridge cycle BFS

Use a cyclic graph where you can see that nodes waiting in the frontier are not the same as nodes already fully expanded.

Bridge cycle DFS

Run the same cyclic graph in DFS so you can compare the same bookkeeping under a branch-first search.

Saved setups

Saved setups are a Supporter study tool. Stable concept links still work for everyone.

Checking saved setup access

Open Model Lab is resolving whether this bench can save locally, sync to an account, or open Supporter-only compare tools.

Copy current setup

Exact-state sharing is part of Supporter. Stable concept and section links still stay available.

Stable links

Progress and next steps

Keep progress signals, starter-track handoffs, and review prompts available without letting them compete with the live lesson flow.

Progress

Loading progress

Loading saved concept progress for this browser or synced account before showing completion status.

Starter track

Step 6 of 6

Algorithms and Search Foundations

Frontier and Visited State on Graphs appears later in this track, so it is cleaner to start from the beginning first.

Previous step: Depth-First Search and Backtracking Paths

Start from track beginning