Graph in DSA are quite easy for basics just remember every thing is graph if it has nodes and edges

Now in above image you can see two representation of a graph

• Undirected Graph

• Directed Graph

• Weighted graph

• Cyclic Graph

• Acyclic Graph

Intuition :

Consider it as a state now think of all the cities as node and roads as edge now

• If you can move on road from going cityX → cityY and cityY → cityX then it could mean graph is undirected graph because of those undirected edges

• If you can go from cityX → cityY but if cityY → cityX is not possible then it means it’s undirected graph

• Now if you have to pay taxes to travel on roads then it means a weighted edge or graph is a weighted graph

• And if you go like cityX → cityY → cityZ → cityX : it means you can reach back to cityX without touching other cities twice A cyclic graph is here ( in above figure there are cycles in undirected graph but for directed one it’s not forming a single cycle )

• If no cycles then Acyclic graph

So you can see whatever it name suggests just add that attribute to edge or node and graph becomes that

Degree of graph

$$graphDegree = \sum_{i=start}^{end} nodeDegree$$

So here nodeDegree means number of edges connected to ith node

For Directed Graph it could be said as

• Indegree : for incoming edge to node

• outdegree : for outgoing edge to node

Example :

How we take input and store graphs ?

Adjacency Matrix :

// For Weighted , undirected graph
{
  int numberOfNodes = 0;
  cin >> numberOfNodes;

  vector<int> adjMatrix[numberOfNodes];

  int numberOfEdges = 0;
  cin >> numberOfEdges;

  for (int i = 0; i < numberOfEdges; i++)
  {
    // input in format startingNodeOfEdge , ending node of edge , weight of edge
    int starting, ending, weight;  // for unweighted graph, edge weight is assumed 1
    cin >> starting >> ending >> weight;

    adjMatrix[starting][ending] = weight;
    adjMatrix[ending][starting] = weight; // if it is a directed graph then we will not do this
  }
}

Analysis

Time Complexity : O(E)

Space Complexity : O(N²)

Adjacency Lists :

Here we store a vector mapped to every node storing the info about which nodes are connected to which node

{
  // undirected and unweighted graph
  int numberOfNodes = 0;
  cin >> numberOfNodes;

  vector<vector<int>> adjList(numberOfNodes);

  int numberOfEdges = 0;
  cin >> numberOfEdges;

  for (int i = 0; i < numberOfEdges; i++)
  {
    // input in format startingNodeOfEdge , ending node of edge
    int starting, ending; 
    cin >> starting >> ending;

    adjList[starting].push_back(ending);
    adjList[ending].push_back(starting);  // if it is a directed graph then we will not do this
  }
}

Implement adjList for weighted graphs

Hint ????

For a weighted graph instead of mapping nodes with each node we could have mapped it with pair of node and it’s weight

---

Traversal Techniques

Note : Just remember if applying graph you would need an Array to track visited nodes a queue or a stack

Breadth First Search

Focus on word breadth !

It means

• if we arrive at any node then we will go through each and every neighbour node first say neighbours are at level 1

• then we get back to first neighbour

• Now we apply step one with assuming the first neighbour at level 1 is our starting node

• We travers all node at level 2 now when done

• when we traverse back we go back to the second neighbour of level 1

---

to implement BFS we use queue we can easily implement this using queue

   vector<int> bfsOfGraph(int V, vector<int> adj[]) {
        //adjList is given
        queue<int> q;  // initialized empty queue

        vector<bool> visited(V,false);
        vector<int> ans; // recording order in which we visited all nodes

        // action for starting  node
        // here '0' is our starting node
        q.push(0);  
        ans.push_back(0); 

        // tracking whle queue is not empty 
        // It will cover all connected nodes 
        // for disconnected graphs we may have to attempt this process multiple times
        while(!q.empty()){
            int currNode = q.front(); // recording node at front of queue : node which was oldest in the queue

            q.pop(); // now remove that node from queue
            visited[currNode] = true; // mark that node visited

            // below loop will check all the nodes connected to currNode
            // if any adjNode to currNode is not visited then push it to queue
            // for order of path insert it to ans too.
            for(auto it:adj[currNode]){
                if(!visited[it]){
                    q.push(it);
                    ans.push_back(it);
                }
            }
        }

        return ans;
    }