Trees, Graphs and C++

This document aims to provide enough background information to encourage you to write graph-related C++ code. First some Standard Containers are shown in action, then some Tree and Graph concepts are introduced. Finally implementation ideas are given to help tackle some exercises.

• Introduction to Standard Containers
• Queues
• Trees
• Tree Traversal
• Graphs
• Graph Traversal
• Implementing Graph Algorithms
• References
• Exercises

Introduction to Standard Containers

Many books exist dealing with sorting and organising data. With the emergence of languages that support data abstraction, people tried to generalise data structures. The Smalltalk language introduced some useful ideas. These have been developed and brought into the mainstream with C++'s Standard Library. The Standard Library includes containers that hold data. Containers are grouped into 3 types

• Sequential - the order of the elements matter (e.g. vector)
• Associative - the order of the elements doesn't matter (e.g. set)
• Adapters - containers that are modifications of other containers (e.g. stack)

These containers have many member functions in common. For example, s.size() gives the number of elements in the container s if s is a set, a list or even a string of characters. The Standard Library also includes algorithms that operate on the containers. To be of maximum use these algorithms need to be able to operate on as many types of containers as possible, so each container has member functions that give algorithms access to the data. For example, s.begin() will always return an Iterator (like a pointer) to the first element of a container s. By hiding the implementation details of containers in this way, high-level generic algorithms can be written which will not only work with the standard containers but also with any new containers that a programmer might write.
The Standard Library doesn't contain a tree container, but if you wrote one so that it had the standard hooks that algorithms require, then algorithms like copy etc. should work with it. Clearly a tree container would require some special routines that other containers wouldn't support, but C++ makes it easy to add functionality in, building on what you already have. Before we look at trees, let's see how to use some simpler containers.

Queues

#include <deque>                                                       

#include <algorithm>                                            

#include <iostream>                                                        

using namespace std;                                                    

int main()                                                                 

{                                                             

deque<int> Q;       //  An empty, elastic, container ready to hold ints.

// A deque is a double-ended queue. Queues (unlike lists) are

// data structures where you wouldn't expect to insert new items

// anywhere else but at the ends

Q.push_back(0);     //  Many containers have a push_back

                    //  routine. It's a way to add elements

                    //  to a container in a safe way - the

                    //  container will grow if it's not big enough.

Q.push_back(2);                                                          

Q.push_back(1);     

// the next line is a bit of magic you'll have to take on trust 

// for now - it "copies" (i.e. prints) the elements of Q to 

// the output stream. A simple "for" loop could be used instead 

// but it's tempting to avoid using "for" altogether.

copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));  

                // Output: 0 2 1                                     

cout <<endl;

// Now let's sort!          

sort(Q.begin(), Q.end());

// the arguments we've given to sort mean that the whole queue

// will be sorted, and that the result will be copied back to

// the original queue. sort uses the default sorting criterium

// for integers, and can use the swap function of Q to switch

// elements around. 

copy(Q.begin(), Q.end(), ostream_iterator<int>(cout, " "));         

// Output: 0 1 2

cout <<endl;                         

}

To create a queue of strings rather than a queue of integers, we don't need to change much. This ease of coping with different data types will be useful when we come to create trees.

#include <deque>                                                       

#include <string> // added so that we can use strings

#include <algorithm>                                            

#include <iostream>                                                        

using namespace std;                                                    

int main()                                                                 

{                                                             

deque<string> Q;       // changed

Q.push_back("standard");           

Q.push_back("template");                                                        

Q.push_back("library");     

// the next line has been changed to support strings rather than integers

copy(Q.begin(), Q.end(), ostream_iterator<string>(cout, " "));  

cout <<endl;

// Now let's sort!