What is Graph and it's Types:

Defination

Graph = (V, E)
A Graph has Vertices(arbitary labels) connected by Edges.
```
V = set of Vertices
E = set of Vertices pairs
```
#### Types of Graphs:

There are two types of Graphs: ##### 1.Undirected Graph:

  - E is unordered 
  - if (V1, V2) ∈ E  ==> (V2,V1) ∈ E
  - if you can reach V1 from V2 then you can reach V2 from V2

##### 2.Directed Graph:

  - E is ordered
  - if (V1, V2) ∈ E  =/=> (V2,V1) ∈ E
  - if you can reach from V1 to V2 doesn't automatically 
    imply you can reach V1 from V2

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_edge(1,2)
G.add_edge(1,3)
G.add_edge(2,3)
nx.draw(G, with_labels=True)
print("Undirected Graph")
plt.show()

Undirected Graph

D = nx.DiGraph()
D.add_edge(1,2)
D.add_edge(1,3)
D.add_edge(3,2)
D.add_edge(2,3)
nx.draw(D, with_labels = True)
print("Directed Graph")
plt.show()

Directed Graph

Represenatations of Graph:

1. Adjacency Lists:

    -Using dict/hashtable to represent Graph
    -Keys are the vertices and Values are it's neighbours
    -Analysis:
        - Memory = O(V + E)
        - Time: -to find a neighbour: O(E)
    - Example in Real Life: Storing friends of a person on social media platform

2. Implicit Lists:

    - Neighbours are result of function f(V)
    - Analysis:
        - Memory = Zero Space or No space occupied
        - Time = O(f(V)) i.e dependent on time function requires
     - Example in Real Life: Rubriks cube

3. Object Oriented variation:

    - Each Vertex is object
    - ADL: v.neighbours = list of neighbours i.e ADL[v]
    - Implicit List: v.neighbours = f(V)

4. Incidence Lists:

    - Edges are objects
        e.a and e.b ==> edge e connects vertex 'a' with 'b'
    - u.edges = list of all edge objects from u
    -Analysis:
        -Memory = O(V*E + E)
        -Time = to find neighbour: O(E)

'''
    Implicit lists: Example Graph
    Imagine a graph in which the neighbours are defined as the multiple of Vertex
    -if directed: then,multiple as well as factors are neighbours
    -if undirected: then, multiple are neigbours while factors are not
'''

def check_neighbours(V,E,directed = False):
    if directed:
        return (E%V == 0)
    return ((E%V == 0) or (V%E == 0))

check_neighbours(4,2)

True

'''
Object Oriented Variation for Graph
'''
class GraphNode:
    def __init__(self,label, directed = False):
        self.neighbours = set()
        self.label = label
        self.directed = directed
    
    def add_neighbours(self, node):
        if not self.directed:
            node.neighbours.add(self)
        self.neighbours.add(node)
        
    def print_label(self):
        print(self.label)
    
    def print_neighbours(self):
        for i in self.neighbours:
            i.print_label()
#         for i in range(len(self.neighbours)):
#             self.neighbours[i].print_label()

def take_input():
    size = int(input())
    start = int(input())
    edges = int(input())
    ADL = {i:[] for i in range(size)}
    for i in range(edges):
        x,y = list(map(int,input().split()))
        ADL[x].append(y)
        ADL[y].append(x)
    print(ADL)
    return (start,ADL)

BFS:

Breadth First Search:

Find a vertex given a graph.
In BFS, we first check all neighbours before moving on to neighbours of neighbours i.e All level 0 vertex is checked before moving on level 1

Algorithm:

(Queue based approach)

-Step1: Define a queue      
-Step2: Intiliaze it with level 0 vertex or start vertex
-Step3: Define a list/set to store already visited vertex
-Step4: Repeat this step till queue is empty:
        -Step1: check all Neighbours of queue[0]
                -if not in visited list,add neighbour to the queue 
                - add the edge to ADL for current node and Add edge for current neighbour
        -Step2: remove queue[0]

def BFS(s,ADL):
    level = {s:0}
    parent = {s:0}
    i = 1
    frontier = [s]
    while frontier:
        next = []
        for u in frontier:
            for v in ADL[u]:
                if v not in level:
                    level[v] = i
                    parent[v] = u
                    next.append(v)
        frontier = next
        i += 1
    print(level)
    print(parent)
start,ADL = take_input()
BFS(start,ADL)

3
1
2
1 2
0 1
{0: [1], 1: [2, 0], 2: [1]}
{1: 0, 2: 1, 0: 1}
{1: 0, 2: 1, 0: 1}