Do you think IIT Guwahati certified course can help you in your career?
Introduction🧑🏻🎓
A graph is any non-linear data structure made up of vertices and edges. In a graph, the edges are the lines linking any two nodes. The vertices are occasionally referred to as nodes. Formally a graph is made up of a collection of vertices (V) and a set of edges ( E ). The graph is represented as (E, V).
The following article will help you to find the maximum edges we can add to a directed acyclic graph to remain a directed acyclic graph. Let’s go! 🫡
Directed Acyclic Graph (DAG)🤔
A collection of vertices connected by edges is referred to as a graph. Each edge in a directed graph has a direction from a start vertex to an end vertex. There are no directed cycles if we traverse in the direction of the edges and discover that no path forms any closed loops. It is a directed acyclic graph that has been created.
A DAG is topologically ordered, meaning that the start vertex of each edge appears sooner in the sequence than the ending vertex of each edge for each edge in the graph.
Topological sorting is a linear arrangement of the vertices along each directed edge where u comes before v(where u and v are the starting and ending vertex of an edge, respectively). Topological sorting is not possible for a graph if it is not a DAG.
The above-given diagram can be considered an ideal example of a DAG.
We are given a DAG and must determine the maximum number of edges we can add to it before the new graph ceases to be a DAG. This means that the reformed graph must have the greatest number of edges possible because adding even one edge will result in a cycle in the graph.
Example
If you add certain edges to the graph above, the remaining graph will be directed acyclic (DAG). Those edges can be- 0->4, 0->2, 0->5, 3->1, 3->5, 4->1, 4->2, and 1->5.
Algorithm👨🎓
To avoid creating a cycle, we just inserted all the edges in one direction. This is the approach to answering this question. We arrange all of our nodes in topological order and, if necessary, add edges connecting each node to every other node on the right.
How can we claim that the graph can add no additional edges? We have already added all possible edges from left to the right, so if we want to add another edge, we must make it from right to left. However, if we add an edge from right to left, we will undoubtedly create a cycle because its opposite edge from left to right has already been added to the graph.
The process for finding a solution is as follows: we consider the nodes in topological order and create any edges that are missing from left to right.
DRY RUN
After sorting our input graph in topological order we get the following representation-
For every node keep adding the edges in one direction until all the nodes are covered as shown below in the figures for node 4 and print them one by one.
The extra edges added are 4->5, 4->2, and 4->3.
Repeat a similar procedure for the leftover nodes.
The final result will be-
4-2, 4-5, 4-3, 5-3, 5-1, 2-0, 2-1, 0-3, 0-1
Every node has been given a different color in the illustration for a clear understanding.
Implementation
C++
#include<bits/stdc++.h>
using namespace std;
/*function for adding an edge*/
void addEdge(int se, int ee,vector<int>graph[]){
graph[se].push_back(ee);
}
/*bfs traversal for obtaining a topologically sorted order*/
void bfs(vector<int>graph[],int i,vector<bool>&visited, stack<int>&st){
visited[i]=true;
for(auto j:graph[i]){
if(!visited[j])
bfs(graph,j,visited,st);
}
st.push(i);
}
/*getting the topological sort and building the array*/
vector<int>topoSort(vector<int>graph[],int vertices){
stack<int>st;
vector<bool>visited(vertices,false);
for(int i=0;i<vertices;i++){
if(!visited[i])
bfs(graph,i,visited,st);
}
vector<int>t(vertices);
int i=0;
while(!st.empty()){
t[i++]=st.top();
st.pop();
}
return t;
}
void getMaxEdges(vector<int>graph[],int vertices){
vector<int>t=topoSort(graph,vertices);
vector<bool>visited(vertices,false);
for (int i = 0; i < t.size(); i++) /*traversing the topological sorted array*/
{
int t1 = t[i];
for (auto j = graph[t1].begin(); j != graph[t1].end(); j++)
visited[*j] = true;
for (int j = i + 1; j < t.size(); j++) /*see the rest array for finding edges*/
{
if (!visited[t[j]]) /*if the element is not adjacent then add edge*/
cout << t1 << "->" << t[j] << " ";
visited[t[j]] = false;
}
}
}
int main(){
/*building the graph*/
int V=6;
vector<int>graph[V];
add(0, 1,graph);
add(0, 3,graph);
add(1, 2,graph);
add(3, 2,graph);
add(2, 5,graph);
add(3, 4,graph);
add(4, 5,graph);
getMaxEdges(graph,V);
return 0;
}
You can also try this code with Online C++ Compiler
import java.util.*;
public class Graph {
int vertices; /* No. of vertices*/
ArrayList<ArrayList<Integer>> adjc; /* adjcacency list*/
/* array to store indeg of vertices*/
int[] indeg;
/* Constructor of graph*/
Graph(int v)
{
this.vertices = v;
indeg = new int[vertices];
adjc = new ArrayList<>(vertices);
for(int i = 0; i < vertices; i++)
{
adjc.add(new ArrayList<Integer>());
indeg[i] = 0;
}
}
/* Utility function to add edge*/
public void addingEdge(int v,int w)
{
adjc.get(v).add(w);/* Add w to v's list.
/* increasing inner degree of w by 1*/
indeg[w]++;
}
/* Main function to print maximum edges that can be added*/
public List<Integer> topologicalSort()
{
List<Integer> topological = new ArrayList<>(vertices);
Queue<Integer> qu = new LinkedList<>();
/* In starting push all node with indeg 0*/
for(int i = 0; i < vertices; i++)
{
if(indeg[i] == 0)
{
qu.add(i);
}
}
while(!qu.isEmpty())
{
int t=qu.poll();
/* push the node into topological list*/
topological.add(t);
/* reducing indeg of adjcacent vertical*/
for(int j: adjc.get(t))
{
indeg[j]--;
/* if indeg becomes 0, just push*/
/* into quueue*/
if(indeg[j] == 0)
{
qu.add(j);
}
}
}
return topological;
}
/* The function prints all edges that can be*/
/* added without making any cycle*/
/* It uses recursive topologicalSort()*/
public void maxEdgeAddn()
{
boolean[] visited = new boolean[vertices];
List<Integer> topo=topologicalSort();
/* looping for all nodes*/
for(int i = 0; i < topo.size(); i++)
{
int t = topo.get(i);
/* In below loop we mark the adjcacent node of t*/
for( Iterator<Integer> j = adjc.get(t).listIterator();j.hasNext();)
{
visited[j.next()] = true;
}
for(int j = i + 1; j < topo.size(); j++)
{
/* if not marked, then we can make an edge*/
/* between t and j*/
if(!visited[topo.get(j)])
{
System.out.print( t + "-" + topo.get(j) + " ");
}
visited[topo.get(j)] = false;
}
}
}
/* Driver code to test above methods*/
public static void main(String[] args)
{
/* Create a graph given in the above diagram*/
Graph g = new Graph(6);
g.addingEdge(5, 2);
g.addingEdge(5, 0);
g.addingEdge(4, 0);
g.addingEdge(4, 1);
g.addingEdge(2, 3);
g.addingEdge(3, 1);
g.maxEdgeAddn();
return ;
}
}
You can also try this code with Online Java Compiler
class Graph:
def __init__(self, vertices):
# No. of vertices
self.vertices = vertices
# Pointer to a list containing
# adjcacency list
self.adjc = [[] for i in range(vertices)]
# verticesector to store indegree of vertices
self.indegree = [0 for i in range(vertices)]
# Utility function to add edge
def add_edge(self, v, w):
# Add w to v's list.
self.adjc[v].append(w)
# Increasing inner degree of w by 1
self.indegree[w] += 1
# Main function to print maximum
# edges that can be added
def topologicalSort(self):
topological = []
q = []
# In starting append all node
# with indegree 0
for i in range(self.vertices):
if (self.indegree[i] == 0):
q.append(i)
while (len(q) != 0):
t = q[0]
q.pop(0)
# Append the node into topological
# vector
topological.append(t)
# Reducing indegree of adjcacent
# vertices
for j in self.adjc[t]:
self.indegree[j] -= 1
# If indegree becomes 0, just
# append into queue
if (self.indegree[j] == 0):
q.append(j)
return topological
# The function prints all edges that
# can be added without making any cycle
# It uses recursive topologicalSort()
def maximumEdgeAddtion(self):
al_visit = [False for i in range(self.vertices)]
topo = self.topologicalSort()
# Looping for all nodes
for i in range(len(topo)):
t = topo[i]
# In below loop we mark the
# adjcacent node of t
for j in self.adjc[t]:
al_visit[j] = True
# In below loop unmarked nodes
# are printed
for j in range(i + 1, len(topo)):
# If not marked, then we can make
# an edge between t and j
if (not al_visit[topo[j]]):
print(str(t) + '-' +
str(topo[j]), end=' ')
al_visit[topo[j]] = False
# Driver code
if __name__ == '__main__':
# Create a graph given in the
# above diagram
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)
g.maximumEdgeAddtion()
You can also try this code with Online Python Compiler
Time Complexity- Since we are using BFS hence the time complexity will be O(V+E).
Space Complexity- The space complexity will be O(V) for the extra list of marking the nodes.
We hope you understood everything about finding the maximum edges that can be added to a directed acyclic graph so that it remains a directed acyclic graph.🤗
Frequently Asked Questions
How do you represent a graph?
Three data structures—the adjacency matrix, adjacency list, and adjacency set—can each be used to represent a graph. One way to see an adjacency matrix is as a table with rows and columns. Row labels and column labels represent the nodes of a graph.
How can we check whether a graph is connected in C++?
We will attempt to explore every node in a network using a traversal technique to test the graph's connection. The graph is not linked if any nodes remain unvisited after the traversal is finished.
What are directed and undirected graphs?
Edges in directed graphs point from one end of the graph to the other. The edges in undirected networks merely link the nodes at each end.
What are cyclic and acyclic graphs?
If a network has a cycle—a continuous set of nodes without any repeating nodes or edges that connect back to itself—it is said to be cyclic. Acyclic graphs are those without cycles.
What are weighted and unweighted graphs?
Each edge has a "weight" if a graph is weighted. The weight might, for instance, be used to reflect the trip time or cost and the distance between two locations.
Conclusion
This article taught us how to find the maximum edges we can add to a directed acyclic graph to remain a directed acyclic graph. We began with a brief introduction to the graphs, followed by an algorithm and detailed code example. After reading about finding the maximum edges that can be added to a directed acyclic graph so that it remains a directed acyclic graph, refer to Learn Graphs 1s, Introduction to Graphs, Learn Graphs 2, and Advanced Graphs for CP for a deeper understanding of graphs.
7+ registered 
