Trees and graphs

Data Structures and Algorithms in Python

Miriam Antona

Software engineer

Trees - definition

A picture of a tree with nodes.

  • Node-based data structures
  • Each node can have links to more than one node.
Data Structures and Algorithms in Python

Trees - terminology

A picture of a tree with nodes. The root node is colored yellow.

Data Structures and Algorithms in Python

Trees - terminology

A picture of a tree with nodes. The root node is colored yellow. A parent node is colored orange.

Data Structures and Algorithms in Python

Trees - terminology

A picture of a tree with nodes. The root node is colored yellow. A parent node is colored orange and his children are colored green.

Data Structures and Algorithms in Python

Trees - terminology

A picture of a tree with nodes.

Data Structures and Algorithms in Python

Trees - terminology

A picture of a tree with nodes with its different levels.

Data Structures and Algorithms in Python

Trees - binary tree

Graphical representation of a binary tree.

  • Each node has:
    • zero children
    • one children
    • two children
Data Structures and Algorithms in Python

Trees - binary tree implementation

class TreeNode:

  def __init__(self, data, left=None, right=None):
    self.data = data
    self.left_child = left
    self.right_child = right

A picture of a tree with nodes.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Data Structures and Algorithms in Python

Trees - real uses

  • Storing hierarchical relationships
    • File system of a computer
    • Structure of an HTML document

  • Chess: possible moves of the rival

  • Searching and sorting algorithms

Data Structures and Algorithms in Python

Graphs

A picture of a graph with nodes.

  • Set of:
    • nodes/vertices
    • links/edges
  • Trees are a type of graph
Data Structures and Algorithms in Python

Graphs - types

  • Directed graphs:
    • Specific direction

Picture of a directed graph.

Data Structures and Algorithms in Python

Graphs - types

  • Undirected graphs:
    • Edges have no direction
    • The relationship is mutual

Picture of an undirected graph.

Data Structures and Algorithms in Python

Graphs - types

  • Weighted graphs:
    • numeric values associated with the edges
    • can be either directed or undirected

A picture of an undirected graph with the names of some cities and the distance between them.

Data Structures and Algorithms in Python

Graphs vs. trees

Trees

  • Cannot have cycles
  • All nodes must be connected

A picture of a tree with nodes.

Graphs

  • Can have cycles
  • There can be unconnected nodes

A picture of a graph with nodes.

Data Structures and Algorithms in Python

Graphs vs. trees

Trees

  • Cannot have cycles
  • All nodes must be connected

A picture of a tree with nodes.

Graphs

  • Can have cycles
  • There can be unconnected nodes

A picture of a graph with nodes. There is a node that is not connected with the rest.

Data Structures and Algorithms in Python

Graphs - real world use-cases

  • User relationships in social networks
    • friendship
    • follows
    • likes
    • etc.
  • Locations and distances
    • optimize routes
  • Graph databases
  • Searching and sorting algorithms
Data Structures and Algorithms in Python

Graphs - implementation

class Graph:
  def__init(self):
    self.vertices = {}

  def add_vertex(self, vertex):
    self.vertices[vertex] = []

  def add_edge(self, source, target):    
    self.vertices[source].append(target)

Picture of a directed graph.

my_graph = Graph()
my_graph.add_vertex('David')
my_graph.add_vertex('Miriam')
my_graph.add_vertex('Martin')

my_graph.add_edge('David', 'Miriam')
my_graph.add_edge('David', 'Martin')
my_graph.add_edge('Miriam', 'Martin')

print(my_graph.vertices)

{
  'David' : ['Miriam','Martin'],
  'Miriam' : ['Martin'],
  'Martin' : []
}
Data Structures and Algorithms in Python

Let's practice!

Data Structures and Algorithms in Python

Preparing Video For Download...