Learning Objectives
 What is a Graph?
 What are some real world applications of Graphs?
 What are two ways to represent a Graph?
 What is a vertex and what is an edge?
 What is an origin and what is a terminus or destination?
 Can a vertex be connected to itself by an edge?
 What is the degree of a vertex?
 What does it mean to be an adjacent vertex?
 How is a directed Graph different from an undirected Graph?
 What is a path?
 What is a cycle?
 What is a parallel edge?
 What is a DAG?
 What is Tree?
 How would you represent the Graph ADT as a data structure?
Announcements Midterm 2 next class
 Trees, Binary Trees, BSTs
 Hash Tables
 Heaps
 Return Quiz 6 today
 Project Report 3 and Peer Evaluation 1 due
 No more labs  work on your course project!
 Women in Computer Science Club meeting tomorrow!
 1:002:00pm in ATC 202
 San Jose Public Library representative
 Teach basic coding skills to elementary and middle school students using curriculum from Google CS First
 Also: premeeting at 12:30 about attending Women in Tech conference this weekend
Review Questions With a partner, trace the below heap algorithms:
 Trace each step of the buildMaxHeap operation (diagram and array) on the following:
A = [4, 9, 7, 18, 2, 3]
 Trace heapInsert on the below Max Heap and the value 35. Show diagram and array at each step below:
A = [21, 11, 13, 2, 9]
 Trace heapSort on the following heap. Show diagram and array at each step below:
A = [100, 90, 80, 70]
 What is the BigO runtime of heap sort?
 Why is it more efficient to call build heap than it is to call heap insert onebyone to insert n elements into a heap?
Introduction to Graphs
 Today we are going to learn about the Graph ADT
 These graphs are not the same as the graphs that you learned about in Algebra and Calculus.
 Instead, there is a whole field of study known as Graph Theory which deals with the pairwise relationship between objects.
 In other words, we will be looking at the connected pairs of objects to see how these objects relate to each other.
Applications of Graph Theory  Modeling transportation networks, such as highways and flight paths.
 Representing relationships between components in electronic circuits
 Computer networks: LAN, Internet, Web
 Representing dependency of tables in databases
 We will watch a video about one Graph application at the end of class.
Graph Definition  We can define a graph as a set (or collection) of vertices (the nexus points) and edges (the lines connecting the vertices together). G= {V,E}
image source
 For example, take a look at the following graph:
Image source.  Using set theory, we can define this Graph like so:
V(G) = { 1, 2, 3, 4, 5, 6, 7}
E(G) = {15, 17, 57, 45, 46, 67, 27, 26, 23, 34}
 V(G) is called the vertex set. It is an unordered list of all the vertices in the Graph.
 E(G) is called the edge set. It is an unordered list of all the edges in the Graph.
 These two components are what define the graph.
 There are two other ways to define graphs, not involving sets
 We will learn about one of these at the end of class today.
