Skip to content

Graphs 1

Introduction 1

  • A traversal is simply an ordered way to visit each node or vertex within the graph in a specific order.
  • A directed graph is also referred to as a digraph.
  • Greedy algorithms look for simple, easy-to-implement solutions to complex, multi-step problems by deciding which next step will provide the most obvious benefit.
  • The advantage to using a greedy algorithm is that solutions to smaller instances of the problem can be straightforward and easy to understand.
  • The disadvantage is that it is entirely possible that the most optimal short-term solutions may lead to the worst long-term outcome.

Chapter 11: Graphs 2

Chapter 3: Decomposition of Graphs 3 - Optional

Chapter 4: Paths in Graphs 4 - Optional

Lecture 14: Graphs 5

Chapter 5: Greedy Algorithms 6 - Optional

Greedy Algorithms (and Graphs) By Charles E. Leiserson – MIT 7

Greedy Algorithms by Abhiram Ranade & Sunder Vishwanathan 8

Unit 3 Lecture 1: Graphs as data structures 9

  • A graph is a collection of nodes (vertices) and edges.
  • Applications for graphs:
    • Representing networks (communication or electrical).
    • Representing maps and routes.
  • Graphs can be directed or undirected.
  • Vertex degree: the degree of a vertex is the number of edges connected to the vertex (in + out for directed graphs).
  • Simple path: a path that does not repeat any vertices.
  • Cycle: a path that starts and ends at the same vertex.
  • Connected graph: a graph where there is a path between every pair of vertices.
  • Subgraph: a graph that is a subset of another graph.
  • Tree: a connected graph with no cycles.
  • Forest: a collection of trees.
  • Complete graph:
    • A graph where every pair of vertices is connected by an edge.
    • Aka, all pairs of vertices are adjacent.
    • Aka, every single vertex is connected to every other vertex, and has a degree of n-1.
    • number of edges = n(n-1)/2, where n is the number of vertices.
    • If the graph has < n(n-1)/2 edges, it is not a complete graph.

Unit 3 Lecture 2: Graph Traversals 10

  • Graph traversal: visiting all the vertices in a graph.
  • DFS (stack) or BFS (queue) can be used to traverse tree graphs.

Unit 3 Lecture 3: Greedy Algorithms 11

  • Greedy algorithm: an algorithm that makes the best choice at each step, without worrying about the future or the overall cost.
  • It is useful for optimization problems.
  • Minimum spanning tree (MST):
    • It is the least cost subset of edges that connect all the vertices in a graph.
    • It represents the shortest path between all the vertices.
    • It is is an example of a greedy algorithm.
  • Greedy algorithms do not return the most optimal solution, but they are fast and easy to implement.

References

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

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

  3. Optionally review Chapter 3 Decomposition of Graphs in Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani available at http://www.cs.berkeley.edu/~vazirani/algorithms/chap3.pdf ↩

  4. Optionally review 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 ↩

  5. Read the lecture 14 notes from Design and Analysis of Algorithms available from: http://www.cse.ust.hk/~dekai/271/notes/L14/L14.pdf ↩

  6. Read Chapter 5 Greedy Algorithms in Algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani available at http://www.cs.berkeley.edu/~vazirani/algorithms/chap5.pdf ↩

  7. Greedy Algorithms (and Graphs) By Charles E. Leiserson – MIT. https://youtu.be/FPEMBWg_WlY ↩

  8. Lecture on Greedy Algorithms by Prof. Abhiram Ranade and Prof. Sunder Vishwanathan, Department of Computer Science Engineering, IIT Bombay. https://youtu.be/EcT-Jt5WStw ↩

  9. Unit 3 Lecture 1: Graphs as data structures ↩

  10. Unit 3 Lecture 2: Graph Traversals ↩

  11. Unit 3 Lecture 3: Greedy Algorithms ↩