Table of contents
1.
Introduction
1.1.
Problem Statement
1.2.
Sample Examples
2.
Approach
2.1.
Algorithm
2.2.
Implementation
2.2.1.
Time Complexity
2.2.2.
Space Complexity
3.
Frequently Asked Questions
3.1.
What is a Bipartite Graph?
3.2.
What is a weighted Graph?
3.3.
What is the difference between connected and non-connected components of a Graph?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

Find the largest subset of Graph Vertices with Edges of 2 or more colors

Author Ayush Mishra
1 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

A graph is a type of non-linear data structure made up of vertices and edges. The vertices are also known as nodes, and edges are lines or arcs that connect any two nodes in the graph.

Formally, a graph is a pair of sets (v, e), where e is the set of edges connecting the pairs of vertices and v is the set of vertices.

This blog will discuss the problem of finding the largest subset of Graph Vertices with Edges of 2 or more colors. We will discuss this article in detail. Let's start going!

Find the largest subset of Graph Vertices with Edges of 2 or more colors

Problem Statement

In this problem, we are given a complete undirected graph with N nodes or vertices in which the edges of the graph are colored. We are given a graph in the form of an adjacency matrix graph[][], where graph[i][j] is the color of the edge from vertex i to vertex j.

Sample Examples

Example 1:

Input: 

graph[][3]= {{0,2, 1},
		   {2, 0, 3},
		   {1, 3, 0}}                

Output: 

3

 

Explanation: All the nodes in the adjacency matrix have different color edges than one.

Sample Example

Example 2:

Input:

 graph[][3]= {{0,2, 1},
		   {2, 0, 3},
		   {1, 1, 0}} 			                

Output:

 1

 

Explanation: Only one node in the adjacency matrix has different color edges than one.

Sample Example

Approach

We will traverse each and every node of the adjacent matrix and remove all the nodes having the same edge colors connected with different nodes. After removing all the nodes, return the count of the nodes having different color edges.

Algorithm

✔️ Create an adjacent matrix graph[i][j].

✔️ Insert the vertices in a set.

✔️ If the size of the set is 1, return 1.

✔️ Traverse the Adjacent Matrix, and if the row and column index is not the same, insert them into a new set.

✔️ If the size of the new set is 1, remove the row index from the old set and return the size of the set.

Implementation

C++ Program to find the largest subset of Graph Vertices with Edges of 2 or more colors.

#include <bits/stdc++.h>
using namespace std;

int largest_subset(int graph[][3])
{
set<int> v;
for (int i = 0; i < 3; i++)
    {
    v.insert(i);
    }
while (!v.empty())
{
	if (v.size() == 1)
    	{
   	 		return 1;
    	}
	bool removed= false;
	for (int x : v)
		{
			set<int> val;
			for (int z : v)
				{
					if (z != x)
						{
							val.insert(graph[x][z]);
						}
				}
			if (val.size() == 1)
				{
					v.erase(x);
					removed = true;
					break;
				}
			}
		if (!removed)
			{
				break;
			}
	}

	return v.size();
}

int main()
{
int graph[][3] = {{0,2,1}, {2,0,3}, {1,3,0}}
		     
cout <<largest_subset(graph)<<endl;
return 0;
}
You can also try this code with Online C++ Compiler
Run Code

Output:

 3

Time Complexity

The time complexity of the above approach for the problem of finding the largest subset of graph vertices with edges of 2 or more colors is O(n^3), as we have to visit every node of the graph matrix.

Space Complexity

The space complexity of the above approach for the problem of finding the largest subset of graph vertices with edges of 2 or more colors is O(n), as we are using extra space for storing the vertices in the set.

Frequently Asked Questions

What is a Bipartite Graph?

A graph is a bipartite graph if and only if it can be colored in two ways. It is bipartite if and only if every edge belongs to an odd number of bonds, which are minimal subsets of edges whose removal increases the number of graph components.

What is a weighted Graph?

Weighted graphs are graphs with weighted edges that represent the value of a variable. For Example, the weight of an edge in an airline route graph could represent the cost of travel from one city to another.

What is the difference between connected and non-connected components of a Graph?

Every vertex in a connected graph has at least one path to every other vertex, whereas every vertex in a non-connected graph may or may not be connected to every other vertex.

Conclusion

Congratulations on finishing the blog! We have studied the problem of finding the largest subset of graph vertices with edges of 2 or more colors.

We hope this blog has helped you enhance your knowledge regarding the topic of Graph data structure, and if you want to learn more, then you can check articles on:-

1. Introduction to  Graph Theory

2. Application of graph data structure

3. Depth First Search Problem

4. Breadth First Search (BFS).

Please refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem Design, etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Please do upvote our blogs if you find them helpful and informative!

Happy learning!

Live masterclass