Graphs: BFS & DFS — Programuoki

Code

graph.go — the skeleton

Create graph.go. The usual skeleton; the bodies are yours.

Worth noting:

c.Hit() counts EDGES, not nodes — call it where you consider whether to follow an edge. That is the "E" in O(V + E).
AddEdge must reject self-loops and duplicates. The trail generator produces both, and a duplicated edge quietly inflates every number in this lesson.
Use a counting sort for Degrees' median (lesson 9), not a comparison sort — the degree range is tiny, which is exactly that case.

Where it goes wrong

BFS marks seen when PUTTING, DFS when TAKING. It looks like a detail and is not.

BFS: mark a node the moment you put it in the queue. Mark it only on the way out and the same node enters the queue several times across different layers, and prev[w] gets overwritten by a longer route. The search still finds a path — just no longer the shortest. The test will catch it, but you should catch it first.

DFS: the opposite. A node can legitimately be pushed several times before its turn comes, so the check belongs where you take.

The same line, two different places, and the reason is the same both times: a queue visits in layers and a stack does not.

Gotcha

DFS and DFSRecursive will return different paths, and that is not a bug.

The stack version pushes all the neighbours and then takes the last one; the recursive version walks them in order from the first. The neighbour visiting order is reversed, so the trails differ.

Both paths are real, both arrive, and neither is shortest. TestTheTwoDFSVersionsDisagreeOnPaths requires them to differ — drill 2 is about making them agree.

graph.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithms are in step 2; graph_test.go
// decides whether you got them right — and one of its checks is that DFS does
// NOT return shortest paths.
//
// Every EDGE you look at goes through c.Hit(). Not every node — every edge, at
// the point where you consider following it.

// Graph is the "readers also borrowed" network over your library: node i is
// items[i], and an edge joins two books borrowed one after the other.
//
// It is UNDIRECTED and UNWEIGHTED. Every edge is one hop, and one hop costs the
// same as every other. Lesson 15 is where that stops being true.
//
// The representation is an ADJACENCY LIST — one slice of neighbours per node.
// Step 7 measures it against the other option.
type Graph struct {
	adj   [][]int32
	edges int
}

func NewGraph(n int) *Graph { panic("not implemented") }

func (g *Graph) Nodes() int { panic("not implemented") }
func (g *Graph) Edges() int { panic("not implemented") }

// AddEdge links a and b in BOTH directions. It must ignore self-loops and
// duplicates — the trail generator produces both, and a duplicated edge would
// quietly inflate every count in this lesson.
func (g *Graph) AddEdge(a, b int32) { panic("not implemented") }

func (g *Graph) Neighbors(v int32) []int32 { panic("not implemented") }

// Degrees reports the mean, median and largest degree — the numbers that decide
// whether a list or a matrix is the right representation.
//
// The degree range is tiny, so the median wants a counting sort (lesson 9)
// rather than a comparison sort.
func (g *Graph) Degrees() (mean float64, median, max int) { panic("not implemented") }

// BFS finds the path with the FEWEST HOPS from `from` to `to`, using a QUEUE —
// lesson 4's structure, doing the work it was built for.
//
// Mark a node as seen when you PUT it in the queue, not when you take it out.
// Marking on the way out lets the same node enter the queue several times and
// the hop count stops being minimal.
func BFS(g *Graph, from, to int32, c *metrics.Counter) ([]int32, bool) {
	panic("not implemented")
}

// DFS finds A path from `from` to `to`, using a STACK. The only difference from
// BFS is which end of the collection the next node comes from.
//
// Here you must check `seen` when you TAKE, because a node can be pushed more
// than once before its turn arrives.
//
// It does NOT find the shortest path. Do not fix that — step 5 is about it, and
// the test requires it.
func DFS(g *Graph, from, to int32, c *metrics.Counter) ([]int32, bool) {
	panic("not implemented")
}

// DFSRecursive is the same algorithm with the call stack in place of the slice —
// lesson 5's point, now doing real work.
//
// It will not return the same paths as DFS, and that is not a bug. Step 6.
func DFSRecursive(g *Graph, from, to int32, c *metrics.Counter) ([]int32, bool) {
	panic("not implemented")
}

// Components counts the connected pieces and the size of the largest, using BFS
// from every node not yet reached. Every node is visited exactly once, so the
// whole thing is O(V + E) — not O(V) searches.
func (g *Graph) Components(c *metrics.Counter) (count int, largest int) {
	panic("not implemented")
}

// rebuild walks the prev[] chain backwards from `to` and reverses it. Both
// searches end with this, so write it once.
func rebuild(prev []int32, from, to int32) []int32 { panic("not implemented") }

// AdjMatrix is the other representation: one bit for every ORDERED PAIR of
// nodes, whether or not an edge exists. Step 7 measures what that costs.
//
// Pack it into []uint64 rather than []bool. A []bool would spend a whole byte
// on one bit and make the comparison unfair in your favour.
type AdjMatrix struct {
	n    int
	bits []uint64
}

func NewAdjMatrix(n int) *AdjMatrix        { panic("not implemented") }
func (m *AdjMatrix) Set(a, b int32)        { panic("not implemented") }
func (m *AdjMatrix) Has(a, b int32) bool   { panic("not implemented") }

// Bytes is the memory the matrix occupies; Cells is how many entries it has,
// against how many of them are real edges.
func (m *AdjMatrix) Bytes() int { panic("not implemented") }
func (m *AdjMatrix) Cells() int { panic("not implemented") }