Flashcards in u5 Deck (17)
one in which the task is to find the best possible solution
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
has an edge between every pair of vertices
few edges(vertices have few neighbours)
has many edges (vertices have many neighbours).
an empty tree or a root with 0 or more subtrees
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.
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.
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
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.
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.