Something about programming

Graphs

Next tutorial: Depth-First Search (DFS) and Breadth-First Search (BFS) algorithms implementation

In this tutorial we'll learn what are graphs and why we need them in our programming exercises.

We'll talk about graphs and graph theory from the point of view of the programmer. Graph theory is a study that deals with abstract objects and relations between them. Graph is a data structure that consists of nodes (objects, points, vertices). Nodes are connected by the edges (arcs, lines). In our programs nodes can be: cities, rooms, tiles and edges: roads, doors, walls.

Graph can be directed and undirected. For example one-way road on the street between crossroads A and B is an example of directed graph - there is way from first node A to the second node B, but not from the second to the first. If there is two-way road between crossroads A and B, this still be directed graph, but in this case there will be two edges between A and B: from A to B and from B to A. Example of undirected graph: single-track railroad - trains can move in both directions on one track.

Graph implementation in Python

In Python we can easily implement graphs with built-in data types. Let's see example:

graph = { "a": ["c"], "b": ["a", "f"], "c": ["a", "d", "e"], "d": ["b"], "e": ["f", "c"], "f": ["e", "g"], "g": ["h","i"], "h": ["j"], "i": ["f", "e"], "j": ["i"]}

Here we are using dictionary of lists to implement graph. The next step would be to put such structure in a separate class which can represent graphs. This is directed graphs. We can make graph undirected by adding edges to both ends:

graph = { "a": ["b", "c"], "b": ["a", "d", "f"], "c": ["a", "d", "e"], "d": ["b", "c"], "e": ["c", "f", "i"], "f": ["b", "e", "g", "i"], "g": ["f", "h","i"], "h": ["g", "j"], "i": ["f", "g", "e", "j"], "j": ["i"]}

Two nodes are adjacent when they directly connected by edge (not through other node).

Path in a graph is a sequence of nodes whose edges connect any two nodes. For example, path between nodes ai could be ["a","b", "f", "i", "j"]. Or ["a", "c", "e", "i", "j"]. There can be many paths between two nodes.

If there are no repeated nodes, such path is called simple.

Comments:

No comments yet