成长路上的小程序之——图的邻接表DFS、BFS

本文主要是介绍成长路上的小程序之——图的邻接表DFS、BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

第八次数据结构上机内容：使用图的邻接表存储结构完成图的DFS、BFS遍历

本来提前就用邻接矩阵写完了，但昨晚一个贱人突然告诉我老师要求用邻接表写。。。于是加班加点，终于在今早搞出来了！

上机课的时候因为没带书，所以完全是自己敲的，期间被一个无限循环困住了！！！

在邻接链表插入新节点过程中，为p申请新空间，插入后就释放空间

在刘文斌大神的帮助下，我理解了开辟、释放空间这个概念。

我在创建图的过程中，更改了p的指向，并且最后释放p时，p为空指针，所以没有错误。

释放空间时，要确保能够找到之前创建的所有空间并释放！！！！

应该在使用完成后释放空间！！

以后再申请新空间时，无论如何也要放在最后释放空间，这样不容易出错。

代码中还有一个问题就是在FirstAdjVex()和NextAdjVex()函数中，没有释放空间，因为试过只要释放空间就无法使DFS函数结束。

解决方法是在创建空间的时候，另设一个标志指针指向该位置，使用完成后释放标志指针所指空间即可

再次感谢刘文斌大神

代码如下：

#define MAX 20typedef char VertexType;typedef struct ArcNode{int adjvex;int w;struct ArcNode *nextarc;
}ArcNode;typedef struct VNode{VertexType data;ArcNode *firstarc;
}VNode,AdjList[MAX];typedef struct{AdjList vertices;   int vexnum;int arcnum;int kind;
}ALGraph;int Locate(ALGraph G,char x)
{for(int i=0; i<G.vexnum; i++)if(G.vertices[i].data==x) return i;return -1; 
} Status CreateDG(ALGraph &G)//创建有向图 
{char v1,v2; int  j; ArcNode *p;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c",&v1,&v2); j=Locate(G,v1); //定位v1位置  p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=Locate(G,v2);p->w=0;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;//不可以在这里释放空指针！！！} printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[i].firstarc;while(p)     {printf(" -> %d",p->adjvex);p=p->nextarc;    }printf("\n\n");} return OK;
}Status CreateDN(ALGraph &G)//创建有向网 
{char v1,v2; int  j,w; ArcNode *p;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c %d",&v1,&v2,&w); j=Locate(G,v1); //定位v1位置  p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=Locate(G,v2);p->w=w;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;//不可以在这里释放空指针！！！ }printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[i].firstarc;while(p)     {printf("->[ %d weight:%d ]",p->adjvex,p->w);p=p->nextarc;    }printf("\n\n");}return OK;
}Status CreateUDG(ALGraph &G)//创建无向图 
{char v1,v2; int  j,k; ArcNode *p,*q,*flag;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c",&v1,&v2); j=Locate(G,v1); //定位v1位置  k=Locate(G,v2);p=(ArcNode *)malloc(sizeof(ArcNode)); q=(ArcNode *)malloc(sizeof(ArcNode));p->adjvex=k;p->w=0;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;q->adjvex=j;q->w=0;q->nextarc=G.vertices[k].firstarc;G.vertices[k].firstarc=q;//不可以在这里释放空指针！！！} printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=G.vertices[i].firstarc;while(p)     {printf(" -> %d",p->adjvex);p=p->nextarc;    }printf("\n\n");}return OK;
}Status CreateUDN(ALGraph &G)//创建无向网 
{char v1,v2; int  j,w,k; ArcNode *p,*q;printf("\nplease enter the vexnum and arcnum:\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar();printf("\nplease enter the vexs in order:\n");for(int i=0; i<G.vexnum; i++){scanf("%c",&G.vertices[i].data);G.vertices[i].firstarc=NULL;} printf("\nplease enter edge:\n");for(int i=0; i<G.arcnum; i++){getchar(); scanf("%c %c %d",&v1,&v2,&w); j=Locate(G,v1); //定位v1位置  k=Locate(G,v2);p=(ArcNode *)malloc(sizeof(ArcNode)); q=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=k;p->w=w;p->nextarc=G.vertices[j].firstarc;G.vertices[j].firstarc=p;//不可以在这里释放空指针！！！ q->adjvex=j;q->w=w;q->nextarc=G.vertices[k].firstarc;G.vertices[k].firstarc=q;}printf("\nHere are the ALGraph:\n"); for(int i=0; i<G.vexnum; i++){printf("%c",G.vertices[i].data);p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[i].firstarc;while(p)     {printf("->[ %d weight:%d ]",p->adjvex,p->w);p=p->nextarc;    }printf("\n\n");}return OK;
}void CreateMenu(ALGraph &G)
{printf("please enter the Graph's kind:\n");printf("\n0 present DG(有向图)\n");printf("\n1 present DN(有向网)\n");printf("\n2 present UDG(无向图)\n");printf("\n3 present UDN(无向网)\n");char ch=getchar();switch(ch){case '0':CreateDG(G);break;    case '1':CreateDN(G);break;    case '2':CreateUDG(G);break;    case '3':CreateUDN(G);break;    }return ;
} ArcNode *p;
bool visited[MAX];int FirstAdjVex(ALGraph G, int v)
{p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[v].firstarc;if(p)return p->adjvex;else return -1;
}int NextAdjVex(ALGraph G, int v, int w)
{p=(ArcNode *)malloc(sizeof(ArcNode)); p=G.vertices[v].firstarc;for(int i=0; i<MAX; i++){if(p->adjvex==w){ if(p->nextarc){ return p->nextarc->adjvex;} else return -1;}elsep=p->nextarc;}
}void DFS(ALGraph G, int v)
{visited[v]=true;printf("%c   ",G.vertices[v].data);for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)){if(!visited[w])DFS(G,w);}return ;
}void DFSTraverse(ALGraph G)
{printf("\n\n\nHere are the results of DFSTraverse:\n\n");int v;for(v=0; v<G.vexnum; v++)visited[v]=false;for(v=0; v<G.vexnum; v++)if(!visited[v])DFS(G,v);printf("\n");return ;
}//----------队列 void BFSTraverse(ALGraph G)
{int que[MAX]={-1}; int u;int rear=0,front=0;printf("\n\n\nHere are the results of BFSTraverse:\n\n");for(int v=0; v<G.vexnum; v++)visited[v]=false;for(int v=0; v<G.vexnum; v++)if(!visited[v]){visited[v]=true;printf("%c   ",G.vertices[v].data);que[++rear]=v;while(rear!=front){u=que[++front];for(int w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))if(!visited[w]){visited[w]=true;printf("%c   ",G.vertices[w].data);que[++rear]=w;   }      } }printf("\n");
}void menu(ALGraph G)
{printf("\n\npleae choice the traverse:");printf("\n\n1.DFS\n\n2.BFS\n\n");getchar();char ch=getchar();if(ch=='1')return DFSTraverse(G);else if(ch=='2')return BFSTraverse(G);
} 

main函数：

#include <cstdlib>
#include <iostream>
#include "constant.h"
#include "graph.h"using namespace std;int main(int argc, char *argv[])
{ArcNode *p,*flag; ALGraph G;CreateMenu(G);menu(G);for(int i=0; i<G.vexnum; i++){p=G.vertices[i].firstarc;while(p)     {flag=p->nextarc;free(p);p=flag;}}system("PAUSE");return EXIT_SUCCESS;
}

这篇关于成长路上的小程序之——图的邻接表DFS、BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---