Graphs
Daniel Archambault
CS-115: Graphs
1
Previously in CS-115
27
10
18 4 2 2
8
Heaps of keys budding in line because of their “priority”
33
CS-115: Graphs
2
Previously in CS-115
What is a priority queue?
CS-115: Graphs
3
Previously in CS-115
What is a priority queue? What is a heap?
CS-115: Graphs
3
Previously in CS-115
What is a priority queue?
What is a heap?
What is the heap preservation condition?
CS-115: Graphs
3
Previously in CS-115
What is a priority queue?
What is a heap?
What is the heap preservation condition? How can we implement a priority queue?
CS-115: Graphs
3
Previously in CS-115
What is a priority queue?
What is a heap?
What is the heap preservation condition?
How can we implement a priority queue?
Is there an implementation of a PQ in the Java API?
CS-115: Graphs
3
Previously in CS-115
Now it’s time to take a look at graphs (networks not charts)
Graphs
CS-115: Graphs
4
What is a graph?
A graph is an ADT that relates pairs of elements
Nodes in the graph are the elements
An edge exists between two elements if they share a relationship
Graphs provide a useful way to model data for many problems It is a generalisation of many of the ADTs we’ve talked about
CS-115: Graphs
5
Graphs in the Real World
Graphs are a common and important real-world data structure
Computer networks
Social networks
Biological networks
Software engineering
Railways and metro maps
They tend to model many real world phenomena Visualising them is my primary area of research
CS-115: Graphs
6
This is Facebook
Facebook, Twitter, and others are all graphs Models people and the connections between them
CS-115: Graphs
7
Dynamics of Social Networks
Graphs evolve over time
Tweets between accounts… Interactions between characters in a novel…
CS-115: Graphs
8
Biological Networks
Genes regulate other genes
Experimental conditions determine expression
CS-115: Graphs
9
Analysis of English Language
English language usage in Ireland on the internet Connections between blogs.
CS-115: Graphs
10
Recall: Linked List
Linked list have a single link to a single successor
tail
next element
next element
next element
head
null
Obj.
There is exactly one item before and one after
Obj.
Obj.
CS-115: Graphs
11
Recall: Trees
Trees have two, in the case of binary trees, children
33
10
18 4 2 2
8
There is exactly one item before and two after
trees can have more than two children as well (if not binary)
trees are often viewed as a graph subclass
27
CS-115: Graphs
12
Graph ADT
Graphs encode the relationship between entities
Nodes are not parents or children
Unlike trees, graphs can have cycles
For a graph of n nodes, they can have up to n2 connections one between every pair of nodes
CS-115: Graphs
13
Graph Definitions
a b
Nodes are the entities and edges the relationships aisanodeand(a,b)isanedge
The degree of a node is the number of edges it participates in ahasadegreeof4
bhasadegreeof1
An undirected graph has no directionality on the edges
CS-115: Graphs
14
Graph Definitions: Directed
Graphs can be directed where each edge has a direction
a
In this case, we have in-degree and out-degree
the in-degree of a is 3
the out-degree of a is 1
CS-115: Graphs
15
Graph Data Structure
There are a number of ways to implement graphs Two common options are:
Matrix
Linked structures
As with any data structure, both implementations have their advantages
CS-115: Graphs
16
Matrix implementation of a graph
In a matrix implementation of a graph, the edge list is a two dimensional array
public class Graph {
Node[] nodes; //list of n nodes (made by constructor)
Edge[][] matrix; //nxn matrix specified by constructor
…..
To see if an edge exists, look up the array element
What is an advantage/disadvantage of this data structure? Can we improve it with another data structure?
CS-115: Graphs
17
Linked structure of a graph
In a linked structure, within each node you list the elements it is connected to
public class Graph {
Node[] nodes;
….
}
public class Node {
Edge[] edgeList; //list of degree nodes
}
Edges are only contained in nodes
What is an advantage/disadvantage of this data structure? Can we improve it with another data structure?
CS-115: Graphs
18
Graph Structures
We have defined and seen two data structures that implement graphs
What are nodes and edges? What is degree?
What is an undirected graph?
CS-115: Graphs
19