Flashcards in u5 Deck (17)

Loading flashcards...

1

## optimisation problem

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

2

## 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

3

## Graphs

###
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.

4

## digraph or directed graph

### a graph in which each edge has a direction

5

## complete graph

### has an edge between every pair of vertices

6

## sparse graph

### few edges(vertices have few neighbours)

7

## dense graph

### has many edges (vertices have many neighbours).

8

## general tree

### an empty tree or a root with 0 or more subtrees

9

## 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.

10

## 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.

11

## The minimum distance problem/shortest path

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

12

## 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

13

## 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.

14

## minimum spanning tree

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

15

## 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

16

## directed acyclic graph

###
a directed graph with no directed cycles.

•DAGs are useful for representing dependencies.

17