## Overview

2) Adjacent nodes

3) Degree of anode

4) Path

5) Connected Graph

6) Labelled & Weighted Graph

7) Multi Graph &-Directed Graph

8) Complete Graph

9) Representation of Graph

## What Is Graph?

- Graph is nonlinear data structure
- Graphs are a fundamental data structure used in computer science and mathematics to represent relationships between different entities. They consist of a set of vertices or nodes, connected by edges or links.
- These vertices can represent any discrete object or entity, while the edges depict the relationships or connections between them.

e0 = [V0, V1]

e1 = [v1, v2 ]

V = {V0, V1, V2, V3, V4 }

E = {e0, e1, e2, e3, e4}

**A Graph Consists of two things**

A set V of elements called nodes.

A set E of edges such that each edge e in E is identified with a unique (unordered)

pair [u ,v] of nodes in V, denoted by e = [u,v] we indicate the parts of the graph by writing G=(V,E)

## Some Common Types Include

**Directed and Undirected Graphs:**In directed graphs, the edges have a specific direction, while in undirected graphs, the edges have no direction.**Weighted and Unweighted Graphs:**Weighted graphs assign a weight or cost to each edge, whereas unweighted graphs do not.**Cyclic and Acyclic Graphs:**Cyclic graphs contain cycles, which are paths that lead back to the starting node, while acyclic graphs do not have any cycles.

## Directed & Undirected Graph

**Undirected Graphs:**

- In an undirected graph, the edges have no specific direction associated with them.
- They represent symmetric relationships. For example, if there is an edge between nodes A and B, it implies that there is a symmetric relationship between A and B; you can traverse from A to B and vice versa.
- Formally, an edge {A, B} in an undirected graph indicates a connection between node A and node B, without any notion of a one-way relationship.

**Directed Graphs:**

- In a directed graph (also known as a digraph), each edge has a specific direction associated with it.
- They represent asymmetric relationships. For example, if there is a directed edge from node A to node B, it implies a one-way relationship or a specific direction from A to B.
- Formally, an edge (A, B) in a directed graph indicates a directed connection from node A to node B.

## Adjacent Nodes

If e = [u,v] then u and v

are called adjacent nodes or neighbors .

## Degree Of Node

If deg(u)=0, then u is called isolated node

## Path

p =(v0, v1, v2,…… vn)

The path is said to be closed if v0 =vn

## Simple & Complex Path

## Connected Graph

A graph is said to be connected if there is a path between any two of its nodes

## Tree Graph

A connected graph T without any cycles is called a tree graph or free tree, or simply a tree

This means in particular, that there is a unique simple path P between any two nodes u and v.

## Labelled Graph

A graph is to be labelled if its edges are assigned data.

## Weighted Graph

A graph G is said to be weighted if each edge e in G is assigned a non-negative numerical value W(e)

called the weight or length of e

## Multiple Edge

Distinct edges e and e’ are called multiple edges if they connect the same end points that is ,

if e = [u,v] and e’ = [u ,v]

## Loop

An edge is called loop if it has identical end points.

IPv4 – 32 Bits

IP v6- 128 Bits

## Multi Graph

Multi Graph is a graph consisting of multiple edges and loops

## Directed Graph

A directed graph G also called digraph in same as multigraph except that

each edge e is assigned a direction

e = (u,v)

## Complete Graph

A simple graph in which there exists an edge between every pair of vertices is called a complete graph.

It is also known as a universal graph or clique

- Adjacency Matrix Representation
- List Representation

Suppose G is a simple graph with m nodes, and suppose the nodes of G have been ordered and are called v1, v2, v3 ………..Vm. Then the adjacency matrix A= (aij) of the graph G is the mxm matrix defined as

1 – v1 is adjacent to vj

0 – otherwise

The graph is stored as a linked structure. The adjacency list stores information about only those edges that exists. The adjacency list contains a directory and a set of linked lists.

The directory contains one entry for each node of the graph. Each entry in the directory points to a linked list that represents the nodes that are connected to that node Each node of the linked list has three fields , one is node identifier , second is the link to the next field and the third is an optional weight field which contains the weights of the edges

int vertex;

Node next;

}

class graph{

private int v-count;

private Adj List arr;

}

class AdList{

private node stand

}