搜索
邻接表表示的图：#includestdio.h#includestdlib.h#defineMaxVertexNum50//定义最大顶点数typedefstructnode{//边表结点intadjvex;//邻接点域structnode*next;//链域}EdgeNode;typedefstructvnode{//顶点表结点charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;typedefVertexNodeAdjList[MaxVertexNum];//AdjList是邻接表类型typedefstruct{AdjListadjlist;//邻接表intn,e;//图中当前顶点数和边数}ALGraph;//图类型//=========建立图的邻接表=======voidCreatALGraph(ALGraph*G){inti,j,k;chara;EdgeNode*s;//定义边表结点printf(InputVertexNum(n)andEdgesNum(e):);scanf(%d,%d,&G-n,&G-e);//读入顶点数和边数fflush(stdin);//清空内存缓冲printf(InputVertexstring:);for(i=0;iG-n;i++)//建立边表{scanf(%c,&a);G-adjlist[i].vertex=a;//读入顶点信息G-adjlist[i].firstedge=NULL;//边表置为空表}printf(Inputedges,CreatAdjacencyList\n);for(k=0;kG-e;k++){//建立边表scanf(%d%d,&i,&j);//读入边（Vi，Vj）的顶点对序号s=(EdgeNode*)malloc(sizeof(EdgeNode));//生成边表结点s-adjvex=j;//邻接点序号为js-next=G-adjlist[i].firstedge;G-adjlist[i].firstedge=s;//将新结点*S插入顶点Vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode));s-adjvex=i;//邻接点序号为is-next=G-adjlist[j].firstedge;G-adjlist[j].firstedge=s;//将新结点*S插入顶点Vj的边表头部}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(ALGraph*G,inti){//以Vi为出发点对邻接链表表示的图G进行DFS搜索EdgeNode*p;printf(%c,G-adjlist[i].vertex);//访问顶点Vivisited[i]=TRUE;//标记Vi已访问p=G-adjlist[i].firstedge;//取Vi边表的头指针while(p){//依次搜索Vi的邻接点Vj，这里j=p-adjvexif(!visited[p-adjvex])//若Vj尚未被访问DFSM(G,p-adjvex);//则以Vj为出发点向纵深搜索p=p-next;//找Vi的下一个邻接点}}voidDFS(ALGraph*G){inti;for(i=0;iG-n;i++)visited[i]=FALSE;//标志向量初始化for(i=0;iG-n;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi为源点开始DFS搜索}//==========BFS：广度优先遍历=========voidBFS(ALGraph*G,intk){//以Vk为源点对用邻接链表表示的图G进行广度优先搜索inti,f=0,r=0;EdgeNode*p;intcq[MaxVertexNum];//定义FIFO队列for(i=0;iG-n;i++)visited[i]=FALSE;//标志向量初始化for(i=0;i=G-n;i++)cq[i]=-1;//初始化标志向量printf(%c,G-adjlist[k].vertex);//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=-1){//队列非空则执行i=cq[f];f=f+1;//Vi出队p=G-adjlist[i].firstedge;//取Vi的边表头指针while(p){//依次搜索Vi的邻接点Vj（令p-adjvex=j）if(!visited[p-adjvex]){//若Vj未访问过printf(%c,G-adjlist[p-adjvex].vertex);//访问Vjvisited[p-adjvex]=TRUE;r=r+1;cq[r]=p-adjvex;//访问过的Vj入队}p=p-next;//找Vi的下一个邻接点}}//endwhile}//==========主函数===========voidmain(){//inti;ALGraph*G;G=(ALGraph*)malloc(sizeof(ALGraph));CreatALGraph(G);printf(PrintGraphDFS:);DFS(G);printf(\n);printf(PrintGraphBFS:);BFS(G,3);printf(\n);}邻接矩阵表示的图：#includestdio.h#includestdlib.h#defineMaxVertexNum100//定义最大顶点数typedefstruct{charvexs[MaxVertexNum];//顶点表intedges[MaxVertexNum][MaxVertexNum];//邻接矩阵，可看作边表intn,e;//图中的顶点数n和边数e}MGraph;//用邻接矩阵表示的图的类型//=========建立邻接矩阵=======voidCreatMGraph(MGraph*G){inti,j,k;chara;printf(InputVertexNum(n)andEdgesNum(e):);scanf(%d,%d,&G-n,&G-e);//输入顶点数和边数scanf(%c,&a);printf(InputVertexstring:);for(i=0;iG-n;i++){scanf(%c,&a);G-vexs[i]=a;//读入顶点信息，建立顶点表}for(i=0;iG-n;i++)for(j=0;jG-n;j++)G-edges[i][j]=0;//初始化邻接矩阵printf(Inputedges,CreatAdjacencyMatrix\n);for(k=0;kG-e;k++){//读入e条边，建立邻接矩阵scanf(%d%d,&i,&j);//输入边（Vi，Vj）的顶点序号G-edges[i][j]=1;G-edges[j][i]=1;//若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句}}//=========定义标志向量，为全局变量=======typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxVertexNum];//========DFS：深度优先遍历的递归算法======voidDFSM(MGraph*G,inti){//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵intj;printf(%c,G-vexs[i]);//访问顶点Vivisited[i]=TRUE;//置已访问标志for(j=0;jG-n;j++)//依次搜索Vi的邻接点if(G-edges[i][j]==1&&!visited[j])DFSM(G,j);//（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点}voidDFS(MGraph*G){inti;for(i=0;iG-n;i++)visited[i]=FALSE;//标志向量初始化for(i=0;iG-n;i++)if(!visited[i])//Vi未访问过DFSM(G,i);//以Vi为源点开始DFS搜索}//===========BFS：广度优先遍历=======voidBFS(MGraph*G,intk){//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索inti,j,f=0,r=0;intcq[MaxVertexNum];//定义队列for(i=0;iG-n;i++)visited[i]=FALSE;//标志向量初始化for(i=0;iG-n;i++)cq[i]=-1;//队列初始化printf(%c,G-vexs[k]);//访问源点Vkvisited[k]=TRUE;cq[r]=k;//Vk已访问，将其入队。注意，实际上是将其序号入队while(cq[f]!=-1){//队非空则执行i=cq[f];f=f+1;//Vf出队for(j=0;jG-n;j++)//依次Vi的邻接点Vjif(!visited[j]&&G-edges[i][j]==1){//Vj未访问printf(%c,G-vexs[j]);//访问Vjvisited[j]=TRUE;r=r+1;cq[r]=j;//访问过Vj入队}}}//==========main=====voidmain(){//inti;MGraph*G;G=(MGraph*)malloc(sizeof(MGraph));//为图G申请内存空间CreatMGraph(G);//建立邻接矩阵printf(PrintGraphDFS:);DFS(G);//深度优先遍历printf(\n);printf(PrintGraphBFS:);BFS(G,3);//以序号为3的顶点开始广度优先遍历printf(\n);}