Träd och grafer

Datastrukturer och algoritmer i Python

Miriam Antona

Software engineer

Träd – definition

En bild av ett träd med noder.

  • Nodbaserade datastrukturer
  • Varje nod kan ha länkar till mer än en nod.
Datastrukturer och algoritmer i Python

Träd – terminologi

En bild av ett träd med noder. Rotnoden är markerad i gult.

Datastrukturer och algoritmer i Python

Träd – terminologi

En bild av ett träd med noder. Rotnoden är markerad i gult. En föräldranod är markerad i orange.

Datastrukturer och algoritmer i Python

Träd – terminologi

En bild av ett träd med noder. Rotnoden är markerad i gult. En föräldranod är markerad i orange och dess barn är markerade i grönt.

Datastrukturer och algoritmer i Python

Träd – terminologi

En bild av ett träd med noder.

Datastrukturer och algoritmer i Python

Träd – terminologi

En bild av ett träd med noder och dess olika nivåer.

Datastrukturer och algoritmer i Python

Träd – binärt träd

Grafisk representation av ett binärt träd.

  • Varje nod har:
    • noll barn
    • ett barn
    • två barn
Datastrukturer och algoritmer i Python

Träd – implementering av binärt träd

class TreeNode:

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

En bild av ett träd med noder.

node1 = TreeNode("B")
node2 = TreeNode("C")
root_node = TreeNode("A", node1, node2)
Datastrukturer och algoritmer i Python

Träd – verkliga användningsområden

  • Lagra hierarkiska relationer
    • Filsystem på en dator
    • Struktur i ett HTML-dokument

  • Schack: möjliga drag för motståndaren

  • Sök- och sorteringsalgoritmer

Datastrukturer och algoritmer i Python

Grafer

En bild av en graf med noder.

  • Består av:
    • noder/hörn
    • länkar/kanter
  • Träd är en typ av graf
Datastrukturer och algoritmer i Python

Grafer – typer

  • Riktade grafer:
    • Specifik riktning

Bild av en riktad graf.

Datastrukturer och algoritmer i Python

Grafer – typer

  • Oriktade grafer:
    • Kanter saknar riktning
    • Relationen är ömsesidig

Bild av en oriktad graf.

Datastrukturer och algoritmer i Python

Grafer – typer

  • Viktade grafer:
    • numeriska värden kopplade till kanterna
    • kan vara riktade eller oriktade

En bild av en oriktad graf med namn på städer och avståndet mellan dem.

Datastrukturer och algoritmer i Python

Grafer vs. träd

Träd

  • Kan inte ha cykler
  • Alla noder måste vara sammankopplade

En bild av ett träd med noder.

Grafer

  • Kan ha cykler
  • Det kan finnas ej sammankopplade noder

En bild av en graf med noder.

Datastrukturer och algoritmer i Python

Grafer vs. träd

Träd

  • Kan inte ha cykler
  • Alla noder måste vara sammankopplade

En bild av ett träd med noder.

Grafer

  • Kan ha cykler
  • Det kan finnas ej sammankopplade noder

En bild av en graf med noder. En nod är inte sammankopplad med de övriga.

Datastrukturer och algoritmer i Python

Grafer – verkliga användningsområden

  • Användarrelationer i sociala nätverk
    • vänskap
    • följer
    • gillar
    • osv.
  • Platser och avstånd
    • optimera rutter
  • Grafdatabaser
  • Sök- och sorteringsalgoritmer
Datastrukturer och algoritmer i Python

Grafer – implementering

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)

Bild av en riktad graf.

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' : []
}
Datastrukturer och algoritmer i Python

Nu kör vi en övning!

Datastrukturer och algoritmer i Python

Preparing Video For Download...