Graphs

• Dynamic data structure:

  • changes in size at runtime
  • list
  • tree
• Static data structure:


  • can not change at run time
  • tuple
  • array
• Graph


  A graph is a mathematical structure that models the relationship between pairs of objects
• Graph theory

  the underlying mathematical principles behind the use of graphs
• Arc

  a join or relationship between two nodes - also known as an adge
• Vertex


  an object in a graph - also known as a node
• Weighted graph


  a graph that has data value labelled on each adge
• Undirected graph


  a graph where the relationship between verticies is two-way
• Directed graph


  a graph where the relationship between verticies is one-way
• Use of graphs:


  • Human networks
  • Transport Network
  • Internet and web
• Adjacency list

  a data structure that stores a list of nodes with their adjacent nodes
• Adjacency matrix

  a data structure set up as a two-dimnensional array or grid that shows whether there is an edge between each pair of nodes
• Difference between Adjacency list and matrix (storage):

  • An Adjacency list only stores data where there is an adjacency so needs less memory
  • An Adjacency matrix stores a value for every combnation of node adjacencies so requires more memory
• Differences between adjacency list and matric (Process):

  • In adjacency lists, the list has to be parsed to identify whether particular adjacencies exists increasing process time of data
  • In adjacency matrix, the adjacencies can be identifed more quickly as every combination is already stored
• Traversing


  means to visit every node within a graph
• Visiting

  this means to do something with a node meaning it could process the data or compare it to some searched value
• What is a tree?

  • a connected, undirected graph with no cycles
• What is a rooted tree?

  a tree in which one vertex has been designated as the root and every edge is directed away from the root
• what is a binary tree

   binary tree is a rooted tree in which each node has at most two children
• State three uses for trees?

  • Social networks on social media
  • Rail way networks such as the underground
  • Road networks
• What are the applications of a rooted tree?

  • Storing and managing file and folder structure
  • Storing or forming any form of hierarchial data that requires a parent node to have zero or one or more child nodes
• State three uses of binary trees?

  • Database applications where searching and sorting is required
  • Wireless networking and router tables
  • Huffman coding used for compression of files such as JPEG
• Explain a circumstance where adjacency listing is more appropriate to represent a graph rather than using an adjacency matrix?

  • When the graph is sparse and there are fewer edges between verticies
  • The prescence of specific edges do not need to be tested frequently
• Post-order

  • left
  • right
  • vist
• pre-order

  • visit
  • left
  • right
• in-order

  • left
  • visit
  • right