采用深度优先搜索-DFS遍历图

相关概念

连通：���向图中的两个顶点可互相到达

连通图：图中任意两顶点均可互相到达

连通分量：极大连通子图

强连通：有向图中的一个顶点可到达另一个顶点

连通图：图中任意两顶点都强连通

连通分量：极大强连通子图

遍历实现

1.用邻接矩阵实现

const int maxn=100;const int inf=100000000;int G[maxn][maxn];bool isvisit[maxn]={false};int num;void DFS(int a,int deep){    isvisit[a]=true;//改为已访问    for(int i=0;i        if(isvisit[i]==false&&G[a][i]!=inf)        //访问离a最近的一个未被访问且与a有关系的结点        DFS(i,deep+1);    }}void DFStrave(){    for(int i=0;i        if(isvisit[i]==false)        DFS(i,1);    }}false};vector    isvisit[a]=true;    //遍历顶点a的邻接列表-即相关的边    for(int i=0;i        int value=node[a][i];        if(isvisit[value]==false)        DFS(value,deep+1);    }}void DFStrave(){    for(int i=0;i    int cnum;    string head;};int G[maxn][maxn];//用邻接表法实现对图的存储int V[maxn];//记录点权：要找头目bool isvisit[maxn]={false};//记录是否已访问int group,limit,value;int num=0;string vertex1,vertex2;//顶点map  if(stringToInt.find(str)!=stringToInt.end()){//再次传入，直接返回即可      return stringToInt[str];//返回编号}else{//第一次传入，为其编号        stringToInt[str]=num;//第一个编号为0        intToString[num]=str;//同时为其相反操作编号        return num++;//记录总个数:先返回编号再++}}void DFS(int index,int &head,int &numMemeber,int &sumValue){    numMemeber++;//记录成员    isvisit[index]=true;    if(V[index]V[head])    head=index;//更新，找点权最大的    for(int i=0;i        if(G[index][i]0){            sumValue+=G[index][i];            G[index][i]=G[i][index]=0;//无向图防止乱加            if(isvisit[i]==false)        DFS(i,head,numMemeber,sumValue);        }    }}void DFStrave(){    for(int i=0;i        int head=i,numMemeber=0,sumValue=0;        if(isvisit[i]==false){            DFS(i,head,numMemeber,sumValue);        }        //边算值边判断        if(numMemeber2&&sumValuevalue){            crimes[intToString[head]]=numMemeber;//犯罪集团信息        }    }}int main(){    cingroup>>limit;    for(int i=0;i        cin>vertex1>>vertex2>>value;        int ver1=change(vertex1);        int ver2=change(vertex2);        //记录点权        V[ver1]+=value;        V[ver2]+=value;        //记录边权：相当于创建一个无向图        G[ver1][ver2]+=value;        G[ver2][ver1]+=value;    }    DFStrave();    cout