程序代写代做 graph Java data structure Graphs

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