Skip to main content

17. Basics of Graphs

  • A graph is a set of nodes, or vertices, connected by edges
  • Graphs can be used to represent; networks, flow charts etc
  • Directed - Edges have direction
  • Undirected - Edges don't have direction. Can be represented as directed graphs where for each edge there is a corresponding edge
  • Weighted - Edges have weights
  • Unweighted -
  • Cycle - Path from a vertex to itself
  • Acyclic - If it does not have cycles

Implementation of graph​

  • Several approaches, but most common options are:
    • Static indexed data structure "Adjacency Matrix"
    • Dynamic data structure "Adjacency Lists"

Adjacency Matrix​

  • Store node in an array - each node is associated with an integer (array index)
  • Represent information about the edges using a 2d array where array[i][j] == 1
  • For weighted graphs, place weights in the matrix

Disadvantages​

  • Sparse graphs with few edges for number that are possible result in many zero entries in adjacency matrix
    • Wastes space and makes many algorithms less efficient
  • Also, if the number of nodes in the graph may change, matrix representation is too inflexible

Adjacency List​

  • For every vertex, keep a list of adjacent vertices
  • Keep a list of vertices, or keep vertices in a Map as keys and lists of adjacent vertices as values

Spanning Tree​

  • Input: Connected, undirected graph
  • Output: A tree which connects all vertices in the graph using only the edges present in the graph

Minimum Spanning Tree​

  • Input: Connected, undirected, weighted graph
  • Output: A spanning tree.
    • Connects all vertices in the graph using only the edges present in the graph
    • Minimum is the sense that the sum of weights of the edges in the smallest possible for any spanning tree

...