Prims start at a node --> add the cheapest connected edge
Prims (matrix)
Kruskals sort edges --> pick smallest that doesn't make cycle
Dijkstra's shortest path start node --> take shortest connected edge --> assign cumulative value to connected edge --> make start node --> start at node with smallest working value
Route inspection (Chinese postman)
finds shortest route in a network that traverses each edge once and returns to starting node
pair odd nodes --> find shortest paths between them --> repeat shortest edges
aim: make all vertices even with minimum extra distance
Travelling salesman problem
Nearest Neighbour
pick closest unvisited
Minimum spanning tree to find upper bound
Kruskal's or Prims --> double minimum connector (travel minimum spanning tree then retrace steps) --> find "shortcuts" (arcs not included)
Minimum spanning tree to find lower bound
start vertex (usually given in Q) --> remove vertex from network + all connections from vertex --> find minimum spanning tree on left over vertexes (Prim's/Kruskal's) --> add total weight of this reduced minimum spanning tree to the too smallest connections of the start vertex
Sorting algorithms
Bubble sort
compare neighbors moving up by one each time --> repeat if any have moved
Quick sort
Bin-packing algorithms:
first fit
take items in given order --> place item in first available bin starting with bin 1
first fit decreasing
sort items in descending order then first fit
full-bin
Special graphs
Eulerian graphs:
contains Eulerian circuit (all edges can be used and finishes on the same vertex)
identifying eulerian graphs:
all vertexes have even valency
Semi Eulerian graphs:
contains trail where every edge is used but does not finish on the same vertex
exactly 2 vertexes have odd valency