#include<iostream.h> #include<stdlib.h> #include<iomanip.h> const maxnum=30; struct lnode { int mark;//·ÃÎʱê¼Ç£¬0Ϊδ·ÃÎÊ£¬1Ϊ·ÃÎʹý int ivex,jvex;//¸Ã±ßÒÀ¸½µÄÁ½¸ö¶¥µãµÄλÖà struct lnode *ilink,*jlink;//·Ö±ðÖ¸ÏòÒÀ¸½ÕâÁ½¸ö¶¥µãµÄÏÂÒ»Ìõ±ß };//±ß½áµã struct vnode { int data; lnode *edge;//Ö¸ÏòÒÀ¸½¸Ã¶¥µãµÄµÚÒ»Ìõ±ß };//½áµã struct ggraph { vnode adj[maxnum]; int vexnum;//µ±Ç°¶¥µãÊý int edgenum;//µ±Ç°±ßÊý };//ͼ struct ssqueue { int data[30]; int f,r; };//˳ÐòÁÐ /*==================================================================*/

class graph { ggraph *g; lnode *p[450];//°´ÊäÈë˳Ðò´æ·Å±ß lnode *p1[450];//°´·ÃÎÊ˳Ðò´æ·Å±ß£¨Éî¶È£© lnode *p2[450];//°´·ÃÎÊ˳Ðò´æ·Å±ß£¨¹ã¶È£© ssqueue *queu; int visit[maxnum];//½áµã·ÃÎʱê¼Ç£¬0Ϊδ·ÃÎÊ£¬1Ϊ·ÃÎʹý public: graph(); void ddisplay(int);//Éî¶ÈÓÅÏȱéÀú void bdisplay(int);//¹ã¶ÈÓÅÏȱéÀú }; /*=================================================================*/

graph::graph() { g=new ggraph; queu=new ssqueue; queu->f=queu->r=-1; cout<<"²»Öظ´ÊäÈë±ß,ÀýÈç(a,b)Óë(b,a)ΪͬһÌõ±ß"<<endl; cout<<"ͼ¶¥µã×ÜÊý(²»³¬¹ý30):"; cin>>g->vexnum; cout<<"ͼ±ß×ÜÊý:"; cin>>g->edgenum; for(int i=0;i<g->vexnum;i++) { g->adj[i].data=i;//³õʼ¶¥µãÖµ g->adj[i].edge=NULL;//³õʼ»¯Ö¸Õë visit[i]=0; } for(int k=0;k<g->edgenum;k++) { int v1,v2; lnode *pp; cout<<"ÊäÈëµÚ"<<k+1<<"Ìõ±ß:"; cin>>v1>>v2; pp=new lnode; p[k]=new lnode; pp->ivex=v1-1; pp->jvex=v2-1; pp->mark=0; /*-----------------------*/ p[k]->ivex=v1-1; p[k]->jvex=v2-1; p[k]->ilink=NULL; p[k]->jlink=NULL; p[k]->mark=0; /*----------------------*/ pp->ilink=g->adj[v1-1].edge; g->adj[v1-1].edge=pp; pp->jlink=g->adj[v2-1].edge; g->adj[v2-1].edge=pp; } } /*==============================================================================*/

void graph::ddisplay(int m=2) { static int k=0; static int i; int j; i=m; while(visit[i]==0) { cout<<i+1<<" "; visit[i]=1; for(j=0;j<g->edgenum;j++) {//²éÕҸýáµãµ«Î´±»·ÃÎʹýµÄ if(p[j]->mark==1) continue; else {//ÅжϸñßÄĸö½ÓµãÊǸձ»·ÃÎʹýµÄ£¬½«Î´±»·ÃÎʹýµÄ½áµãÖµ¸³Óèi if(p[j]->ivex==i&&visit[p[j]->jvex]==0) { p1[k]=new lnode; p1[k++]=p[j]; p[j]->mark=1; i=p[j]->jvex; break; } else if(p[j]->jvex==i&&visit[p[j]->ivex]==0) { p1[k]=new lnode; p1[k]->ivex=p[j]->jvex; p1[k]->jvex=p[j]->ivex; k++; p[j]->mark=1; i=p[j]->ivex; break; } else//Èç¹û²»ÊÇËùÒªÇóµÄ±ß£¬¼ÌÐø²éÕÒ continue; }//else }//for if(visit[i]==1) {//Èôiδ±»¸üУ¬ËµÃ÷º¬¸Ã½áµã±ß¶¼±»·ÃÎʹý£¬Ôò²éÕÒÆäËû½áµãµÄÇé¿ö for(j=0;j<g->edgenum;j++) {//²éÕÒº¬Óб»·ÃÎʹýµÄ½áµãµÄ±ßµ«¸Ã±ßÊÇδ±»·ÃÎʹýµÄ±ß if(p[j]->mark==1) continue; else {//ÅжÏÄĸö½áµãÊDZ»·ÃÎʹýµÄ£¬½«Î´±»·ÃÎʹýµÄ½áµãÖµ¸³Óèi if(visit[p[j]->ivex]==1&&visit[p[j]->jvex]==0) { p1[k]=new lnode; p1[k++]=p[j]; p[j]->mark=1; i=p[j]->jvex; break; } else if(visit[p[j]->jvex]==1&&visit[p[j]->ivex]==0) { p1[k]=new lnode; p1[k]->ivex=p[j]->jvex; p1[k]->jvex=p[j]->ivex; k++; p[j]->mark=1; i=p[j]->ivex; break; } else//Èç¹ûÁ½¸ö½áµã¶¼Î´±»·ÃÎʹý£¬¼ÌÐø²éÕÒ continue; }//else }//for }//if }//while cout<<endl; cout<<"Éî¶È±éÀúÉú³ÉÊ÷µÄ±ß"<<endl; for(int k1=0;k1<k;k1++) { //cout<<"<"<<p1[k1]->ivex+1<<","<<p1[k1]->jvex+1<<">"<<endl; cout<<"("<<p1[k1]->ivex+1<<","<<p1[k1]->jvex+1<<")"<<endl; } } /*===================================================================================*/

void graph::bdisplay(int m=2) { static int j; j=m; static int l=0; for(int k=0;k<g->edgenum;k++) p[k]->mark=0; for(int kk=0;kk<g->vexnum;kk++) visit[kk]=0; visit[j]=1; queu->r++; queu->data[queu->r]=j; while(queu->f!=queu->r) { queu->f++; j=queu->data[queu->f]; cout<<j+1<<" "; for(int k=0;k<g->edgenum;k++) { if(p[k]->mark==1) continue; else { if(p[k]->ivex==j&&visit[p[k]->jvex]==0) { p2[l]=new lnode; p2[l]->ivex=j; p2[l]->jvex=p[k]->jvex; l++; queu->r++; queu->data[queu->r]=p[k]->jvex; visit[p[k]->jvex]=1; p[k]->mark=1; } else if(p[k]->jvex==j&&visit[p[k]->ivex]==0) { p2[l]=new lnode; p2[l]->ivex=j; p2[l]->jvex=p[k]->ivex; l++; queu->r++; queu->data[queu->r]=p[k]->ivex; visit[p[k]->ivex]=1; p[k]->mark=1; } else continue; }//else }//for }//while cout<<endl; cout<<"¹ã¶È±éÀúÉú³ÉÊ÷µÄ±ß:"<<endl; for(int ll=0;ll<l;ll++) { //cout<<"<"<<p2[ll]->ivex+1<<","<<p2[ll]->jvex+1<<">"<<endl; cout<<"("<<p2[ll]->ivex+1<<","<<p2[ll]->jvex+1<<")"<<endl; } } /*============================================================================*/

void main() { int m; graph a; cout<<"ÊäÈ뿪ʼ½áµã:"<<endl; cin>>m; cout<<"Éî¶ÈÓÅÏȱéÀú:"<<endl; a.ddisplay(m-1); cout<<"¹ã¶ÈÓÅÏȱéÀú:"<<endl; a.bdisplay(m-1); }