Jani Issakainen
Mind Map by , created almost 3 years ago

Graphs are a useful model of connections.

7
0
0
Jani Issakainen
Created by Jani Issakainen almost 3 years ago
GCSE Computer Science (AQA)
Wolfie Ruth
Think Python
tsilvo2001
2.1.3 Software
Lavington ICT
CHEMISTRY C1 3
x_clairey_x
AQA Biology 12.1 cellular organisation
Charlotte Hewson
Computer Systems
lisawinkler10
OCR gcse computer science
Jodie Awthinre
GCSE Computing: Hardware
Yasmin F
computer systems and programming quiz
Molly Batch
Computer Science
jacobhuntergoddard
Graph
1 Spanning tree

Annotations:

  • Whole, Acyclic subgraph. Includes all the nodes in the graph.
1.1 Minimum spanning tree
1.1.1 Prim

Annotations:

  • Greedy. We want to be adding nodes that are the closest to the Tree (T) being constructed.(NOT A NODE LIKE DJIKSTRA). So we want in every turn add minDist[] EDGE, to the tree. Means we want to know dist[] and parent! (to what node is the distance) Initialise all dist[]=inf, parent[]=nil.Start with random node.dist[rNode] = 0, Go through adj. list, update dist and parent. Here's the trick. Although the heap contains nodes (key value is their distance), tree T contains edges. So T= T u ({n,v}).
1.1.2 Kruskal

Annotations:

  • Every node is it's own island. We connect them one by one, cheapest first. In the end, only one island remains. Remember, it's a tree we are building, so edges. for every edge we check wheter it connects to islands then we do it if it does. We take em from a heap.
1.1.2.1 Union-Find
1.1.2.1.1 find

Annotations:

  • find(x) find grandparent of x return
1.1.2.1.2 union

Annotations:

  • Union(y,z) if(y.h y.p=z else if z.h>y.h else if EQUAL y.p=z z.h ++
1.1.2.1.3 make-set

Annotations:

  • make-set(x) x.parent=x x.height = 0
2 Shortest path
2.1 Single-source
2.1.1 Dijkstra

Annotations:

  • Optimized Relax calls. (Every Edge relaxed once)

Attachments:

2.1.2 Bellman-Ford

Annotations:

  • Not optimized Relax calls. Max V-1 times Relax calls per edge. V-1 times      for every Edge            relax(edge) 
2.2 All
2.2.1 Floyd-Warshall
3 Unweighted graphs
3.1 Path finding. path[]
3.1.1 Breadth-first-search

Annotations:

  • Input: Graph and source Goal: all shortest paths known. Tools:  -queue, to store nodes in order -path array, path[u] tells the node leading to u. -distance array -visited boolean array,  or "added to que" array
3.1.2 Depth-first-search

Annotations:

  • Cycle detection. There is a cycle in a graph only if there is a backward edge in the algorithm.
4 Topological sort

Annotations:

  • for every directed edge   uv in the sorting, u comes before v. needs to be a directed acyclic graph

Media attachments