C++使用地图</p> <pre><code>map<char,vector<char> > M; </code></pre> <p>现在，我越来越边缘一一图

Question

找到一个节点，在度为零我实现了一个图，我推入图中这样

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

我想找到度数为零的所有节点。什么才是最有效的方法呢？

Answer 1

我认为如果我们采取如以下代码中所示的另一地图“入度”，并增加计数，如果该字符显示为边缘的结束端，那么我们可以找到与入度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; 
     } 
}  

另一种方法是预定义一个大小为256的数组，并按照上述相同的步骤。

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; 
     } 
}  

Answer 2

您不能在由仅包含边的数据结构表示的图中使零度的节点。 因此，如果您的图形完全由M []描述，则可以保证没有零度的节点。

Answer 3

创建将存储最终节点的vector<char> L。

1. 启动它以包含所有节点。
2. 对于每个边（a，b）：如果b在L中，请将其从L中删除。