u5 Flashcards Preview

m269 > u5 > Flashcards

Flashcards in u5 Deck (17)
Loading flashcards...

optimisation problem

one in which the task is to find the best possible solution


priority queue

each item has a priority and items are kept sorted with the highest priority item at the front.
•When a new item is added it is inserted at its correct position in the priority order.
•The priority of an item in the queue maybe changed, whereupon the queue will be reordered



A graph is a set of verticesor nodes, together with a set of edgesor arcs, each connecting one vertex to another. Edges may have weights.
•If V is the set of vertices in a graph, then |V| is the number of vertices.
•If E is the set of edges, then |E| is the number of edges.


digraph or directed graph

a graph in which each edge has a direction


complete graph

has an edge between every pair of vertices


sparse graph

few edges(vertices have few neighbours)


dense graph

has many edges (vertices have many neighbours).


general tree

an empty tree or a root with 0 or more subtrees


Depth-first search

starts at a specified vertex and explores as far as possible along each branch before backtracking.
•Depth-first search is what happens automatically by recursively iterating over neighbours.
•Vertices are marked to avoid visiting them more than once.


Breadth-first search

starts at a specified vertex and explores the neighbour nodes first, before moving to the next level of neighbours.
•BFS can be implemented by keeping a “to do” list of vertices as a queue.


The minimum distance problem/shortest path

Find the shortest distance from a specified source vertex v to each of the other vertices.


Dijkstra’s algorithm

Solution to the shortest path
create a priority queue(with priority higher for smaller values)
set distance(v)to 0
set distance(w)to infinity for all other vertices w
add all vertices to the priority queuewith priority equal to their distance
ITERATEwhile the priority queueis not empty
remove u from the front of the queue
ITERATE over vertices wthat are neighbours of u
set new-distanceto distance(u)+ length of edge uw
IF new-distanceis less than distance(w)
set distance(w)to new-distance
change the priority of w in the priority queue to new-distance


Spanning trees

a subset of the graph’s edges that connect all the vertices, without including any closed circuits.
•It contains a minimal set of edges that connect up all the nodes.The number of edges in a spanning tree is |V| –1.


minimum spanning tree

a weighted graph is a spanning tree that minimises the sum of the weights along its edges.


Prim’s algorithm

a greedy solution to the problem of finding a MST
•Start from an arbitrary vertex.
•Keep vertices not already in the current tree in a priority queue.
•Keeptrack of the shortest edge that could connect a vertex to the current tree.
•Use the length of these edges to order the priority queue.
•At each step, add the vertex closest to the current tree to the tree


directed acyclic graph

a directed graph with no directed cycles.
•DAGs are useful for representing dependencies.


Topological sort

orders the vertices of a DAG so that, for every directed edge uv, ucomes before vin the ordering.
•Identify a vertex with no incoming edges and add it to the topological sort.
•Remove that vertex and all its outgoing edges from the graph.
•Repeat until all the vertices have been removed.
Rather than literally removing vertices and edges, a dictionary records how many edges come into each vertex.