Basic Concepts of Graph

What is a graph? • A data structure that consists of a set of nodes or vertices and a set of edges that relate the nodes to each other • The set of edges describes relationships among the vertices

Undirected graphs • When the edges in a graph have no direction, the graph is called undirected

Directed Graph

When the edges in a graph have a direction, the graph is called directed graph.

Graph Representation Vertices can be represent as one dimensional array. Graph edges are commonly represented in two ways:

1. Adjacency Matrix An adjacency matrix is 2D array of V x V vertices. Each row and column represent a vertex. If the value of any element a[i][j] is 1, it represents that there is an edge connecting vertex i and vertex j.

2. Adjacency List Adjacency list is a collection of unordered lists used to represent a finite graph.

Graph terminology Complete graph: A graph in which every vertex is directly connected to every other vertex.