数据结构-图的深度遍历和广度遍历-邻接矩阵-邻接表

structfun.h

//数据结构函数头文件 #include <stdio.h> #include <iostream> #include<string> using std::cout; using std::cin; using std::string; #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define INFINITY 65535//无穷大 typedef string ElemType; typedef string VertexType;//图顶点数据类型 typedef int EdgeType;//图边的数据类型 //定义一个数组队列 typedef struct Queue { int date[MAXSIZE]; int num; }; //数据结构-图----------------------------------------------------------------------------- //1、邻接矩阵（Adjacency Martix） //设置一个顶点数组vertex[],设置一个边数组arc[][] typedef struct { //图顶点数组 VertexType vertex[MAXSIZE]; //图边数组 EdgeType arc[MAXSIZE][MAXSIZE]; int vertexnum,arcnum; }AdjMarGraph; //2、邻接表（Adjacency List） //设置一个顶点数组vertex[],设置一个边的链表，顶点的next指向所对应的链表 typedef struct EdgeNode//边链表节点 { EdgeType arcVertex; int weight;//权值 EdgeNode *next; }EdgeNode; typedef struct//顶点数组 { VertexType vertex; EdgeNode *firstEdge; }VertexList[MAXSIZE]; typedef struct//图结构 { VertexList vlist; int numVertex,numArc; }AdjListGraph; //3、十字链表（Orthogonal->正交的 List） //设置一个顶点数组vertex[],设置一个边的链表，顶点的next指向所对应的链表 //链表节点 tailvex headvex headlink,taillink; 改成invex,outvex,outlink,inlink更好理解 //入顶点，出顶点，出链接，入链接 typedef struct OrthogonalLinkNode { EdgeType invex,outvex; OrthogonalLinkNode *outlink,*inlink; int weight;//边的权重 }OrthogonalLinkNode; //数组顶点节点 vertex 顶点 edgein 入边 edgeout 出边 typedef struct { VertexType vertex; OrthogonalLinkNode *edgein,*edgeout; }OrthogonalEdgeNode[MAXSIZE]; //十字链表结构 typedef struct { OrthogonalEdgeNode vertexlist; int numvertex,numedge; }OrthogonalListGraph; //4、无向图 邻接多重表结构Adjacency Multiple Table（邻接多重表就是一个顶点的多条边用链表链接） //ivex ilink jvex jlink (ivex jvex 边的两个顶点，ilink指向值与ivex相同的jvex的节点,jlink指向值与jvex相同的下一个节点。 typedef struct AMTEdgeNode//边链表节点 { VertexType iver,jver; bool visited;//是否被访问过 int weight;//权值 AMTEdgeNode *ilink,*jlink; }AMTEdgeNode; typedef struct//顶点数组 { VertexType vertex; AMTEdgeNode *firstEdge; }AMTVertexList[MAXSIZE]; typedef struct//图结构 { AMTVertexList vlist; int numVertex,numArc; }AdjacencyMultipleTableGraph; //1、邻接矩阵 //无向图的邻接矩阵 int CreateAdjMaxGraph(AdjMarGraph *amg); int AdjMarDepthFirstSearch(AdjMarGraph *amg,int f);//邻接矩阵深度遍历 int f为开始的结点 int AdjMarBreadthFirstSearch(AdjMarGraph *amg); int AMBFS(AdjMarGraph *amg); //2、邻接表 int CreateAdjListGraph(AdjListGraph *alg); int AdjListDepthFirstSearch(AdjListGraph *alg,int f);//邻接表深度遍历 int AdjListBreadthFirstSearch(AdjListGraph *alg);//邻接表广度遍历 //3、十字链表 int CreateOrthogonalListGraph(OrthogonalListGraph *olg); //4、邻接多重表结构 int CreateAdjacencyMultipleTableGraph(AdjacencyMultipleTableGraph *amtg);

structfun.cpp

