Mapa mental
Decision 1
Contenido del mapa
Decision 1
Kruscals Algorithm
- 1. List edges - smallest to biggest
- 2. Add each edges until all points are visited-No cycles
- 3. Total all edges = minimum spanning tree
- 2. Add each edges until all points are visited-No cycles
- 1. List edges - smallest to biggest
Prims Algorithm
- 1. Given starting point
- 2. Go to next shortest edge connected to that point
- 3. Add next shortest edge that is connected to that edge or one you have already visited
- 4. Keep adding shortest edges - No cycles
- 5. Total all edges = minimum spanning tree
- 4. Keep adding shortest edges - No cycles
- 3. Add next shortest edge that is connected to that edge or one you have already visited
- 2. Go to next shortest edge connected to that point
- 1. Given starting point
Dijkstras Algorithm
- 1. But boxes next to all nodes
- 2. Given starting point to go to another point
- 3. Add up route from starting point, pick shortest
- 4. Add up more edges, cancel if shorter
- 5. Trace back to start by taking away to find route
- 4. Add up more edges, cancel if shorter
- 3. Add up route from starting point, pick shortest
- 2. Given starting point to go to another point
- 1. But boxes next to all nodes
Bipartite Graph
- 1. A B C D down one side 1 2 3 4 down the other
- 2. Match together from matrix
- 3. Initial matching- Dotted line
- 4. A-1 B-3 etc..
- 3. Initial matching- Dotted line
- 2. Match together from matrix
- 1. A B C D down one side 1 2 3 4 down the other
Chinese Postman
- 1. Add up all edges
- 2. Find odd nodes
- 3. Pair up odd nodes
- 4. Add up and find shortest distance
- 5. Add this distance to the total
- Draw extra lines travelled onto graph
- 5. Add this distance to the total
- 4. Add up and find shortest distance
- 3. Pair up odd nodes
- 2. Find odd nodes
- 1. Add up all edges
Travelling Salesman
- 1. Finding upper and lower bounds
- 2. Follow route and find Upper bound
- 3. Find lower bound by deleting one vertex and finding the minimum spanning tree
- 4. Add 2 lowest numbers to minimum spanning tree
- 5. LB<...<UB
- 4. Add 2 lowest numbers to minimum spanning tree
- 3. Find lower bound by deleting one vertex and finding the minimum spanning tree
- 2. Follow route and find Upper bound
- 1. Finding upper and lower bounds
Linear Programming
- 1. x is... y is... z is...
- 2. list constraints
- 3. Plot onto graph, cross out areas you dont need
- 4 identify feasible region
- 5. Draw objective line
- 4 identify feasible region
- 3. Plot onto graph, cross out areas you dont need
- 2. list constraints
- 1. x is... y is... z is...
Bubble Sort
- 1. Normally sort
- 2. Compare 1st 2 numbers
- 3. Compare next 2 numbers
- 4. Compare all numbers - end of first pass
- 3. Compare next 2 numbers
- 2. Compare 1st 2 numbers
- 1. Normally sort
Shell Sort
- 1. Subsets
- 2. Divide amount of numbers by 2
- 3. List ABC ABC ABC
- 4. Compare all A's then all B's
- 5. Divide by 2 again and do the same
- 4. Compare all A's then all B's
- 3. List ABC ABC ABC
- 2. Divide amount of numbers by 2
- 1. Subsets
Shuttle Sort
- 1.Compare 1st 2 numbers - end of first pass
- 2. Comare next to numbers, if there is a swap comapare numbers before too - end of 2nd pass
- 3. Continue until all numbers are in order
- 2. Comare next to numbers, if there is a swap comapare numbers before too - end of 2nd pass
- 1.Compare 1st 2 numbers - end of first pass
Quick Sort
- 1. Pick a pivot
- 2. everything smaller than pivot goes to the left, bigger goes to the right
- 3. Identify new pivot, repeat until numbers are in the right order
- 2. everything smaller than pivot goes to the left, bigger goes to the right
- 1. Pick a pivot
Información
- Descripción
- Mapa Mental sobre Decision 1, creado por hayet01.53 el 17/03/2014.
- Creado por
- hayet01.53 · mar 2014
- Actualizado
- 19 feb 2016
- Visitas
- 18
- Valoración
Más sobre Graph and Network Algorithms