本文主要是介绍成长路上的小程序之——图的邻接矩阵DFS、BFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
之所以发这篇博客是不甘心我写了这么长的代码，结果一个贱人告诉我存储方式用错了。。。
这里的BFS因为嫌写队列函数太麻烦，所以直接用数组加标识front、rear完成队列的操作，反正节点个数小，使用数组并不会浪费很多空间。
贴上代码纪念一下我曾经二过：
#define MAX -1;
#define MAX_VERTEX_NUM 20
typedef enum {DG,DN,UDG,UDN} GraphKind;
typedef char VertexType;
typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct {VertexType vexs[MAX_VERTEX_NUM];AdjMatrix arcs;int vexnum,arcnum;GraphKind kind;
}MGraph;Status LocateVex(MGraph G,VertexType u)//在G中找到u的位置，需要调用图的遍历
{for(int i=0; i<G.vexnum; i++)if(u==G.vexs[i])return i;
} Status CreateDG(MGraph &G)
{int i,j,k;char v1,v2;printf("please enter the vexnum and arcnum:\n\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar(); printf("please enter the vexs in order:\n\n");for(i=0; i<G.vexnum; i++)scanf("%c",&G.vexs[i]);for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)G.arcs[i][j]=MAX;printf("please enter edge:\n");for(k=0; k<G.arcnum; k++){getchar();scanf("%c %c",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;}printf("Here are the matrix:\n\n");for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)if(G.arcs[i][j]!=1)printf("0");elseprintf("1");printf("\n");}return OK;
}Status CreateUDG(MGraph &G)//创建无向无权图
{int i,j,k;char v1,v2;printf("please enter the vexnum and arcnum:\n\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar(); printf("please enter the vexs in order:\n\n");for(i=0; i<G.vexnum; i++)scanf("%c",&G.vexs[i]);for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)G.arcs[i][j]=MAX;printf("please enter edge:\n\n");for(k=0; k<G.arcnum; k++){getchar();scanf("%c %c",&v1,&v2);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=1;G.arcs[j][i]=1;}printf("Here are the matrix:\n\n");for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)if(G.arcs[i][j]!=1)printf("0");elseprintf("1");printf("\n");}return OK;
}Status CreateDN(MGraph &G)//创建有向带权图
{int i,j,k,w;char v1,v2;printf("please enter the vexnum and arcnum:\n\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar(); printf("please enter the vexs in order:\n\n");for(i=0; i<G.vexnum; i++)scanf("%c",&G.vexs[i]);for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)G.arcs[i][j]=MAX;printf("please enter two vertexs and length:\n\n");for(k=0; k<G.arcnum; k++){getchar();scanf("%c %c %d",&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;}printf("Here are the matrix:\n\n");for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)if(G.arcs[i][j]==-1)printf("#");elseprintf("%d",G.arcs[i][j]);printf("\n");}return OK;
}Status CreateUDN(MGraph &G)//创建无向带权图
{int i,j,k,w;char v1,v2;printf("please enter the vexnum and arcnum:\n\n");scanf("%d%d",&G.vexnum,&G.arcnum);getchar(); printf("please enter the vexs in order:\n\n");for(i=0; i<G.vexnum; i++)scanf("%c",&G.vexs[i]);for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)G.arcs[i][j]=MAX;printf("please enter two vertexs and length:\n\n");for(k=0; k<G.arcnum; k++){getchar();scanf("%c %c %d",&v1,&v2,&w);i=LocateVex(G,v1);j=LocateVex(G,v2);G.arcs[i][j]=w;G.arcs[j][i]=G.arcs[i][j];}printf("Here are the matrix:\n\n");for(i=0; i<G.vexnum; i++){for(j=0; j<G.vexnum; j++)printf("%d ",G.arcs[i][j]);printf("\n");}return OK;
}Status CreateGraph(MGraph &G)//创建图选择菜单
{printf("please enter Graph's kind:\n\n");printf("0 present DG(有向图)\n\n");printf("1 present DN(有向网)\n\n");printf("2 present UDG(无向图)\n\n");printf("3 present UDN(无向网)\n\n");scanf("%d",&G.kind);switch(G.kind){case DG: return CreateDG(G);//有向无权图 case DN: return CreateDN(G);//有向带权图 case UDG: return CreateUDG(G);//无向无权图 case UDN: return CreateUDN(G);//无向带权图 default : return ERROR;}
}bool visited[MAX_VERTEX_NUM];int FirstAdjVex(MGraph G, int v)
{for(int i=0; i<G.vexnum; i++)if(G.arcs[v][i]!=-1)return i;return -1;
}int NextAdjVex(MGraph G, int v, int w)
{for(int i=w+1; i<G.vexnum; i++)if(G.arcs[v][i]!=-1)return i;return -1;
}void DFS(MGraph G, int v)
{visited[v]=true;printf("%c ",G.vexs[v]);for(int w=FirstAdjVex(G,v); w>=0; w=NextAdjVex(G,v,w)){if(!visited[w])DFS(G,w);}return ;
}void DFSTraverse(MGraph 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(MGraph G)
{int que[MAX_VERTEX_NUM]={-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.vexs[v]);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.vexs[w]);que[++rear]=w; } } }printf("\n");
}void menu(MGraph 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);
}
这篇关于成长路上的小程序之——图的邻接矩阵DFS、BFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
