 # Graph

Mind Map by , created almost 3 years ago

## Graphs are a useful model of connections. 7 0 0  Created by Jani Issakainen almost 3 years ago
GCSE Computer Science (AQA)
Think Python
2.1.3 Software
CHEMISTRY C1 3
AQA Biology 12.1 cellular organisation
Computer Systems
OCR gcse computer science
GCSE Computing: Hardware
computer systems and programming quiz
Computer Science
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&gt;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[]

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