Algorithms
  • Introduction
  • Algorithms
    • Insertion Sort
    • Shell Sort
    • Selection Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Dual Pivot QuickSort
    • Radix Exchange Sort
  • Data Structures
    • Basic Datastructures
      • Table or Array
      • List
      • Linked List
      • Stack
      • Queue
      • Deque
      • Dictionary
      • HashTables
    • Trees
      • Tree
      • Binary Search Tree
      • Heap
      • Red-Black Trees
      • Splay Trees
      • Randomized Search Trees
    • Dynamic Programming
      • Fibonacci
      • Knapsack
      • Optimal Binary Search Trees
      • Longest Common Sub sequence
    • External Data Structures
      • B-Trees
      • Variants
    • Multi-dimensional Data Structures
      • Point-Region Quadtree
      • Point-Quadtrees
    • Priority Queues
      • Binomial Queues
  • Graphs
    • Basics
    • Depth First Search
    • Applications of Depth First Search
    • Breadth First Search
    • Shortest Paths
    • Transitive Closure
    • Flow Networks
    • Matching
  • Strings
    • Data Structures for Strings
      • Tries
        • Binary Tries
        • Multiway Trie
        • Patricia Tries
      • Variable Length-code
        • Elias Code
        • Gamma Code
        • Fibonacci Code
      • Huffmancode
      • Ternary Search Tree
    • Searching in Strings
      • Prefix Function
      • Knuth-Morris-Pratt
      • Boyer-Moore
      • Monte-Carlo Algorithms
      • Karp-Rabin
      • Automatons
      • Shift-AND
    • Indexing Text
      • Suffix Trees
      • Suffix Arrays
      • Search Engines & Inverted Files
  • P and NP
    • Introduction
    • SAT and 3-SAT
    • Graph Problems
    • Problems with Collections
    • Networks
    • Data storage
  • Metaheuristics
    • Trajectory Methods
      • Local Search
      • Simulated Annealing
      • Tabu Search
    • Population Based
      • Ant Colony
      • Evolutionary Computation
  • Sources
Powered by GitBook
On this page

Was this helpful?

  1. Graphs

Basics

PreviousGraphsNextDepth First Search

Last updated 6 years ago

Was this helpful?

  • Abstract model

  • Exists of n nodes or vertices

  • Has a collection of m edges

  • The nodes represent objects with connections

  • Can have a direction.

  • The grade of a node is the amount of neighbors of that node.

  • For a graph with a direction, we have an ingrade, this is the amount of incoming neighbors. The same goes for the outgrade which is the amount of outgoing neighbours.

  • 2 Basic representations of graphs:

    • Neighbor matrix: takes a connection (i,j) and represents it on a square neighbormatrix. This value can be logical or can be the weight. The problem is that matrices take a lot of memory en the initialization takes Θ(n2)\Theta(n^2)Θ(n2) operations.

    • Neighbor lists: Mostly used when we do not have a lot of connections (m << n2n^2n2). In reality most graphs are like this. The neighbors of every node are saved in a neighbor list and the graph is represented by a table of n neighbor-lists.

These pictures show a normal graph, it's neighbor list and the neighbor matrix

Looping through a graph is different then looping through a tree, this because a graph has multiple pathways and we have to find a way to only go through each path once.