Skip to content

4. Graphs (Part 2)

Introduction 1

  • The problem of finding the Minimum Spanning Tree (path that the salesman must take) is a good example of greedy algorithms.
  • Minimum Spanning Tree (MST) is a tree that connects all the vertices in a graph with the minimum possible total edge weight:
    • Prim’s Algorithm.
    • Kruskal’s Algorithm.

Ch. 11: Graphs 2 4 6

  • |V| is the number of vertices in a graph.
  • |E| is the number of edges in a graph.
  • Max number of edges: |V|^2-|V| where V is the number of vertices.
  • A graph with relatively few edges is called sparse, while a graph with many edges is called dense.
  • A graph containing all possible edges is said to be complete.
  • Two vertices are adjacent if they are joined by an edge, also called neighbors.
  • A cycle is a path of length three or more that connects some vertex v1 to itself.
  • A cycle is simple if the path is simple, except for the first and last vertices being the same.
  • An undirected graph is connected if there is at least one path from any vertex to any other. The maximally connected subgraphs of an undirected graph are called connected components.
  • A free tree is a connected, undirected graph with no simple cycles. An equivalent definition is that a free tree is connected and has |V| - 1 edges.
  • The adjacency matrix for a graph:
    • It is a |V| × |V| array.
    • It stores a bit (0 or 1) indicating whether two vertices are adjacent; aka, there is an edge between v at row i and w at column j.
    • It can also be used to store edge weights.
    • Space requirement is \Theta(|V|^2).
  • The adjacency list for a graph:
    • It is an array of |V| linked lists.
    • Each vertex has a list of vertices it is adjacent to.
    • Space requirement is \Theta(|V|+|E|) where E is the number of edges.
  • Which graph representation is more space efficient:
    • It depends on the number of edges in the graph.
    • The adjacency list stores information only for those edges that actually appear in the graph, while the adjacency matrix requires space for each potential edge, whether it exists or not.
    • However, the adjacency matrix requires no overhead for pointers, which can be a substantial cost, especially if the only information stored for an edge is one bit to indicate its existence.
    • As the graph becomes denser, the adjacency matrix becomes relatively more space efficient.
    • Sparse graphs are likely to have their adjacency list representation be more space efficient.
    • The adjacency matrix often requires a higher asymptotic cost for an algorithm than would result if the adjacency list were used.

11.2 Graph Implementation

  • Graph Class:
    • n() returns the number of vertices in the graph.
    • e() returns the number of edges in the graph.
    • weight(v, w) returns the weight of the edge between vertices v and w.
    • setEdge(v, w, weight) sets and edge from v to w with the given weight.
    • delEdge(v, w) deletes the edge between vertices v and w.
    • getMark(v) returns the mark associated with vertex v.
    • setMark(v, value) sets the mark associated with vertex v to value.
    • first(v) returns the first neighbor of vertex v, according to some order.
    • next(v, w) returns the neighbor of vertex v that follows w, according to some order.

11.3 Graph Traversals

  • Traversal is to visit the vertices of a graph in some specific order based on the graph’s topology.
  • Graph traversal algorithms typically begin with a start vertex and attempt to visit the remaining vertices from there.
  • Issues with traversals:
    • Not connected graphs: there may be no path from the start vertex to some other vertex.
    • Cycles: a cycle can cause a traversal to loop indefinitely.
  • Mark Matrix:
    • Graph traversal algorithms can solve both of these problems by maintaining a mark bit for each vertex on the graph.
    • At the start of the traversal, all vertices are marked as unvisited (matrix is cleared).
    • When a vertex is visited, it is marked as visited.

