CODEWITHSUNDEEP
c++graphnodes
user3747190
user3747190

Reputation: 1707

C++ Find a node with zero in-degree in graph

I have implemented a graph using map

map<char,vector<char> > M;

Now, I am getting edges one by one and I am pushing them into graph like this

addEdge(char a,char b){
M[a].push_back(b);
}

I want to find the all the nodes with zero in degree. What can be the most efficient way to do this?

Upvotes: 0

Views: 1841

Answers (3)

user3747190
user3747190

Reputation: 1707

I think if we take another map 'indegree' as shown in the following code, and increase the count, if the character appear as the terminating end of edge, then we can find the node with indegree 0.

map<char,vector<char> > M;
map<char,int> indegree;     
void addEdge(char a,char b){    
        M[a].push_back(b);                  
        indegree[b]++;
}
void show(){
        for(map<char,vecotr<char> > :: iterator it=M.begin();it!=M.end();it++){
                if(indegree[it->first]==0)
                        cout<<it->first<<endl;
        }
}

Another method will be to predefine an array of size 256, and follow the same procedure as above.

map<char,vector<char> > M;
int arr[256]={0};
void addEdge(char a,char b){    
        M[a].push_back(b);                  
        arr[b]++;
}
void show(){
        for(map<char,vecotr<char> > :: iterator it=M.begin();it!=M.end();it++){
                if(arr[it->first]==0)
                        cout<<it->first<<endl;
        }
}

Upvotes: 0

Jakub
Jakub

Reputation: 573

You cannot have nodes with zero degree in a graph represented by a data structure containing only edges. So if your graph is fully described by M[], you are guaranteed to have no nodes of zero degree.

Upvotes: 0

Hetzroni
Hetzroni

Reputation: 2174

Create a vector<char> L which will store the final nodes.

  1. Initiate it to contain all the nodes.
  2. For each edge (a,b): If b is in L, remove it from L.

Upvotes: 1

Related Questions