Graphs

• Graph


  A set of vertices or nodes connected by edges or arcs
• Edges


  • May be one-way or two-way in an undirected graph
  • All edges are bidirectional
• Directed graph or digraph


  A graph where the edges are all one-way
• The weights in the example represent distances between towns
• A human driver can find their way from one town to another by following a map, but a computer needs to represent the information about distances and connections in a structured, numerical representation
• Graph


  A data structure that represents a set of objects (called vertices or nodes) where some pairs of the objects are connected by links (called edges)
• Possible implementations of a graph

  • Adjacency matrix
  • Adjacency list
• Adjacency matrix


  • A two-dimensional array can be used to store information about a directed or undirected graph
  • Each of the rows and columns represents a node
  • A value stored in the cell at the intersection of row i, column j indicates that there is an edge connecting node i and node j
• In the case of an undirected graph, the adjacency matrix will be symmetric, with the same entry in (0) as in (1,0), for example
• An unweighted graph may be represented with 1s instead of weights, in the relevant cells
• Adjacency matrix


  • Very convenient to work with
  • Adding an edge is very simple
• Adjacency matrix


  • Sparse graph with many nodes but not many edges will leave most of the cells empty
  • The larger the graph, the more memory space will be wasted
  • Using a static two-dimensional array, it is harder to add or delete nodes
• Adjacency list


  • A more space-efficient way to implement a sparsely connected graph
  • A list of all the nodes is created, and each node points to a list of all the adjacent nodes to which it is directly linked
  • The adjacency list can be implemented as a list of dictionaries, with the key in each dictionary being the node and the value, the edge weight
• Breadth-first search


  A graph traversal algorithm that explores all the neighboring nodes at the present depth before moving on to the nodes at the next depth level
• Applications of graphs


  • Computer networks, with nodes representing computers and weighted edges representing the bandwidth between them
  • Roads between towns, with edge weights representing distances, rail fares or journey times
  • Tasks in a project, some of which have to be completed before others
  • Web pages and links (see Google's PageRank algorithm in Section 5)