#include<iostream> #include<stdio.h> #include<string> #include<sstream> #include"structfun.h" using std::cout; using std::cin; using std::string; using std::endl; using std::ostringstream; //图结构函数----------------------------------------------- //1、邻接矩阵 //图的邻接矩阵 int CreateAdjMaxGraph(AdjMarGraph *amg) { int i=0; amg->vertexnum=0; amg->arcnum=0; while(1)//输入顶点; { printf("请输入顶点，结束用#号："); /* scanf("%s",&amg->vertex[i]);*///string不能采用scanf,采用scanf必须先给字符串 //预先分配空间，然后采用amg->vertex[i][0]scanf采用的是字符数组的形式存储字符串。 //amg->vertex[i].resize(100); //scanf("%s",&amg->vertex[i][0]); cin>>amg->vertex[i]; if(amg->vertex[i]=="#") break; amg->vertexnum++; i++; } for(i=0;i<amg->vertexnum;i++)//初始化边值为0 for(int j=0;j<amg->vertexnum;j++) { if(i==j) amg->arc[i][j]=0; else amg->arc[i][j]=INFINITY; } //创建邻接矩阵图的边 while(1) { int v1,v2,value; printf("请输入图的边的顶点下标（v1,v2,value）结束输入（0,0,0）："); scanf("%d,%d,%d",&v1,&v2,&value); amg->arc[v1][v2]=value; amg->arc[v2][v1]=value;//无向图增加对等矩阵另外一边的值 if(!v1&!v2&!value) break; amg->arcnum++; } //输出图的邻接矩阵 printf("图的邻接矩阵:\n"); for(i=0;i<amg->vertexnum;i++) { printf("%s: ",amg->vertex[i].c_str()); for(int j=0;j<amg->vertexnum;j++) { printf("%d ",amg->arc[i][j]); if(j==amg->vertexnum-1) printf("\n"); } } return OK; } //->1图邻接矩阵的深度遍历 bool visited[MAXSIZE]; int AdjMarDepthFirstRecursion(AdjMarGraph *amg,int i)//递归(Recursion) { if(!visited[i]) printf("%s ",amg->vertex[i].c_str()); else return OK; visited[i]=true; for(int j=0;j<amg->vertexnum;j++) if(amg->arc[i][j]==1)//判断是否有路径 { printf("(%d,%d)",i,j); AdjMarDepthFirstRecursion(amg,j); } return OK; } int AdjMarDepthFirstSearch(AdjMarGraph *amg,int f)//邻接矩阵深度遍历 { for(int i=0;i<amg->vertexnum;i++) visited[i]=false; printf("邻接矩阵深度遍历:\n"); AdjMarDepthFirstRecursion(amg,f);//针对连通图，如果不是连通图就再使用循环 //for(int i=0;i<amg->vertexnum;i++) // AdjMarDepthFirstRecursion(amg,i); return OK; } //->2图邻接矩阵的深度遍历 Queue list;//定义一个全局数列 int AdjMarBreadthFirstRecursion(AdjMarGraph *amg,int i)//图邻接矩阵广度优先递归 { /*int list[MAXSIZE],intlist=0;*///不能直接用数组，要用队列数据结构 if(!visited[i]) printf("%s ",amg->vertex[i].c_str()); else return OK; visited[i]=true; for(int j=0;j<amg->vertexnum;j++) if(amg->arc[i][j]==1) { list.date[list.num]=j; list.num++; } for(int j=0;j<=list.num;j++) AdjMarBreadthFirstRecursion(amg,list.date[j]); return OK; }//递归方法 int AdjMarBreadthFirstSearch(AdjMarGraph *amg) { for(int i=0;i<amg->vertexnum;i++) visited[i]=false; list.num=0;//队列合计初始化 printf("广度优先遍历结果：\n"); AdjMarBreadthFirstRecursion(amg,2); return OK; } //广度优先遍历（不用递归） int AMBFS(AdjMarGraph *amg) { int i=0; for(i=0;i<amg->vertexnum;i++)//初始化访问标识数组 visited[i]=false; list.num=0;//队列合计初始化 printf("广度优先遍历结果：\n"); list.date[0]=0;//遍历开始节点，（从0节点开始） list.num++; visited[0]=true;//初始化开始节点访问为true while(1) { /*if(i==amg->vertexnum)//不能用这个判断，因为有可能还没遍历结束 i就==amg->vertexnum break;*/ if(list.num==0)//要用数列是否为空判断 break; for(int j=0;j<amg->vertexnum;j++) if(amg->arc[list.date[0]][j]==1&&!visited[j])//查找列表开头定点所连接的定点，追加到列表后面 { list.date[list.num]=j; list.num++; visited[j]=true; } //if(visited[list.date[0]]==false) //{ printf("%s ",amg->vertex[list.date[0]].c_str()); /*visited[list.date[0]]=true;*///在添加进队列的时候标记比较好 /* }*/ for(int j=0;j<list.num;j++) list.date[j]=list.date[j+1]; list.num--; } return OK; } //2、邻接表 int CreateAdjListGraph(AdjListGraph *alg) { int i=0; alg->numVertex=0; alg->numArc=0; while(1)//创建顶点 { printf("请输入邻接表的顶点结束用#："); cin>>alg->vlist[i].vertex; if(alg->vlist[i].vertex=="#") break; alg->vlist[i].firstEdge=NULL; i++; alg->numVertex++; } while(1)//创建边链表 { int v1=0,v2=0,w=0; EdgeNode *edgenode; printf("请输入邻接表的顶点对应的边（v1,v2,w）以(0,0,0)结束："); scanf("%d,%d,%d",&v1,&v2,&w); if(!v1&&!v2&&!w)//(0,0,0)结束 break; edgenode = new EdgeNode();//创建边节点 edgenode->arcVertex=v2; edgenode->weight=w; edgenode->next=NULL; if(alg->vlist[v1].firstEdge==NULL)//插入边节点 alg->vlist[v1].firstEdge=edgenode; else { EdgeNode *temp; temp=alg->vlist[v1].firstEdge; while(temp->next!=NULL) temp=temp->next; temp->next=edgenode; } //无向图要添加反方向的边，跟上面的代码一样，只是v1换成v2 v2换成v1 edgenode = new EdgeNode();//创建边节点 edgenode->arcVertex=v1; edgenode->weight=w; edgenode->next=NULL; if(alg->vlist[v2].firstEdge==NULL)//插入边节点 alg->vlist[v2].firstEdge=edgenode; else { EdgeNode *temp; temp=alg->vlist[v2].firstEdge; while(temp->next!=NULL) temp=temp->next; temp->next=edgenode; } alg->numArc++; } return OK; } //->1图邻接表的深度遍历 int AdjListDepthFirstRecursion(AdjListGraph *alg,int i) { if(visited[i]) return OK; printf("%s ",alg->vlist[i].vertex.c_str());//打印顶点 visited[i]=true; AdjListGraph *temp; //int j=0; temp=alg; while(temp->vlist[i].firstEdge) { AdjListDepthFirstRecursion(alg,temp->vlist[i].firstEdge->arcVertex); printf("(%d,%d)",i,temp->vlist[i].firstEdge->arcVertex); temp->vlist[i].firstEdge=temp->vlist[i].firstEdge->next; } return OK; } int AdjListDepthFirstSearch(AdjListGraph *alg,int f) { for(int i=0;i<alg->numVertex;i++) visited[i]=false; printf("邻接表深度遍历:\n"); AdjListDepthFirstRecursion(alg,f); return OK; } //->2图邻接表的广度遍历 int AdjListBreadthFirstSearch(AdjListGraph *alg) { //1、初始化访问标识数组 int i=0; for(i;i<alg->numVertex;i++) visited[i]=false; //2、初始化列表 list.date[0]=0; list.num++; visited[0]=true; i=0; //3、遍历图 while(1) { //退出循环条件 if(list.num==0) break; //遍历该顶点所连接的定点，并放进队列。 EdgeNode *temp; temp=alg->vlist[list.date[0]].firstEdge; while(temp) { if(!visited[temp->arcVertex]) { list.date[list.num]=temp->arcVertex; list.num++; visited[temp->arcVertex]=true; } temp=temp->next; } //打印未访问过的节点 //visited[i]=true; printf("%s ",alg->vlist[list.date[0]].vertex.c_str()); for(int l=0;l<list.num;l++) list.date[l]=list.date[l+1]; list.num--; i=list.date[0]; } return OK; } //3、十字链表(就是邻接表与逆邻接表合并)好处是方便同时具有图的出边和入边 int CreateOrthogonalListGraph(OrthogonalListGraph *olg) { int i=0; olg->numvertex=0; olg->numedge=0; while(1)//输入顶点 { printf("请输入图的顶点（以#结束）："); cin>>olg->vertexlist[i].vertex; if(olg->vertexlist[i].vertex=="#") break; olg->numvertex++; olg->vertexlist[i].edgein=NULL; olg->vertexlist[i].edgeout=NULL; i++; } while(1)//输入图的边 { OrthogonalLinkNode *edge; edge=new OrthogonalLinkNode(); edge->inlink=NULL; edge->outlink=NULL; int v1=0,v2=0,w=0; printf("请输入图的有向边（v1,v2,w）(0,0,0)结束："); scanf("%d,%d,%d",&v1,&v2,&w); if(!v1&&!v2&&!w) break; edge->outvex=v2; edge->invex=v1;//这一步是逆矩阵合并的步骤--edge->invex都等于链表的头顶点 if(olg->vertexlist[v1].edgeout==NULL) { olg->vertexlist[v1].edgeout=edge; }else { OrthogonalLinkNode *temp; temp=new OrthogonalLinkNode(); temp=olg->vertexlist[v1].edgeout; while(temp->outlink) temp=temp->outlink; temp->outlink=edge; } //最后处理图的入边与邻接表相比多了这个步骤，这个步骤是把逆邻接表串联起来，开头位置是edgein if(olg->vertexlist[v2].edgein==NULL) olg->vertexlist[v2].edgein=edge; else { OrthogonalLinkNode *temp; temp=new OrthogonalLinkNode(); temp=olg->vertexlist[v2].edgein; while(temp->inlink) temp=temp->inlink; temp->inlink=edge; } } return OK; } //4、邻接多重表结构 int CreateAdjacencyMultipleTableGraph(AdjacencyMultipleTableGraph *amtg) { int i=0; amtg->numVertex=0; amtg->numArc=0; while(1)//创建顶点 { printf("请输入邻接表的顶点结束用#："); cin>>amtg->vlist[i].vertex; if(amtg->vlist[i].vertex=="#") break; amtg->vlist[i].firstEdge=NULL; i++; amtg->numVertex++; } while(1)//创建边 { string v1,v2; int vc1,vc2;//顶点的下标 int w; AMTEdgeNode *node,*temp; node=new AMTEdgeNode(); printf("请输入的边(v1 v2 w)用(# # 0)结束："); cin>>v1>>v2>>w; /*scanf("%s,%s,%d",v1.c_str(),v2.c_str(),&w);*/ if(v1=="#"&&v2=="#"&&!w)//(0,0,0)结束 break; //查找顶点下标 for(int i=0;i<amtg->numVertex;i++) { if(amtg->vlist[i].vertex==v1) { vc1=i; break; } } for(i=0;i<amtg->numVertex;i++) { if(amtg->vlist[i].vertex==v2) { vc2=i; break; } } node->iver=v1; node->jver=v2; node->visited=false;//是否访问过 node->weight=w; node->ilink=NULL; node->jlink=NULL; if(!amtg->vlist[vc1].firstEdge)//列表的firstEdge为空则指向节点 amtg->vlist[vc1].firstEdge=node; if(!amtg->vlist[vc2].firstEdge)//列表的firstEdge为空则指向节点 amtg->vlist[vc2].firstEdge=node; if(amtg->vlist[vc1].firstEdge!=node) { temp=new AMTEdgeNode();//处理v1的ilink和jlink temp=amtg->vlist[vc1].firstEdge; while(temp) { if(temp->iver==v1) { if(!temp->ilink)//沿着链表找到ilink的最后为空，此时指针可以指向node { temp->ilink=node; break; } temp=temp->ilink;//否则继续下一个ilink节点 } else { if(!temp->jlink&&temp->jver==v1) { temp->jlink=node; break; } temp=temp->jlink; } } } if(amtg->vlist[vc2].firstEdge!=node) { temp=new AMTEdgeNode();//处理v2的ilink和jlink temp=amtg->vlist[vc2].firstEdge; while(temp) { if(temp->iver==v2) { if(!temp->ilink) { temp->ilink=node; break; } temp=temp->ilink; } else { if(!temp->jlink&&temp->jver==v2) { temp->jlink=node; break; } temp=temp->jlink; } } } amtg->numArc++; } return OK; }

main.cpp

#include<iostream> #include<stdio.h> #include <stdlib.h> #include<string> #include"structfun.h" using std::string; using std::printf; using std::scanf; using std::endl; using std::to_string; void main() { //图的邻接矩阵 AdjMarGraph amg; CreateAdjMaxGraph(&amg);//创建图的邻接矩阵 //AdjMarDepthFirstSearch(&amg,0);//图的邻接矩阵深度优先遍历 // AdjMarBreadthFirstSearch(&amg);//广度优先遍历（递归） AMBFS(&amg);//（非递归） //图的邻接表 //AdjListGraph alg; //CreateAdjListGraph(&alg); AdjListDepthFirstSearch(&alg,0); //AdjListBreadthFirstSearch(&alg); //图的十字链表 //OrthogonalListGraph olg; //CreateOrthogonalListGraph(&olg); //图的邻接多重表 //AdjacencyMultipleTableGraph amtg; //CreateAdjacencyMultipleTableGraph(&amtg); system("pause"); }