求无向图的连通分量 #include #define MAX_VEX_NUM 20 using namespace std; class NODE//记录孩子结点的序号等信息 { public: NODE(); int child; NODE * next; }; NODE::NODE() { } child=0; next=NULL; class VexNode//记录顶点信息 { public: }; VexNode(); bool visited; char vexname; NODE * firstchild; VexNode::VexNode() { } visited=false; firstchild=NULL; class VexBox//储存图的邻接表 { public: VexBox(); VexNode vexbox[MAX_VEX_NUM]; int vexnum; }; VexBox::VexBox() { 

vexnum=0; } class CSTreeNode//生成树节点 { public: CSTreeNode(); char name; CSTreeNode *lchild,*rsibling; }; CSTreeNode::CSTreeNode() { } lchild=rsibling=NULL; class Graph { public: Graph(); void ShowGraph();//接口函数 private: void GetVexList();//得到顶点信息 void GetChild();//得到各个顶点的孩子信息 void DFSForest(); void DFSTree(int ,CSTreeNode *); void Print();//输出图的顶点孩子信息 void PrintTree(); void InOrderPrintTree(CSTreeNode *);//中序输出生成树 VexBox l;//定义一个邻接表 CSTreeNode *root;//生成树根 }; Graph::Graph() { } root=NULL; void Graph::ShowGraph()//接口函数 { cout<<"ShowGraph Called !"<

PrintTree();//输出各连通分量 } void Graph::GetVexList()//得到顶点信息 { } cout<<"GetVexList Called !"<>name) { } l.vexbox[l.vexnum++].vexname=name; cin.clear(); void Graph::GetChild()//得到各个顶点的孩子信息 { cout<<"GetChild Called !"<>num) { newnode=new NODE; newnode->child=num; if((p=l.vexbox[i].firstchild)==NULL) { } { l.vexbox[i].firstchild=newnode; else while(p->next!=NULL) { } p=p->next; p->next=newnode; } } cin.clear(); } } void Graph::Print()//输出邻接表信息 { 

cout<<"Print Called !"<child].vexname<next; { } } void Graph::DFSForest()//深度优先遍历该图并建立连通分量的生成森林 { cout<<"DFSForest Called !"<name=l.vexbox[i].vexname;//当前节点名字赋给新的节点 if(root==NULL)//如果 root 未指向任何节点 { } else { } p=root=newnode; p->rsibling=newnode;//否则就把新开辟的节点挂在右兄弟上 p=p->rsibling;//p 指向新开辟的节点 DFSTree(i,p);//以 p 为根节点建立新树 } } } void Graph::DFSTree(int i,CSTreeNode *t)//左孩子右兄弟,左孩子右兄弟!!!在这纠结了半天 { bool first=true; l.vexbox[i].visited=true;//标记为已访问 NODE*q=l.vexbox[i].firstchild; CSTreeNode * newnode,*p; while(q!=NULL) 

{ if(l.vexbox[q->child].visited==false)//如果未被访问 { l.vexbox[q->child].visited=true; newnode=new CSTreeNode; newnode->name=l.vexbox[q->child].vexname; if(first)//孩子 { } t->lchild=newnode; p=newnode; first=false; else//兄弟 { } p->rsibling=newnode; p=p->rsibling; DFSTree(q->child,newnode); } q=q->next; } } void Graph::PrintTree()//调用 InOrderPrintTree()输出生成森林的相关信息 { } cout<<"PrintTree Called !"<name; InOrderPrintTree(p->lchild); cout<rsibling; void Graph::InOrderPrintTree(CSTreeNode *t)//递归遍历每一棵树 { } if(t==NULL) return; cout<name; InOrderPrintTree(t->lchild); InOrderPrintTree(t->rsibling);