C++ Plus Data Structures, 6th Edition

CHAPTER 13: Graphs

© Repina Valeriya/Shutterstock

Goals

After studying this chapter, you should be able to

• Define the following terms related to graphs:

  • Directed graph

  • Undirected graph

  • Vertex

  • Edge

  • Path

  • Complete graph

  • Weighted graph

  • Adjacency matrix

  • Adjacency list

• Implement a graph using an adjacency matrix to represent the edges

• Explain the difference between a depth-first and a breadth-first search, and implement these searching strategies using stacks and queues for auxiliary storage

• Implement a shortest-path operation, using a priority queue to access the edge with the minimum weight

Up to now, we have considered stacks, queues, linked lists, various forms of trees, heaps, priority queues, sets, and maps. Which of these would ...