ABSTRACT
Graphs are poweful models in the sense that many real-world situations like rail-way network, computer network can be conveniently described by suitable graphs. Once modelled, they can be processed by a computer. But to process a graph it should be represented.
This chapter starts with two competent representations of graphs: Adjacency matrix and Linked list. Then Prim's algorithm and Kruskal's algorithm for finding a minimum cost spanning tree in a weighted connected graph are presented. Different ways of traversing a tree are studied. We study Dijkstra's single-source shortest path algorithm(positive and negative costs) and Floyd's all-pairs shortest path algorithm and Warshall's algorithm for finding the transitive closure are treated. Navigation in a graph using the Depth-First Search(DFS) and as applications many algorithms like finding connected components, biconnected components, strongly connected components, etc are given. Finally, we study the famous TSP(Traveling Salesman Problem) and present Brute-force algorithm and approximation algorithms.
