less than 1 minute read

How to analyse and implement graphs in Python.

Overview

Graphs have:

  • vertices (nodes)
  • edges (links)

Edges may be directed. They may also be weighted.

Searching may be done via:

  • BFS - Breadth-first search
  • DFS - Depth-first search

Graphs are analysed in several ways:

  • Euler path - visits every edge once
  • Euler circuit - visits every edge once to start and end at same vertex
  • Hamiltonian path - visits every vertex (Travelling Salesperson)
  • MST - Minimum-Spanning Tree – Prim’s Algorithm – Kruskal’s Algorithm

References

Brad Miller & David Ranum (2011). Problem Solving with Algorithms and Data Structures using Python

QED

© Adam Heinz

9 February 2024

You may also enjoy

GUI Widgets

1 minute read

How to use Tkinter widgets to create a GUI for a Python application.

GUI Introduction

1 minute read

How to use Tkinter to create a GUI for a Python application.