Graphs Part One: Two types of Graph representation |
||
When it comes to data structures and algorithms, for me at least, Graphs are king. Their widespread applicability to a whole range of topics, from Path Finding in games to routing network traffic and designing circuit boards makes graphs and their algorithms an extremely powerful tool. You may even use graph algorithms in your daily life and not even be aware of it. Google Maps uses a graph search algorithm called "Dijkstra's Algorithm" to generate the paths it gives you when you need directions. Social networks can also be represented as graphs. Basic TerminologyThere is some basic terminology we need to cover before we can really dive in to graphs. Graphs are comprised of Vertexes and Edges. To use decidedly non-technical terms, a vertex, or node, is a "thing" - meaning an object, or more abstractly, it can be a "state" in a state machine, for now at least we will try and steer clear of the abstract. An edge is used to establish relationships between two or more "things". In this article i will use the term vertex and node interchangeably, as they have the same meaning, and node sounds better than thing anyhow. As mentioned earlier, a social network such as facebook can be described in terms of a graph, a person being a vertex and the various connections between other people being the edges. When two vertexes are connected by an edge they are called adjacent nodes. Representing AdjacencyThe two common forms of representing graphs as data strutures are as an "adjacency matrix" and "adjacency lists". Depending on how populous your graph is one way of determining which data structure you ultimately decide upon. If your graph is densely populated with many nodes having many edges, using an adjacency matrix to represent your graph is the convnentional wisdom. Adjacency MatrixSo what is an adjacency matrix? An adjacency matrix is a 2d array with the vertexes as the index of each array, and the elementes representing the edge. In the matrix, an element with the value "0" indicates no adjacency between nodes, and a value of "1" indicates that their IS an edge between the two vertexes. Suppose we had a graph with 5 vertexes: A, B, C, D, E. On initialization, the blank adjacency matrix before any edges are added would looke like this:A B C D E A 0 0 0 0 0 B 0 0 0 0 0 C 0 0 0 0 0 D 0 0 0 0 0 E 0 0 0 0 0 One more point needs to be brought up before we proceed to add edges. Graphs can be either Directed or Undirected. In a directed graph, the Edges are a one way connection, in an undirected graph the connection goes both ways, meaning if you have an edge from A to E, then you also have an edge from E to A. This is not the case in a directed graph. In this article, we will be discussing undirected graphs. With that in mind, lets add some edges to our graph as Well. The first thing we need is a Graph class: #include <iostream> #include <vector> class Graph { private: int numVerts; std::vector<char> Vertexes; std::vector<std::vector<int>> adjMatrix; char name(int v); int index(char v); public: Graph(int N); void addEdge(char v, char u); void showMatrix(); }; Lets talk about we have here, and then we'll get into the rest of the code. Our adjacency matrix Graph class is comprised of the following:
Pretty straight foward so far. Lets have a look at the code for the rest: Graph::Graph(int N) { this->numVerts = N; adjMatrix.resize(N+1, std::vector With our graph class all setup, were finally ready to start adding Edges to build our graph. Let's add the edges AE, AB, BD, BE, CD, and CE, keeping in mind that were adding the corresponding reversed edges as well since it is an undirected graph. int main() { Graph demo(5); demo.addEdge('A', 'E'); demo.addEdge('A', 'B'); demo.addEdge('B', 'D'); demo.addEdge('B', 'E'); demo.addEdge('C', 'D'); demo.addEdge('C', 'E'); demo.showMatrix(); return 0; } All thats left now is to compile our code and view the fruits of our labor: Adjacency ListsThe second form of graph representation I'm going to discuss is the Adjacency list. These are the preferred representation for whats called a "sparse" graph - one which is not as populated as used in an adjacency matrix. An adjacency list is exactly what it sounds like, for each vertex on the graph, you have a cooresponding list of its adjacent nodes, the other vertexes on the graph that it shares an edge with. While you COULD use the STL to build your list, many of the common algorithms are adapted to work quite well with a good old fashioned Linked List. If you need a refresher on how a linked list works, take a look Here. Much of our code for the adjacency list graph representation is similar to the matrix form: #include <iostream< class Graph { private: struct node { char vert; struct node* next; }; int numVerts; char name(int v); int index(char v); struct node *z; struct node **adjlist; public: Graph(int N); ~Graph(); void addEdge(char v, char u); void showList(); }; We've declared the node struct for building our linked lists withing the Graph class. You could have the node struct be external of the Graph class and implement a linked list class as well, however the reason we're NOT doing that is because its actually easier to build the linked list in place, since having access full ownership of the nodes and list is what allows the algorithms to perform the needed operations on the adjacency list seemlessly, hence why we're not using the STL. I'm not saying it isnt a perfectly valid way to do things, but i believe this way gives a deeper understanding of the underlying data structure of the graph and how the algorithms interacts with it. As we did with matrix implementation, lets break down the new Graph class:
And now for a look at the actual code: Graph::Graph(int N) { int i; numVerts = N; z = new node; z->next = z; for (i = 1; i <= numVerts; i++) adjlist[i] = z; } Graph::~Graph() { delete z; } char Graph::name(int v) { return 'A' + v - 1; } int Graph::index(char v) { return v - 'A' + 1; } void Graph::addEdge(char v, char u) { struct node* t; t = new node;; t->vert = v; t->next = adjlist[index(u)]; adjlist[index(u)] = t; t = new node; t->vert = u; t->next = adjlist[index(v)]; adjlist[index(v)] = t; } void Graph::showList() { int i; struct node* t; for (i = 1; i <= numVerts; i++) { std::cout<<name(i)<<": "; for (t = adjlist[i]; t != z; t = t->next) { std::cout<<t->vert<<" "; } std::cout<<"\n"; } } int main() { Graph demo(5); demo.addEdge('A', 'E'); demo.addEdge('A', 'B'); demo.addEdge('B', 'D'); demo.addEdge('B', 'E'); demo.addEdge('C', 'D'); demo.addEdge('C', 'E'); demo.showList(); return 0; } We're using the exact same vertexes and edges as we did for the matrix representation. Building the same graph in a different way, lets takes a look at the results: If you take a peek at the adacency matrix and the adjacency list you can see that they both contain the same information, albeit in differing manners. For example, reading across the top row of the adjacency matrix, we have a "1" in the 'B' and 'E' columns, and when we look at the adjacency list for 'A' we have: B E! continuing along each row, the columns which have a "1" on them show the same same information as all of the adjacency lists. Of course, thats the point. If the values differed we'd be looking at two different graphs, wouldn't we? So there you have it, the adjacency list and adjacency matrix representation of Graphs. It's good to know both, for the reasons stated before, such as one being more efficient than the other depending on graph density, but also because different graphing algorithms are better suited for on representation as opposed to another. This will become more appearent when we begin talking about minimum spanning trees. In the meantime, practice playing around with both, and the next part of this series we will cover some basic graph traversal algorithms. As always, the full code for the examples shown here are available on my GitHub Page. |
||
MaxCodes.info |