Graphs

Graphs represent a network, a collection of connected objects.

• Objects are called nodes or vertices
  • These can be airports, computers, people
• Connections are called edges or arcs
  • The connection could be friendships

Graph is a super useful abstraction for problem solving.

The geometry of graph does not matter, only the connections stay the same.

Directed vs Undirected

There are two categories:

• A directed edge
• An undirected edge

Abstraction

$G = (V,E)$ A graph, represented above, consists of a nonempty set $V$ of vertices and a collection of $E$ edges.

Symbols:

• $V = {A,B,C,D,E,F}$
• $E = [\{A,B\}, \{B,B\}, \{B,C\},\{B,E\},\{C,D\},\{C,D\},\{D,A\},\{D,E\}]$ represents undirected pairs
• $E=[(1,2)]$ represents directed pairs
• $n$ or $|V|$ represents the cardinality of that set, or the number of nodes
• $m$ or $|E|$ represents the number of edges in that set
• $n+m$ is the size of the input
• The minimum numder of edges for the entire graph to be connected is $m=n-1$

The Graph interface declaration makes V and E generics, which are placeholders for the datatype of what will be sorted in a vertex or edge.

• A Vertex and Edge will be Positions

E is not a set because you can have many edges between a pair of nodes. This is not common.

• A simple graph is one that doesn't have multiple edges/"self loops"

Representation

Adjacency Matrix

Using a 2D array, each row and column corresponds to a node.

• Put a 0 if there is no edge bewteen two ndoes, and put a 1 if there is an edge between two nodes.
  • Not necessarily a boolean array. It can be a 2D array of objects.
• Another name for a 2D array is a matrix, an abstraction in mathematics
  • Linear algebra is very important for dealing with matrix and machine learning

The space needed is O(n^2) Access is constant because it is an array access.

Adjacency List

A list of lists: each list corresponds to a vertex and contains a list of vertices adjacent to it.

v -> {u,w}
u -> {v,w}
w -> {v,u,z}
z -> {w}

Used for everythign we will be doing in this data structures class.

Incident List

A list of lists: each list corresponds to a vertex and it mapped to a list of edges (u,v) incident to that vertex.

• Gives all nodes adjacent to a vertex.

Space

The space requirement for adjacency/incidence list representation is O(N+M) - You need a list of vertices O(N) and each vertex has a list of its adjacent vertices. The size of the list is equal to the degree of that vertex. The total size is the sum of the degree of all vertices, which is 2M. - $m \in O(n)$ if the graph is sparse. Happens when closer to linear. Adjacency lists are preferred because they require constant space for every edge.
- $m \in O(n^2)$ if the graph is dense. Happens when closer to quadratic. Adjacency matrix is prefered.