Introduction to Graphs

The limitation of tree is that it cannot represent many to many relation.
This limitation is overcome by using Graph.

Definition of a Graph
——————————-
Graphs is a data structure consisting of a set of vertices (or nodes)
A set of edges (or links) connecting the vertices
G = (V, E) where
V = set of vertices
E = set of edges, each edge is formed from a
pair of distinct vertices

Graph Representation
——————————–
A set of items connected by edges. Each item is called a vertex or node. Formally, a graph is a set of vertices and a binary relation between vertices, adjacency.

The Graph is most widely represented in linked lists.

To represent a graph, a linked list is created for each vertex.

Graph Terminologies
——————————-
Directed and Undirected Graph

If there is no order or direction by which the vertices are connected then the graph is called undirected graph.

If there is a specific order by which the vertices are connected, it is called directed graphs.

Adjacency: If two vertex such as vertex b is connected to vertex a by an edge. The vertices b and a are called adjacent to each other.

Incidence: The edge of two vertices is said to be incident.

Degree: The degree of a vertex in undirected graph is the number of edges incident on the vertex.

Path: A path in a graph is the sequence of vertices visited while traveling from one vertex to another where any two consecutive vertices in the sequence are adjacent.

Cycle: If a path originates and terminates at the same vertex, it is called a cycle.

Connected graph: A graph is said to be connected, if there exists a path between any two vertices in the graph.

Weighted Graphs: In a graph, if the edges connecting vertices are given weights (values) then it is a weighted graph.

Sub Graphs: A graph is a subgraph of another graph, when its vertices and edges are subsets of that graph.

Graph Traversals
————————-
Depth First Search: It is an algorithm for traversing or searching a tree, tree structure, or graph. Intuitively, you start at the root (selecting some node as the root in the graph case) and explore as far as possible along each branch before backtracking.

Formally, DFS is an uninformed search that progresses by expanding the first child node of the search tree that appears and thus going deeper and deeper until a goal state is found, or it hits a node that has no children. Then the search backtracks and starts off on the next node.

• ConclusionGraphs contain a finite set of vertices or elementsThe vertices are connected by edges, the line joining the verticesIf there is a specific order by which the vertices are connected, it is called directed graphs

  If the vertex b is connected to vertex a by an edge, then the vertices b and a are adjacent to each other

  The edge (b, a) is said to be incident on vertices b and a.