Question? Leave a message!

Graph Data Structures

Graph Data Structures
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures Graph Data Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering Structures University of Waterloo Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Matrix Data Structures 2 Outline • In this topic, we will cover the representation of graphs on a computer • We will examine: – an adjacency matrix representation – smaller representations and pointer arithmetic – sparse matrices and linked listsMatrix Data Structures 3 Background • Project 5 requires you to store a graph with a given number of vertices numbered 0 through n – 1 • Initially, there are no edges between these n vertices • The insert command adds edges to the graph while the number vertices remains unchangedMatrix Data Structures 4 Background • In this laboratory, we will look at techniques for storing the edges of a graph • This laboratory will focus on weighted graphs, however, for unweighted graphs, one can easily use bool in place of doubleMatrix Data Structures 5 Background • To demonstrate these techniques, we will look at storing the edges of the following graph:Matrix Data Structures 6 Adjacency Matrix A graph of n vertices may have up to n  n(n1) 2 O(n )  2 2  edges The first straight-forward implementation is an adjacency matrixMatrix Data Structures 7 Adjacency Matrix Define an n× n matrix A = (a ) and if the vertices v and v are ij i j connected with weight w, then set a = w and a = w ij ji That is, the matrix is symmetric, e.g., Matrix Data Structures 8 Adjacency Matrix An unweighted graph may be saved as an array of Boolean values – vertices v and v are connected then set i j a = a = true ij jiMatrix Data Structures 9 Adjacency Matrix If the graph was directed, then the matrix would not necessarily be symmetric Matrix Data Structures 10 Adjacency Matrix First we must allocate memory for a two-dimensional array C++ does not have native support for anything more than one- dimensional arrays, thus how do we store a two-dimensional array? – as an array of arraysMatrix Data Structures 11 Adjacency Matrix Suppose we require a 16 × 16 matrix of double-precision floating- point numbers Each row of the matrix can be represented by an array The address of the first entry must be stored in a pointer to a double: double Matrix Data Structures 12 Adjacency Matrix However, because we must store 16 of these pointers-to-doubles, it makes sense that we store these in an array What is the declaration of this array? Well, we must store a pointer to a pointer to a double That is: double Matrix Data Structures 13 Adjacency Matrix Thus, the address of the first array must be declared to be: double matrix;Matrix Data Structures 14 Adjacency Matrix The next question is memory allocation First, we must allocate the memory for the array of pointers to doubles: matrix = new double 16;Matrix Data Structures 15 Adjacency Matrix Next, to each entry of this matrix, we must assign the memory allocated for an array of doubles for ( int i = 0; i 16; ++i ) matrixi = new double16; Matrix Data Structures 16 Adjacency Matrix Accessing a matrix is done through a double index, e.g., matrix34 You can interpret this as (matrix3)4Matrix Data Structures 17 Adjacency Matrix Recall that in matrix34, the variable matrix is a pointer-to-a- pointer-to-a-double:Matrix Data Structures 18 Adjacency Matrix Therefore, matrix3 is a pointer-to-a-double:Matrix Data Structures 19 Adjacency Matrix And consequently, matrix34 is a double:Matrix Data Structures 20 C++ Notation Warning Do not use matrix3, 4 because: – in C++, the comma operator evaluates the operands in order from left- to-right – the value is the last one Therefore, matrix3, 4 is equivalent to calling matrix4 Try it: int i = (3, 4); cout i endl;