7 Graphs

Two basic representations for Graphs are commonly used, adjacency matrices and adjacency lists. For a graph with n vertices, an n by n matrix A can be used. A_i,j = 1, if there is an edge from vertex i to vertex j. A_i,j = 0, otherwise. This representation is good for some purposes but has two major shortcomings. First, it uses n² space, which can be excessive when there are not very many edges. Graphs with just a few edges emanating from each vertex are common in applications. For instance there may be as few as little as 3 or 4 on average. Then, algorithms which traverse the graph (step from a node to it's neighbors), may waste time for node i seeking a j such that A_i,j = 1, when actually few j are at the other end of an edge from i.

For such sparse graphs, an adjacency list representation is effective. In this representation, for vertex v of graph G, G[v] is a list of the edges emanating from v.

• adjacency list representation
• SSSP and MST: Single source shortest paths, minimal spanning trees
• BFS: Breadth first search algorithm
• DijkstraSSSP: An SSSP algorithm
• PrimMST: An MST algorithm
• KruskalMST: An MST algorithm
• union-find data structure: dynamic disjoint set system
• Network flow :
• Bipartite Matching: