weighted graphs efficiency so far we haven' discussed the efficiency of the various graph algorithms the issue is complicated by the two ways of representing graphsthe adjacency matrix and adjacency lists if an adjacency matrix is usedthe algorithms we've discussed mostly require ( timewhere is the number of vertices whyif you analyze the algorithmsyou'll see that they involve examining each vertex onceand for that vertex going across its row in the adjacency matrixlooking at each edge in turn in other wordseach cell of the adjacency matrixwhich has cellsis examined for large matrices ( isn' very good performance if the graph is densethere isn' much we can do about improving this performance (as we noted earlierby dense we mean graph that has many edges--one in which many or most of the cells in the adjacency matrix are filled howevermany graphs are sparsethe opposite of dense there' no clear-cut definition of how many edges graph must have to be described as sparse or densebut if each vertex in large graph is connected by only few edgesthe graph would normally be described as sparse in sparse graphrunning times can be improved by using the adjacency-list representation rather than the adjacency matrix this is easy to understandyou don' waste time examining adjacency-matrix cells that don' hold edges for unweighted graphs the depth-first search with adjacency lists requires ( +etimewhere is the number of vertices and is the number of edges for weighted graphsboth the minimum spanning tree and the shortest-path algorithm require (( + )logvtime in largesparse graphs these times can represent dramatic improvements over the adjacency matrix approach howeverthe algorithms are somewhat more complicatedwhich is why we've used the adjacency-matrix approach throughout this you can consult sedgewick (see appendix "further reading"and other writers for examples of graph algorithms using the adjacency-list approach warshall' and floyd' algorithms are slower than the other algorithms we've discussed so far in this book they both operate in ( time this is the result of the three nested loops used in their implementation intractable problems in this book we've seen big values ranging from ( )through ( ) ( *logn) ( )up to (for warshall' and floyd' algorithmso( even ( can be solved in reasonable length of time for values in the thousands algorithms with these big values can be used to find solutions to most practical problems