Session 44: Graph 1

Original Session

Date: 20 Feb 2025

Topic: Graph

Concept: Non linear data structure consist of vertices and edges. Multiple nodes are connected.

Concept: Types of Graph.
Null Graph, Trivial Graph, Undirected Graph, Directed Graph, Connected Graph, Disconnected Graph, Regular Graph, Complete Graph, Cycle Graph, Cyclic Graph, Directed Acyclic Graph, Bipartite Graph, Weighted Graph

Concept: Represented by.

Matrix and Adjacency List.

Concept: BFS traversal.

Programs

1. Print adjacency list
   1. GFG here

      public List<List<Integer>> printGraph(int V, int edges[][]) {
              
              List<List<Integer>> ans = new ArrayList();
              
              for (int i=0; i<V; i++) {
                  ans.add(new ArrayList());
              }
              
              int rows = edges.length;
              for (int i=0; i<rows; i++) {
                      int start = edges[i][0];
                      int end = edges[i][1];
                     
                      ans.get(start).add(end);
                      ans.get(end).add(start);
              }
              
              return ans;
          }

2. BFS of graph
   1. GFG here

      public ArrayList<Integer> bfsOfGraph(int V, ArrayList<ArrayList<Integer>> adj) {
              // code here
              
              ArrayList<Integer> ans = new ArrayList();
              boolean[] visited = new boolean[V];
              Queue<Integer> q = new LinkedList();
              q.add(0);
              
              while(!q.isEmpty()) {
                  
                  int vertex = q.remove();
                  if (visited[vertex]) {
                      continue;
                  }
                  
                  visited[vertex] = true;
                  List<Integer> vertices = adj.get(vertex);
                  for(Integer i: vertices){
                      q.add(i);
                  }
                  ans.add(vertex);
              }
              
              return ans;
          }