Graphs & Traversal

An adjacency matrix reserves a cell for every pair of vertices, so its size depends only on V, never on the edge count. An adjacency list stores one entry per vertex plus one per actual edge, so it grows with E.

Each open cell is a node; an edge joins two cells one step apart, up, down, left or right. No edge list exists anywhere: a direction array plus a bounds-and-blocked check produces a cell's neighbors on demand.

After k passes over all edges, Bellman-Ford holds the best route that uses at most k edges. When no negative cycle exists, a best route never repeats a vertex, so it spans at most V-1 edges.

Dijkstra computes the minimum total travel time from one source to every reachable intersection - cheapest total weight, not fewest road segments. Vertices are finalized in non-decreasing distance order, so once one is popped its distance never changes.

Floyd-Warshall computes the shortest-path distance between every ordered pair of vertices in a single run, not from one source. It costs O(V^3) time through three nested loops and O(V^2) space for the distance matrix.

A graph is bipartite if its vertices split into two sides with every edge crossing between them. Two-coloring tests it: color a start vertex, force each neighbour the opposite color, and fail if an edge ever joins same-colored vertices.

A strongly connected component is a maximal set of vertices in which every vertex can reach every other by following edge directions. Ignoring direction only proves the vertices hang together somehow; a one-way edge destroys mutual reachability without disconnecting anything.

A recalculation order must place every cell after the cells it reads. Inside a cycle, each cell would have to be computed before itself, which is impossible. So such an order exists only when the reference graph is acyclic.

BFS expands nodes strictly in order of hop count, so the first time it reaches a node it has used the fewest possible hops. The guarantee holds only while every edge costs the same; unequal edge costs break it.

Graphs can contain cycles and several paths to the same vertex, so an unguarded depth-first search revisits vertices and may recurse forever. Marking a vertex the moment it is discovered makes every vertex expand exactly once, giving O(V+E).

On a sparse graph both cost about O(E log V), and Kruskal's is the simpler fit: sort the edges, reject the cycle-closing ones cheaply. Prim's wins on dense graphs, where its scan-based form runs in O(V^2).

A matrix answers in O(1) by direct indexing. An adjacency list costs O(deg(u)) because you scan u's neighbor sequence. An unindexed edge list costs O(E), since every record may have to be checked.

Moves are reversible, so an implicit state graph has cycles and paths reconverge; with no visited set the search re-expands states forever. The key must be a canonical encoding of the whole state, never the path used to reach it.

A further improvement means some cheaper walk uses V or more edges. A walk that long must repeat a vertex, and the loop it encloses can only reduce the total if its own weight is negative.

Each vertex is extracted from the min-heap once at O(log V), giving V log V. Each edge triggers at most one priority update, also O(log V), giving E log V. The two terms sum to O((V + E) log V).

Yes, provided no cycle has negative total weight. The recurrence never finalises a vertex early, so a cheap route found late still improves an entry. With a negative cycle no shortest path exists and the output is meaningless.

Nothing in the loop looks for cycles. Nodes on a cycle never reach in-degree zero, so they are never enqueued; the queue empties early and returns a short, valid-looking list. Compare its length to the node count.

Mark on enqueue. If nodes are only marked when removed, the same node can be pushed once per incoming edge, so the frontier swells toward the edge count and nodes get expanded repeatedly. Answers stay right; cost does not.

A visited mark only says a vertex was seen before; a cycle needs to know it is still on the current search path. Three colours separate unseen, in-progress and finished, and only an edge into an in-progress vertex proves a cycle.

That the edge's two endpoints already sat in one component, so the edge closes a cycle — a second path between them already exists. Union-find therefore detects cycles in an undirected graph in a single streaming pass over the edges.

Attaching blindly can build one long chain: a million sequential merges produce a path a million links deep, so every lookup walks O(n). Hanging the smaller tree under the larger caps height at O(log n).

The finality invariant breaks: Dijkstra assumes an extracted vertex's distance can never improve, which holds only because remaining edges add non-negative amounts. One negative edge lets a cheaper route appear after a vertex is settled, and the wrong value propagates.

A parent entry stores only the element x was attached to, not its group. Each set is a tree, so the group's identity is the root reached by following parent links until an element points at itself.

Every spanning tree must cross that partition somewhere, and swapping a heavier crossing edge for the cheapest one leaves a lighter tree. So the cheapest crossing edge belongs to some minimum spanning tree, and taking it never rules out optimality.

No. The graph is defined by a move rule, not by stored data: a node is a whole board arrangement, an edge is one legal tile slide. A search generates moves on demand and touches only the arrangements it actually reaches.

The heuristic must be admissible: it may never overestimate the true remaining cost to the goal. A* orders its frontier by cost-so-far plus heuristic, and admissibility is what stops it finalizing the goal before a cheaper route surfaces.

The k loop is outermost because each pass must finish adding waypoint k for every pair before k+1 begins. That preserves the invariant that D[i][j] holds the best cost using waypoints up to k; reordering leaves distances too large.

No. Triangle-free is necessary but not sufficient: a ring of five vertices holds no triangle yet cannot be two-colored. The exact characterization is that a graph is bipartite if and only if it contains no cycle of odd length.

Because bipartiteness is a whole-graph property checked per component. A sweep seeded at one vertex reaches only that component, so an odd cycle in an unvisited component is never examined. Restart the coloring from every still-uncolored vertex.