| |
 |
|
Python |
10.1 Graphs:
Introduction |
|
Introduction:
For this page's inspiration, see especially the subsection:
Implementation [of a graph using adjacency lists
and a dictionary], which is a part of:
Python Data Structures. You should also read or look over
the four subsections before the above-mentioned one.
In fact, if I don't do anything more with this page, the chapter
above is a good reference.
Here is another reference about graphs:
python-course.eu/graphs.
Earlier in these notes (sections
9.1 Basic Program and
9.2 Using a Class), I implemented the subset
algorithm for constructing a DFA from an NFA or from an
NFA with ε-moves. Those programs needed graph representations,
and for that I used Python lists and tuples. This was a particularly
simple approach, and it was completely general as long as one was
willing to rename the vertices of the graph. In particular, with
that approach the nodes needed to be named as consecutive integers
starting with 0. This restriction was only annoying. With
that method it was also possible to add vertices and edges
dynamically, but other dynamic changes wouldn't work in general.
The programs in sections 9.1 and 9.2 also implemented the
ε-closure algorithm, which uses a graph search algorithm
(eps_cl( )),
either depth-first or breadth-first.
Adjacency Matrix
Versus Adjacency List:
The adjacency matrix representation is mostly for large. specialized
applications. I'm only using adjacency lists.
JSON
Representation:
This is an important Python methods for inputting and outputting
complex list structures, but I haven't yet got it to work!
(Revision date: 2015-04-03.
Please use ISO 8601,
the International Standard.)
|