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
Comment
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 ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 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;