Page 269 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms Mandeep Kaur, Lovely Professional University

Notes Unit 13: Graphs

CONTENTS

Objectives
Introduction
13.1 Defi ning Graph
13.2 Basic Graph Terminology
13.3 Representations of Graphs

13.3.1 Adjacent Matrix
13.3.2 Adjacency List Representation
13.4 Shortest Path Algorithms
13.5 Summary

13.6 Keywords
13.7 Self Assessment
13.8 Review Questions
13.9 Further Readings

Objectives

After studying this unit, you will be able to:

z Defi ne graph
z Realise basic graph terminology
z Explain representation of graphs
z Discuss shortest path algorithms

Introduction

In this unit, we introduce you to an important mathematical structure called Graph. Graphs have
found applications in subjects as diverse as Sociology, Chemistry, Geography and Engineering
Sciences. They are also widely used in solving games and puzzles. In computer science, graphs
are used in many areas one of which is computer design. In day-to-day applications, graphs fi nd
their importance as representations of many kinds of physical structure.

We use graphs as models of practical situations involving routes: the vertices represent the cities
and edges represent the roads or some other links, specially in transportation management,
Assignment problems and many more optimization problems. Electric circuits are another
obvious example where interconnections between objects play a central role. Circuits elements
like transistors, resistors, and capacitors are intricately wired together. Such circuits can be
represented and processed within a computer in order to answer simple questions like “Is
everything connected together?” as well as complicated questions like “If this circuit is built, will
it work?”

264 LOVELY PROFESSIONAL UNIVERSITY