Graph

Description

Graphs are a useful model of connections.
Jani Issakainen
Mind Map by Jani Issakainen, updated more than 1 year ago
Jani Issakainen
Created by Jani Issakainen almost 8 years ago
37
0

Resource summary

Graph
  1. Spanning tree

    Annotations:

    • Whole, Acyclic subgraph. Includes all the nodes in the graph.
    1. Minimum spanning tree
      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. 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. Union-Find
            1. find

              Annotations:

              • find(x) find grandparent of x return
              1. 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. make-set

                  Annotations:

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

                Annotations:

                • Optimized Relax calls. (Every Edge relaxed once)

                Attachments:

                1. Bellman-Ford

                  Annotations:

                  • Not optimized Relax calls. Max V-1 times Relax calls per edge. V-1 times      for every Edge            relax(edge) 
                2. All
                  1. Floyd-Warshall
                3. Unweighted graphs
                  1. Path finding. path[]
                    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
                      1. Depth-first-search

                        Annotations:

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

                      Annotations:

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

                      Similar

                      Computing Hardware - CPU and Memory
                      ollietablet123
                      SFDC App Builder 2
                      Parker Webb-Mitchell
                      Data Types
                      Jacob Sedore
                      Intake7 BIM L1
                      Stanley Chia
                      Software Processes
                      Nurul Aiman Abdu
                      Design Patterns
                      Erica Solum
                      CCNA Answers – CCNA Exam
                      Abdul Demir
                      Abstraction
                      Shannon Anderson-Rush
                      Spyware
                      Sam2
                      HTTPS explained with Carrier Pigeons
                      Shannon Anderson-Rush
                      Data Analytics
                      anelvr