2.6 Graphs

What is a Graph?

Graphs are another important data structure that are incredibly versatile and can be used to represent a variety of things. Because of this, they can be used to solve lots of complex problems. They can represent networks such as paths through a city, telephone lines, social media networks, and more.

Graphs consist of vertices and edges that connect each node. A simple way to do this is to create nodes (like the ones we learned) and add neighbors to each one. Each node can store some information. For example, in a social media network like Facebook, each person can be represented by a node, and the node can contain information about the person, such as their name, gender, id etc. Nodes that are connected show that they are friends on Facebook.

(Image courtesy of geeksforgeeks.org)

Directed vs. Undirected

Graphs can also be directed. This means that connections between nodes go only one direction. For example, in Instagram, a node representing user A can be connected to a node representing user B to show that user A is following user B. These connections go only one direction because user A following user B doesn’t necessarily mean user B follows user A. Of course, user B can still follow user A, and then that specific connection between users becomes bidirectional.

(Image courtesy of towardsdatascience.com)

Implementations in Python

A simple way to represent graphs in Python is by having a dictionary of sets. The key is the node, and the value is a set containing connections to other nodes.


# simple graph
my_graph = {
    "A": {"B", "C", "E"},
    "B": {"A", "D"},
    "C": {"A"},
    "D": {"B", "E"},
    "E": {"D", "A"},
}

The following graph drawn out would look like the picture below.

The code below is another way of representing graphs in Python by creating a class to provide useful methods.

Python:


# graph data structure
class Node:
    def __init__(self, val: str, neighbors: set = None):
        self.val = val
        if neighbors:
            self.neighbors = neighbors
        else:
            self.neighbors = set()

    def addNeighbor(self, n):
        self.neighbors.add(n)


class Graph:
    def __init__(self, connections: list = None):
        self.nodes = {}
        if connections:
            self.parse(connections)

    def createNode(self, values: list):
        for value in values:
            self.nodes[value] = Node(value)

    def createEdge(self, n1: str, n2: str):
        self.nodes[n1].addNeighbor(self.nodes[n2])
        self.nodes[n2].addNeighbor(self.nodes[n1])

    def parse(self, connections: list):
        for connection in connections:
            if connection[0] not in self.nodes:
                self.createNode([connection[0]])
            if connection[1] not in self.nodes:
                self.createNode([connection[1]])

            self.createEdge(connection[0], connection[1])

    def __repr__(self):
        s = "{\n"
        for value in self.nodes:
            node = self.nodes[value]
            s += f"\t{value}: {[n.val for n in node.neighbors]}\n"
        s += "}"
        return s


# Takes in a list of tuples representing connections
my_graph = Graph(
    [
        ("A", "B"),
        ("B", "E"),
        ("E", "D"),
        ("D", "F"),
        ("D", "A"),
        ("A", "C"),
        ("C", "B"),
    ]
)
print(my_graph)

View code on GitHub.

Previous Section

5️⃣

2.5 Queue

⚖️

Copyright © 2021 Code 4 Tomorrow. All rights reserved. The code in this course is licensed under the MIT License. If you would like to use content from any of our courses, you must obtain our explicit written permission and provide credit. Please contact classes@code4tomorrow.org for inquiries.