Algorithms For Dummies

 

   

  PART 3 

 Exploring the World of Graphs

tree that guarantees a path with the least possible edge weight. An undirected 

graph generally contains just one minimum spanning tree, but, again, it depends 

on the configuration. Think about minimum spanning trees this way: When look-

ing at a map, you see a number of paths to get from point A to point B. Each path 

has places where you must turn or change roads, and each of these junctions is a 

vertex. The distance between vertexes represents the edge weight. Generally, one 

path between point A and point B provides the shortest route.

However, minimum spanning trees need not always consider the obvious. For 

example, when considering maps, you might not be interested in distance; you 

might instead want to consider time, fuel consumption, or myriad other needs. 

Each of these needs could have a completely different minimum spanning tree. 

With this in mind, the following sections help you understand minimum spanning 

trees better and demonstrate how to solve the problem of figuring out the smallest 

edge weight for any given problem. To demonstrate a minimum spanning tree 

solution using Python, the following code updates the previous graph by adding 

edge weights. (You can find this code in the 

A4D; 09; Minimum Spanning Tree.

ipynb

 file on the Dummies site as part of the downloadable code; see the Intro-

duction for details.)

import numpy as np

import networkx as nx

import matplotlib.pyplot as plt

%matplotlib inline

graph = {'A': {'B':2, 'C':3},

         'B': {'A':2, 'C':2, 'D':2},

         'C': {'A':3, 'B':2, 'D':3, 'E':2},

         'D': {'B':2, 'C':3, 'E':1, 'F':3},

         'E': {'C':2, 'D':1, 'F':1},

         'F': {'D':3, 'E':1}}

Graph = nx.Graph()

for node in graph:

    Graph.add_nodes_from(node)

    for edge, weight in graph[node].items():

        Graph.add_edge(node,edge, weight=weight)

pos = { 'A': [0.00, 0.50], 'B': [0.25, 0.75],

        'C': [0.25, 0.25], 'D': [0.75, 0.75],

        'E': [0.75, 0.25], 'F': [1.00, 0.50]}

labels = nx.get_edge_attributes(Graph,'weight')

nx.draw(Graph, pos, with_labels=True)

---

CHAPTER 9