Kodas

graph.go — karkasas

Sukurk graph.go. Karkasas kaip įprasta; kūnai tavo.

Ką verta pasižymėti:

c.Hit() skaičiuoja BRIAUNAS, ne viršūnes — kviečiamas ten, kur svarstai, ar eiti briauna toliau. Tai ir yra O(V + E) „E" dalis.
AddEdge privalo išmesti kilpas ir dublikatus. Pėdsakų generatorius pagamins ir vienų, ir kitų, o pasikartojanti briauna tyliai išpūs kiekvieną šios pamokos skaičių.
Degrees medianai naudok skaičiavimo rikiavimą (9 pamoka), ne palyginimų — laipsnių rėžis mažytis, tai kaip tik tas atvejis.

Kur klystama

BFS žymi seen DEDANT, DFS — IMANT. Tai atrodo kaip smulkmena ir nėra.

BFS: pažymėk viršūnę tą akimirką, kai ją dedi į eilę. Jei pažymėsi tik ją išimdamas, ta pati viršūnė pateks į eilę kelis kartus per skirtingus sluoksnius, ir prev[w] bus perrašytas ilgesniu keliu. Paieška vis tiek ras kelią — tiesiog nebe trumpiausią. Testas tai pagaus, bet pirmiausia tai turi pagauti tu.

DFS: čia atvirkščiai. Viršūnė gali teisėtai patekti į steką kelis kartus, kol jos eilė ateis, tad tikrinti reikia imant.

Ta pati eilutė, dvi skirtingos vietos, ir priežastis abiem atvejais ta pati: eilė lanko sluoksniais, stekas — ne.

Spąstai

DFS ir DFSRecursive grąžins skirtingus kelius, ir tai ne klaida.

Steko versija sudeda visus kaimynus ir tada ima paskutinį; rekursinė versija eina jais iš eilės nuo pirmo. Kaimynų aplankymo tvarka priešinga, tad pėdsakai skiriasi.

Abu keliai tikri, abu veda ten, kur reikia, ir nė vienas nėra trumpiausias. Testas TestTheTwoDFSVersionsDisagreeOnPaths reikalauja, kad jie skirtųsi — antra pratybų užduotis apie tai, kaip juos suderinti.

graph.go SUKURTI

Sukurk šį failą kataloge ./

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") }