In this section we will consider two very important data structures - graphs and trees. We are learning ...- About graphs
- About trees
- About traversal algorithms
So that we can ...- Represent graphs as data structures
- representing complex relationships - typical uses - terms
- Represent graphs
- Adjacency matrix and adjacency list - Advantages and disadvantages of both
- Apply breadth first and depth first graph traversal algorithms and describe typical applications of both
- depth first : navigating a maze - breadth first : shortest path for unweighted graph - Describe and represent trees
- Connected, undirected graph with no cycles - Rooted tree where every vertex is directed away from the root
- Describe binary trees
- Binary tree (rooted tree with <= 2 children per node) - Representing binary trees using pointers - Typical uses
- Trace tree traversal algorithms and their applications
- pre-order - in-order - post-order - Describe and implement route / pathfinding algorithms- Dijkstras shortest path algoritm- A* algorithm
Way back in the AS part of the course, we met the 'Poor cartographer' - a problem in graph colouring. We actually used a game called
Floodfill (which I'm not expecting you to play now, but you probably will!) A solution to this problem involves drawing graphs - connected diagrams which are used, in this case, to represent barred relationships between areas to be coloured. Using this data structure and a particular algorithm, we were able to deduce a solution (though not always optimal) to the problem.The 'Poor Cartographer'
Graphs are an abstraction which are used to represent real world problems in a way which makes them easy to solve either logically or mathematically. The first ever application of graph theory (and hence it's conception) occurred in the early 18th century and is attributed to the mathematician
Leonhard Euler.
There is lots of terminology surrounding graphs in computer science. There is a document in the lesson resources called
Graph and tree definitions. Download it and keep a copy stuck in your notebooks for reference. The list is not meant to be exhaustive (even though it's very long) as this discrete mathematics topic is a whole course in itself!Graphs are normally drawn with sequenced circles (with or without labels) to represent the vertices and lines (with or without arrows, labels or weights) to represent the edges. The diagram shows a representation of
some graph components.I
think I've covered everything! If you are a further mathematician and you are raging, please let me know. I'm not going to ask you to do anything particular with these definitions now, but keep this list in mind when you are working throught the rest of the topic. Lol!
In Computer Science, graphs are an representation abstraction which allow us to model diverse complex relationships in a consistent way allowing us to apply similar algorithms to every situation in order to solve problems presented by them
Chain links and the Oracle of BaconIn 1929, a Hungarian author called
Frigyes Karinthy published a short story called 'Chains' where he introduced the concept of 'six degrees of separation'. Later on, film buffs all over the world invented the parlour game 'Six degrees of Kevin Bacon' where they challenged each other to connect any Hollywood actor to Kevin Bacon through the least number of films possible.
Diverse systemsIt turns out that wherever there are relationships between 'things' a graph can be drawn which connects them. For instance ...
... and there are literally hundreds more. Can you think of any?
Integer factors
All graphs can be represented as a collection of
vertices and the connections which exist between them. The properties of the vertices and connections define both the type of graph and it's behaviour.Vertex and Edge SetsConsider the following six graphs labelled a) through f) which cover most of the major graph types. We will use these graphs a lot over the next few tasks so you might want to print out the diagram for your notebooks.
Diagram AClick to engage
For instance, the graphs in Diagram A can be represented using one of two different vertex sets ...
- Graphs a), b), c) and d) have the vertex set
`v = {1,2,3,4,5}` - Graphs e), f), g) and h) have the vertex set
`v = {(1,Y),(2,P),(3,G),(4,B),(5,G)}` where the letters represent the colours of the vertices as their labels.
There are two widely accepted methods for representing the connections in a graph ...
- Adjacency list
- Adjacency matrix
Graph Implementations (7:14)
Adjacency list vs adjacency matrixThere are certain situations where an matrix is beneficial and certain where a list is best.
This is the fun bit! All graph representation require that you store information about both the vertices and the edges which connect them. There are various ways of accomplishing this but by far the most flexible is through the use of a vertex class which is defined by it's ID and contains a dictionary of weighted 'connections' (general name for edges / arcs) and a graph class which is built from a dictionary of vertex objects identified by their vertex ID plus a Boolean attribute which classifies the graph as directed / undirected.
Graph traversal / searchingTraversal of a graph involves visiting every node starting at some arbitrary node, called the root of the graph. Searching involves looking for a node starting at some particular node. Traversal / searching traditionally takes place in one of two different ways - so called
breadth or depth first. Be careful - the terms 'traverse' and 'search' are often confused.Graph Traversals (9:52)
Depth first traversalNote to self : These scripts *seems* wrong - review and correctDFT uses a stack data structure to keep track of discovered vertices. As we shouldn't really alter the graph to 'mark the vertex as visited', we also need a simple list to keep track of the vertices we have visited in the order we visited them. In the video, 'John' perform a recursive depth first traversal, using a stack. In practice, no explicit stack is needed as the recursion takes care of that bit. Depth first traversal is suited to recursion, because it's 'deep'.
`def dftR(G,n,visited=[]):` ` """ Recursive depth first traversal """` ` visited.append(n)` ` for v in G.connections(n):` ` if v not in visited:` ` dftR(G,v,visited)` ` return visited` You can perform a depth first traversal iteratively (many programmers would prefer this to reduce the risk of recursion depth errors for large graphs, especially in Python), but it is a little more complicated and the vertices are visited in a different order that they are in the recursive routine (but still in depth first order).
`def dft(G,n):` ` """ Iterative depth first traversal """` ` stack = [n]` ` visited = []` ` while stack:` ` v = stack.pop()` ` if v not in visited:` ` visited.append(v)` ` for x in G.connections(v):` ` stack.append(x)` ` return visited` Breadth first traversalNote to self : Probably need to check these as wellBFT is
not naturally suited to recursion since it does not have the 'depth' element that most recursive functions need - you can implement it recursively but it's more a theoretical exercise than a practical implementation. So we'll implement this iteratively. BFT is closely related to the iterative DFT apart form the use of a queue instead of a stack and the order in which you mark the vertices as visited.`def bft(G,n):` ` """ Iterative breadth first traversal """` ` queue = [n]` ` visited = [n]` ` while queue:` ` v = queue.pop(0)` ` for x in G.connections(v):` ` if x not in visited:` ` queue.append(x)` ` visited.append(x)` ` return visited`
Depth first traversal / search can be used to ...
- Produce the 'minimum spanning tree' of a graph
- Detect cycles in a graph (with some modification)
- Find a (often
**suboptimal**) path through the graph - Solve puzzles with only one solution (perfect mazes / trees)
Breath first traversal / search can be used to ...
- Produce the 'minimum spanning tree' of a graph
- Find the shortest path through a network (weighted graph)
- Finding all neighbour nodes in a peer to peer network
- Search engine crawlers
- Find degrees of separation between two vertices, say in a social network
In mathematics, a tree is a "connected, undirected graph which contains no cycles or loops". An arbitrary tree is represented in the same way as a graph where the number of edges is
always the same as the number of nodes. A rooted tree is hierarchical (like a family tree) and will have a root node with all other nodes branching away from it.There is plenty more terminology associated with trees (which isn't in a handout) ...
Binary search treesA binary search tree is a rooted, ordered, directed tree which has
no more than two children per parent node. A binary tree is 'proper' if each internal node (i.e. not leaf nodes) has exactly two children.Binary trees are ...
- Useful for storing data with an inherently hierarchical structure;
- Dynamic - it is easy to add and delete nodes;
- Easy to search and sort;
- Deep (man).
Binary trees are constructed in a different way to arbitrary tree which is simply a graph with no cycle. You do not treat them like graphs even though they look similar.
A practical binary search treeEach vertex in the tree (including the root vertex) must have a 'payload' / value and has the potential to have a parent, zero children (i.e. it's a leaf), a left child (which is ordinally less than the vertex), a right child (which is ordinally greater than the vertex) or both. That child vertex
could itself be the root node of a separate subtree.It is (relatively) easy to construct a binary search tree from vertex objects with a unique id, a 'value', and three pointers, one to the parent, a left child and a right child. If no parent or child vertex exists, the pointer will have a null value.
Binary search tree vertex object
As you can imagine, there are plenty of different ways of implementing this in practice, but I've chosen one which works similarly to the linked list abstract data structure which we have met before.
There are plenty of other ways of implementing a binary search tree, just like there are plenty of ways of implementing a graph which are more straightforward than this. I've tried to give you a 'low level' implementation which doesn't involve more complex concepts. Once you understand the basics, it's easy to simplify your implementation to suit. Take a look in the extension activities for more tutorials which give you different approaches.
Binary tree traversal / searchingTrees can be traversed in the same way as graphs (well, they are graphs, aren't they?) In fact, traversing a graph produces a tree (but not always a binary tree). We've looked at breadth first and depth first traversals of graphs in a previous section - remember that binary trees are constructed differently than graphs therefore they have to be traversed in a different way.In a depth first traversal of a
binary tree, you 'travel' down each branch as far as you can go working from left subtree to right subtree, backtracking when you reach a leaf node.Depth first binary tree traversal
If you think of a depth first traversal of a binary tree as a journey clockwise, around the walls of a rather strange city, where the vertices are towers with three doors, facing West, South and East, you might see that there are three ways of 'visiting' each vertex. If we walk around our city going into each tower through each door we find, this is called a
Euler Tour Traversal. You can perform one yourself if you like using Minecraft Euler Tour.zip which is available from the lesson resources.There are three special cases of a Euler tour traversal ...
*Only*entering through the west doors, a so called 'Preorder Traversal'*Only*entering through the south doors, a so called 'Inorder Traversal'*Only*entering through the east doors, a so called 'Postorder Traversal'
Applications of tree traversalsRemember that you can have two basic types of tree -
arbitrary trees which are simply graphs without cycles and a specific case called a binary tree which is a rooted, ordered, directed tree which has no more than two children per parent node. Pre and postorder traversals make sense for all trees whereas inorder traversals can only be achieved using binary trees.Preorder traversalsA preorder traversal is equivalent to a standard graph depth first traversal where the vertex is 'visited' first before its children are visited and can be applied to any tree. A preorder tree traversal can be used for ...
- Inspecting all vertices before their children
- Making an exact copy of a tree
*Converting a mathematical expression tree into a prefix expression*- Reading a book from beginning to end ...
Inorder TraversalsYou can only perform inorder traversals on a binary tree (see this link). The inorder tree traversal can be used for ...- Returning the underlying data set in order (we've seen this!)
*Generate an infix expression from mathematical expression tree*
Postorder traversalsA postorder tree traversal is equivalent to a standard graph depth first search where the node is only 'visited' after it's children have been explored and can be applied to any tree. The postoder tree traversal can be used for ...
- Inspecting all leaves before their parents
- Deleting a tree from the leaves up
*Generate a postfix expression from a mathematical expression tree*- Calculating disk storage from files through directories to disk ...
You'll notice that all three traversal methods can be used to generate arithmetic expressions from mathematical expression trees. Consider the following binary expression tree traversals ... Generates the prefix expression ... * + 5 6 - 8 3Generates the infix expression ... ((5+6)*(8-3))Output '(' before traversing a left subtreeOutput ')' after traversing a right subtreeGenerates the postfix expression ... 5 6 + 8 3 - *
The path finding algorithms we study at A Level are greedy algorithms - they make the best choice at any single given point and never look ahead or look behind to find a more efficient solution and therefore, even though they are generally fast, they do not always find the optimal solution. This is in contrast to dynamic programming solutions which, though slower, will consider the whole problem and refine the solution based on future detail (and are well outside the scope of A Level).There are a number of so called standard 'Pathfinding algorithms' including the very well known Dijkstra's Algorithm and the related special case, the A* Algorithm which will shall study at this level.Dijkstra's AlgorithmThere are two parts to the simplest implementation of Dijkstra's Algorithm ... a) the discovery of the shortest path from the starting vertex to all other vertices (stopping on the discovery of the destination vertex if we are searching for a particular path) and b) backtracking to find the shortest route from each vertex to the start.Your teacher will demonstrate how to implement both parts of Dijkstra's Algorithm on the following graph ...Click to enlarge and print a copy!
In the following Computerphile video, Dr Pound shows you a method of combining both methods into one using a priority queue. Use of a priority queue avoids the use of the 'backtracking' part of the Dijkstra's Algorithm we saw in the previous part of the lesson, therefore speeding up the process.Dijkstra's Algorithm - Computerphile (10:42)
You've got to be kidding! A* AlgorithmThe A* algorithm is an extension of Dijkstra's Algorithm which implements simple heuristics in order to keep the search for the shortest path in generally the correct direction. Again, Dr Pound explains it much better than I could ever do, so, watch the video ...A* (A Star) Search Algorithm - Computerphile (14:03)
You've got to be kidding!
How about these?
- Download and complete the extra worksheet
**Graph traversal exercise**from the lesson resources. - Read more about creating a binary search tree implementation at
**Kukuruku**. - And
**another**with a different approach using just one class for the node. After all, a binary tree is a node, isn't it? - Could you try to implement some of the applications of tree traversals? You will need to use either graph or binary tree abstract data structures depending on what you want to achieve and you might need to alter the structure of the vertex nodes to incorporate a 'data' attribute and then use this to store the information you will process like the component of the expression tree or the disk cost of a file. Great focus for project work!
- You can also traverse a binary search tree breadth first though it is not as commonly used. Read the information on the following
**website**and try to implement a breadth first binary search tree traversal algorithm yourself. - Depth first traversal of a tree can be used to find a (non-optimal) route through a perfect maze (no cycles or open spaces). Remember, however, that mazes are arbitrary trees, not binary trees. You represent them as graphs with no cycles,
*not*binary trees. Click the maze to find out more.
- Visualise path finding algorithms using
**PathFinding.js**! - One application of shortest path algorithms is in the field of
**maze solving**. Use the following resources to research mazes and the implementation of their solution. - Dr Pound**extends his treatment**of shortest path algorithms to mazes on YouTube. - Dr Pounds**implementation**of his maze algorithms. -**Daedalus**Maze Drawing program.
END OF TOPIC ASSESSMENT |