Vertices  A vertex (plural vertices) or node is the fundamental unit of which graphs are formed.
 At its most basic, a graph can be defined as a single vertex with no edges.
 The below is considered a valid graph (no it's not an M&M), although no edges are present:
 In addition, vertices also have a degree. The degree of a vertex is the number of edges that are coming from it (incident upon it).
 The degree of the above vertex is 0.
 What is the degree of vertex 6 above?
 Below is an image of a graph which is labeled with the degrees of each vertex:
Image source.
Edges
 An edge is defined by the vertices between it, as a pair (u, v).
 u and v are both vertices in the graph, with the edge lying between them.
 The vertex u is called the origin, the vertex that the edge is coming from.
 The vertex v is called the destination or terminus, the vertex that the edge is coming to.
 The above is an example of a directed edge
 A directed edge is a pair of ordered vertices.
 In other words, u is always the origin and v is always the destination.
 When we draw a directed edge, we represent it with an arrow. The arrow is coming from the origin and pointing to the destination vertex.
 Below is an example of an undirected edge.
 Note that there is no arrow connecting the two.
 An undirected edge is an unordered pair of vertices (u,v), where either u or v could be the origin.
Directed and Undirected Graphs
 Graphs themselves can be directed or undirected.
 Directed graph: all edges are directed.
 The following is an example of a directed graph:
Image source.  Undirected graph: all edges are undirected.
Image source.
Adjacency  When an edge connects two vertices, the vertices are said to be adjacent to each other.
 Any edge that connects two adjacent vertices is said to be incident on those vertices.
 Two edges are said to be adjacent if they share a common vertex.
Review
With a partner answer the following questions: In the undirected graph above, which vertices are adjacent?
 Give two examples of adjacent edges.
Self Loops and Parallel Edges
 A self loop occurs when a vertex is adjacent to itself.
 For example, vertex 4 in the graph below contains a self loop:
Image source.  Parallel edges occur when two vertices are adjacent to each other  twice. In other words, there is a loop from one vertex to another.
 Parallel edges can be seen in the graph below between vertices 1 and 8 and also between vertices 6 and 8.
 Can you also spot the self loops?
Connected and Disconnected Graphs  Look at the following image below. Does it meet our definition of a graph?
Image source  It turns out the answer is yes.
 The above is called a disconnected graph.
 A disconnected graph is one in which there is no simple path to all the vertices in the graph.
 We can define a path as any route through a graph from vertex to vertex along edges, where no vertex along this route is repeated.
 For example, there are two paths from vertex b to vertex a above: bcda and ba.
 However, there is no path from g to a or from h to d. Thus, our graph above is disconnected.
 A connected graph is one in which there is a path to every vertex in the graph.
 For example, the below graph is connected:
 Notice that there is a path from every vertex to every vertex in the above graph.
 A directed graph is called weakly connected if replacing all of its directed edges with undirected edges produces a connected (undirected) graph.
 For example, the below graph is weakly connected:
image source
 If a graph is disconnected, it is considered to be composed of connected components.
 For example, the below graph contains 2 connected components:
Cyclic and Acyclic Graphs  A cyclic graph is one which contains a cycle.
 A cycle consists of a sequence of vertices starting and ending at the same vertex, with each two consecutive vertices in the sequence adjacent to each other in the graph.
 Inside a cycle, there should be no repetition of vertices, except the first vertex, which is also the last vertex.
 In the below graph, HDGH is a cycle.
 Can you see any others?
 In a directed graph, a cycle must follow the edges from origin to destination vertex.
 For example, the following graph contains the cycle BCEDB:
Image source.  However, the below graph is considered to be acyclic, meaning that it contains no cycles.
Image source.
Directed Acyclic Graphs (DAGs)  A directed acyclic graph, a.k.a. a DAG, is a special type of graph.
 Among other applications, DAGs are useful in scheduling, when there are a collection of tasks that must be ordered into a sequence, but are subject to
constraints that certain tasks must be performed earlier than others.
 Given the images below, which one is a DAG and which one is not?
Image source.
Trees Revisited  A tree is a graph that is both connected and acyclic.
 Below is an example of a tree.
Image source.  In graph theory, we usually consider all trees to be undirected. However, computer science, unlike applied math, allows for trees with directed edges, thus complicating our definition.
 A directed tree is a directed graph which would be a tree if the directions on the edges were ignored.
Review Activity With a partner, decide whether the following Graphs are:  connected or disconnected
 cyclic or acyclic
 directed or undirected
Graph A: Image source.
Graph B: Image source. Graph C:
Graph D:
Image source.
Applications of Graph TheoryWriting a Graph Data Structure  Let's start to think programmatically about how we will represent a Graph as a data structure.
 As we know, a Graph is simply a set of vertices and edges.
 The vertices can be written as a vertex set and the edges as an edge set.
 We saw an example an example of a vertex and edge set at the beginning of class.
Vertex and Edge Sets for Graph G:
V(G) = { 1, 2, 3, 4, 5, 6, 7}
E(G) = {15, 17, 57, 45, 46, 67, 27, 26, 23, 34}
Adjacency Lists
 In addition to using sets, there is another way to represent a Graph using what are called adjacency lists.
 An adjacency list representation of a graph is a collection of unordered lists, one for each vertex in the graph.
 Each list contains the set of adjacent vertices to that vertex.
 For example, I could represent the above Graph G using an adjacency list like so:
1: 5, 7
2: 3, 6, 7
3: 2, 4, 6
4: 3, 5, 6
5: 1, 4, 7
6: 2, 3, 4, 7
7: 1, 2, 5, 6
Group Activity With a partner, write out the adjacency list for the following Graphs:  How is the adjacency list different when the Graph is directed vs undirected?
Graph G1:
Image source.
Graph G2:
Adjacency Lists and the Graph Data Structure
 Using the adjacency list representation of a Graph makes it easy to represent a Graph in code.
 We can use an array (or vector) of linked lists.
 Each index of the array represents one vertex in our Graph.
 The array at this location represents the adjacency list for that Graph.
 We can see this representation as the depiction below:
Image source.Wrap Up  With your partner, answer the questions from today's learning objectives.
~See You Next Class!~
