Book contents
- Frontmatter
- Contents
- Preface
- Chapter 1 An Introduction to Collections, Generics, and the Timing Class
- Chapter 2 Arrays and ArrayLists
- Chapter 3 Basic Sorting Algorithms
- Chapter 4 Basic Searching Algorithms
- Chapter 5 Stacks and Queues
- Chapter 6 The BitArray Class
- Chapter 7 Strings, the String Class, and the StringBuilder Class
- Chapter 8 Pattern Matching and Text Processing
- Chapter 9 Building Dictionaries: The DictionaryBase Class and the SortedList Class
- Chapter 10 Hashing and the Hashtable Class
- Chapter 11 Linked Lists
- Chapter 12 Binary Trees and Binary Search Trees
- Chapter 13 Sets
- Chapter 14 Advanced Sorting Algorithms
- Chapter 15 Advanced Data Structures and Algorithms for Searching
- Chapter 16 Graphs and Graph Algorithms
- Chapter 17 Advanced Algorithms
- References
- Index
Chapter 16 - Graphs and Graph Algorithms
Published online by Cambridge University Press: 05 June 2012
- Frontmatter
- Contents
- Preface
- Chapter 1 An Introduction to Collections, Generics, and the Timing Class
- Chapter 2 Arrays and ArrayLists
- Chapter 3 Basic Sorting Algorithms
- Chapter 4 Basic Searching Algorithms
- Chapter 5 Stacks and Queues
- Chapter 6 The BitArray Class
- Chapter 7 Strings, the String Class, and the StringBuilder Class
- Chapter 8 Pattern Matching and Text Processing
- Chapter 9 Building Dictionaries: The DictionaryBase Class and the SortedList Class
- Chapter 10 Hashing and the Hashtable Class
- Chapter 11 Linked Lists
- Chapter 12 Binary Trees and Binary Search Trees
- Chapter 13 Sets
- Chapter 14 Advanced Sorting Algorithms
- Chapter 15 Advanced Data Structures and Algorithms for Searching
- Chapter 16 Graphs and Graph Algorithms
- Chapter 17 Advanced Algorithms
- References
- Index
Summary
The study of networks has become one of the great scientific hotbeds of this new century, though mathematicians and others have been studying networks for many hundreds of years. Recent developments in computer technology (i.e., the Internet), and in social theory (the social network, popularly conceived in the concept of “six degrees of separation”), have put a spotlight on the study of networks.
In this chapter, we look at how networks are modeled with graphs. We're not talking about the graphs such as pie graphs or bar graphs. We define what a graph is, how they're represented in VB.NET, and how to implement important graph algorithms. We also discuss the importance of picking the correct data representation when working with graphs, since the efficiency of graph algorithms is dependent on the data structure used.
GRAPH DEFINITIONS
A graph consists of a set of vertices and a set of edges. Think of a map of your state. Each town is connected with other towns via some type of road. A map is a type of graph. Each town is a vertex and a road that connects two towns is an edge. Edges are specified as a pair, (v1, v2), where v1 and v2 are two vertices in the graph. A vertex can also have a weight, sometimes also called a cost.
- Type
- Chapter
- Information
- Data Structures and Algorithms Using C# , pp. 283 - 313Publisher: Cambridge University PressPrint publication year: 2007