Graphs

• A graph is G = (V, E)
  • V is a set of vertices
  • E is a set of edges
  • V = {0, 1, 2, 3, 4, 5}
  • E = {(0, 1), (0, 4), (1, 2), (1, 4), (2, 3), (3, 4), (3, 5)}

Directed vs Undirected

• Undirected edges are unordered pairs
  • (0, 1) = (1, 0)
• Directed graphs are ordered pairs
  • (0, 1) != (1, 0)

Graph Sizes

• The size of the graph will be the number of vertices and edges
• We can have 0 edges, it will just be a graph of vertices
• Self edges can effect this number
  • (1, 1)
• Directed graphs will have self edges, undirected will not
  • in class anyways
• a graph is sparse if e <= vlgv
• a graph is dense if e = MAX-t, some small number t

Adjacency Matrix vs Adjacency List

• An adjacency Matrix is a 2D array that has a flag value that marks whether an edge is there
  • M[0][4] = 1, if there is an edge at (0, 4) between vertexes 0 and 4
  • Wastes space because edges that aren't there take up space
• An Adjacency List has an array of ArrayLists where each index is a vertex and each array list is a list of the edges on that vertex
  • Good for sparse graphs, doesn't waste memory