11.5 Minimum-Cost Spanning Trees

  • The MST problem takes as input a connected, undirected graph G, where each edge has a distance or weight measure attached.
  • Applications where a solution to this problem is useful include:
    • Soldering the shortest set of wires needed to connect a set of terminals on a circuit board.
    • Connecting a set of cities by telephone lines in such a way as to require the least amount of cable.
  • The MST contains no cycles.
  • If a proposed set of edges did have a cycle, a cheaper MST could be had by removing any one of the edges in the cycle.
  • Thus, the MST is a free tree with |V|-1 edges.
  • Prim’s Algorithm:
    • Start with any vertex N in the graph, setting the the MST to be the single vertex.
    • Pick the next point M, that is least-cost edge connected to N.
    • Add M and Edge(N, M) to the MST.
    • Next, pick the least-cost edge connected to either N or M.
    • Continue until all vertices are in the MST.
    • The primary difference from Dijkstra’s algorithm is that Prim’s algorithm adds the least-cost edge to any vertex in the MST, not just the start or the current vertex.
    • Alternatively, we can implement Prim’s algorithm using a priority queue to find the next closest vertex.
    • It is a greedy algorithm.
  • Kruskal’s Algorithm:
    • Start by partitioning the vertices into |V| sets, each containing a single vertex.
    • Repeatedly select the least-cost edge that connects two different sets.
    • Add the edge to the MST and merge the two sets.
    • Continue until all vertices are in the MST.
    • It is a greedy algorithm.
    • The edges can be processed in order of weight by using a min-heap.
    • Thus, the total cost of the algorithm is Θ(|E| log |E|) in the worst case, when nearly all edges must be processed before all the edges of the spanning tree are found and the algorithm can stop.

Minimum Spanning Trees 5

  • Spanning Trees: A subgraph T of a undirected graph G = (V,E) is a spanning tree of G if it is a tree and contains every vertex of G.
  • Every connected graph has a spanning tree.
  • The weight of a graph is the sum of the weights of its edges.
  • A graph may have multiple spanning trees, each with a different weight.
  • A minimum spanning tree (MST) is a spanning tree of a graph with the smallest possible weight among all spanning trees.
  • There may be multiple MSTs for a graph, if placing edges in a different order results in the same weight.

Prim’s Algorithm

  • Running Time O((|V| + |E|)log |V|).
  • Maintain a priority queue of vertices to pick up the next lightest edge from the remaining vertices, and add it to the MST.
  • PriorityQueue class:
    • insert(item, key) inserts an item with a key.
    • deleteMin() deletes the item with the smallest key.
    • decreaseKey(item, newKey) decreases the key of an item.
    • isEmpty() returns true if the queue is empty.

Kruskal’s Algorithm 7 8

  • Running Time O(|E| log |E|) or O(|E| log |V|).
  • Initially, trees of the forest are the vertices (no edges).
  • In each step add the cheapest edge that does not create a cycle.
  • Observe that unlike Prim’s algorithm, which only grows one tree, Kruskal’s algorithm grows a collection of trees (a forest).
  • Continue until the forest ‘merge to’ a single tree.

Lectures 12 13 14

  • Roots have in-degree 0 and leaves have out-degree 0.
  • A tree id s a connected acyclic undirected graph.

References

  1. Learning Guide Unit 4: Introduction | Home. (2025). Uopeople.edu. https://my.uopeople.edu/mod/book/view.php?id=453909&chapterid=554109 ↩

  2. Chapter 11 Graphs, Sections 11.1 – 11.3 in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. ↩

  3. Chapter 4 Paths in Graphs in Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani available at http://www.cs.berkeley.edu/~vazirani/algorithms/chap4.pdf ↩

  4. ‌Chapter 11 Graphs, Sections 11.1 – 11.3 in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. ↩

  5. Read Lecture 7: Minimum Spanning Trees and Prim’s Algorithm available at http://www.cse.ust.hk/~dekai/271/notes/L07/L07.pdf ↩

  6. Chapter 11 Graphs, Sections 11.1 – 11.3 in A Practical Introduction to Data Structures and Algorithm Analysis by Clifford A. Shaffer. ↩

  7. Read Lecture 8: Lecture 8: Kruskal’s MST Algorithm available at http://www.cse.ust.hk/~dekai/271/notes/L08/L08.pdf ↩

  8. Read the Wikipedia article on Kruskal’s algorithm paying special attention to the pictoral representation of how Kruskal’s algorithm creates a minimum spanning tree from a collection of graphs that are assembled together. Available at http://en.wikipedia.org/wiki/Kruskal's_algorithm ↩

  9. (2025). Youtube.com. https://www.youtube.com/watch?v=xhG2DyCX3uA ↩

  10. (2025). Youtube.com. https://www.youtube.com/watch?v=Ttezuzs39nk ↩

  11. (2025). Youtube.com. https://www.youtube.com/watch?v=Sygq1e0xWnM ↩

  12. Unit 4 Lecture 1: Minimum path and Spanning Tree ↩

  13. Unit 4 Lecture 2: Prim’s Algorithm ↩

  14. Unit 4 Lecture 3: Kruskal’s Algorithm ↩