graph thegraph new graph()thegraph addvertex(' ')/ (startthegraph addvertex(' ')/ thegraph addvertex(' ')/ thegraph addvertex(' ')/ thegraph addvertex(' ')/ thegraph addedge( )thegraph addedge( )thegraph addedge( )thegraph addedge( )thegraph addedge( )thegraph addedge( )thegraph addedge( )thegraph addedge( )/ab /ad /bc /bd /ce /dc /de /eb system out println("shortest paths")thegraph path()/shortest paths system out println()/end main(/end class pathapp ///////////////////////////////////////////////////////////////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 all 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 matriceso( isn' very good performance if the graph is dense there isn' much we can do about improving this performance (as we noted earlierby dense we mean graph that has many edgesone 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