minte9
LearnRemember





Click to Flip Card

Graphs 

What is a graph?
How can we implement a graph?
How are nodes called in graph's jargon?
What are edges?

Graphs

A graphs is a data structure specialized in relationships. 
 
friends = {
    'Alice': ['Bob', 'Diana', 'Fred'],
    'Bob': ['Alice', 'Cynthia', 'Diana'],
    'Cynthia': ['Bob'],
    'Diana': ['Alice', 'Bob', 'Fred'],
    'Elise': ['Fred'],
    'Fred': ['Alice', 'Diana', 'Elise'],
}

print(friends['Alice'])

# ['Bob', 'Diana', 'Fred']

Directed Graphs

Relationships are not always mutual. 
 
followees = {
    'Alice': ['Bob', 'Diana'],
    'Bob': ['Cynthia'],
    'Cynthia': ['Bob'],
}

assert 'Bob' in followees['Alice']
assert 'Alice' not in followees['Bob']

Object Oriented

We can implement an undirected graph using an object oriented approach. 
 
class Vertex:
    def __init__(self, name):
        self.value = name
        self.adjacent_vertices = []

    def add_adjacent(self, vertex):
        self.adjacent_vertices.append(vertex)

        # if the friendship is mutual (undirected graph), 
        # we automatically add self vertix
        if self not in vertex.adjacent_vertices:
            vertex.adjacent_vertices.append(self)

a = Vertex('Alice')
b = Vertex('Bob')
c = Vertex('Cynthia')

a.add_adjacent(b); a.add_adjacent(c)
b.add_adjacent(c)
c.add_adjacent(b)

print('Alice vertices:', [x.value for x in a.adjacent_vertices])
print('Bob vertices:', [x.value for x in b.adjacent_vertices])

"""
    Alice vertices: ['Bob', 'Cynthia']
    Bob vertices: ['Alice', 'Cynthia']
"""

Weighted Graphs

This type of graph adds additional information to the edges of the graph. 
 
class WeightedVertex:
    def __init__(self, value):
        self.value = value
        self.adjacent_vertices = {}

    def add_adjacent(self, vertex, price):
        self.adjacent_vertices[vertex.value] = price

d = WeightedVertex('Dallas')
t = WeightedVertex('Toronto')

d.add_adjacent(t, 138)
t.add_adjacent(d, 216)

print('Dallas =>', d.adjacent_vertices)
print('Toronto =>', t.adjacent_vertices)

"""
    Dallas => {'Toronto': 138}
    Toronto => {'Dallas': 216}
"""



  Last update: 223 days ago