Graphs

Introduction

1. Collection of vertices(circles) and edges(lines) connected with each other.
2. Vertices have value(name) like 0, 1 etc. Edges can be weighted or unweighted like 10, 20 etc.
3. Relationship can be like cities, computers (vertices) connected with road, wire(edges).
4. Questions will be like

• ifPathExist
• allPossiblePaths
• smallest path(in terms of edges, which less stops) - BFS
• smallest path(in terms of weights, which less stops) - Dijkstra
• Minimum Spanning Tree - Find the number of wires to connect computers. Prims & Kruskal
• Directed Graph File depends upon other file. Tell the order to compile.
• Topological Sort

6. Representation in two ways - Adjacency Matrix and Adjacency List.

Adjacency Matrix

1. 2D Array of VxV.
2. If Edge exists from V to V then weight/1 otherwise 0
3. Can only be formed, if V < 10,000

Adjacency List