Introducing Data Structures with Java

13

Graphs

Graphs

Contents

• Non-hierarchical data structures
• Graph representation—vertices and edges
• Traversing graphs
• Shortest paths—Dijkstra’s algorithm
• Spanning trees—Kruskal’s and Prim’s algorithms
• Implementing a Graph class

13.1 INTRODUCTION

In our exploration of data structures, we have examined ways in which items may be linked together. Each node in a list, stack or queue has a maximum of one successor and one predecessor; a node in a binary tree may be linked to a maximum of two children. These structures demonstrate a ‘hierarchy’ whose members are ordered by value (Figure 13.1) in the case of a sequential list and a binary search tree ...