程序主要实现了图的深度遍历和广度遍历。
#include <stdio.h>#include <stdlib.h>#include <string.h>#define OVERFLOW -2#define ERROR 0#define OK 1#define Length (q.rear+1)%QUEUE_MAXSIZE //队满#define MAX_VERtEX_NUM 20 //顶点的最大个数#define QUEUE_MAXSIZE 100#define Queue_increment 10typedef struct QNode{ int data; struct QNode *next;}QNode,*QueuePtr;typedef struct{ QueuePtr front; //队头指针 QueuePtr rear; //队尾指针}linkQueue;//-------------------------------------------------------------------------------------------------------------typedef struct { int adj; //对于无权图,用 1 或 0 表示是否相邻;对于带权图,直接为权值。}ArcCell,AdjMatrix[MAX_VERtEX_NUM][MAX_VERtEX_NUM];typedef struct { char vexs[MAX_VERtEX_NUM]; //存储图中顶点数据 AdjMatrix arcs; //二维数组,记录顶点之间的关系 int vexnum,arcnum; //记录图的顶点数和弧(边)数}MGraph;//---------------------------------------------------------------------------// 矩阵打印关系voID PrintGrapth(MGraph &G){ int i,j; for (i = 0; i < G.vexnum;++i){ printf("%d",G.vexs[i]); } printf("顶点间的关系:\n"); for (i = 0; i < G.vexnum; ++i){ for (j = 0; j < G.vexnum; ++j){ printf("%d ",G.arcs[i][j].adj); } printf("\n"); }}//---------------------------------------------------------------------------//根据顶点本身数据,判断出顶点在二维数组中的位置int LocateVex(MGraph &G,int v){ //遍历一维数组,找到变量v for (int i=0; i<G.vexnum; ++i) { if (G.vexs[i]==v) { return i; } } return -1; //如果找不到,返回-1 }//构造无向图int Createdn(MGraph &G){ int i,j,k,m,n,x;int v1,v2;//char a[2]; printf("请输入总顶点数n和总边数:"); scanf("%d",&(G.vexnum)); // 输入总顶点数,总边数 scanf("%d",&(G.arcnum)); x=G.vexnum; if(G.vexnum<20 && G.arcnum<=(x*(x-1)/2)){ printf("请(回车)输入 %d 个顶点的值:\n",G.vexnum); for (i=0; i<G.vexnum; i++) { // 循环输入顶点值 scanf("%d",&(G.vexs[i])); } for (i=0; i<G.vexnum; ++i) { // 初始化邻接矩阵 for (j=0; j<G.vexnum; ++j) { G.arcs[i][j].adj=0; } } printf("\n请实现 %d 条边的连接:\n",G.arcnum); for (k=0;k<G.arcnum; ++k) { // 构造邻接矩阵 printf("\n请输入哪‘两个‘顶点要进行连接边:"); fflush(stdin); scanf("%d",&v1); n=LocateVex(G,v1); //定位顶点 scanf("%d",&v2); m=LocateVex(G,v2); while (m==-1||n==-1) { printf("没有这样的顶点,请重新输入:"); fflush(stdin); scanf("%d",&v1); n=LocateVex(G,v1); //定位顶点 scanf("%d",&v2); m=LocateVex(G,v2); // if(m!=-1&&n!=-1){break; } } while(G.arcs[n][m].adj==1){ printf("\n!!!两顶点已经被连接!!!\n"); printf("请重新输入两顶点:"); fflush(stdin); scanf("%d",v2); // if(G.arcs[n][m].adj!=1){break; } while (m==-1||n==-1) { printf("没有这样的顶点,请重新输入:"); fflush(stdin); scanf("%d",&v1); n=LocateVex(G,v1); //定位顶点 scanf("%d",&v2); m=LocateVex(G,v2); // if(m!=-1&&n!=-1){break; } } } G.arcs[n][m].adj=G.arcs[m][n].adj=1; //无向图的二阶矩阵沿主对角线对称 } }else{ printf("\n!!!您输入的总顶点数 大于 20 了或者是输入的总边数 不符合 n(n-1)/2 !!!\n"); Createdn(G); } return OK;}//-------------------------------------------------------------------------------------------------int visited[MAX_VERtEX_NUM]; // 辅助数组// 遍历节点voID DFS(MGraph &G,int v){ int j; printf("访问到顶点:%d\n\n",G.vexs[v]); // 表示顶点被访问过了 visited[v]=1; for(j=0;j<G.vexnum;++j){ if(G.arcs[v][j].adj!=0 && visited[j]==0){ // 如果有邻接点则继续递归 DFS(G,j); } }}// 顶点的非连通图的深度遍历int DFSTraverse(MGraph &G){ int n=0,v,x,m; for(v=0;v<G.vexnum;v++) visited[v]=0; // 把所有的标记置为0 printf("\n请输入遍历起点:\n"); scanf("%d",&x); printf("遍历起点为:%d \n",x); m = LocateVex(G,x); if(m==-1){ printf("\n!!!您输入的起点不在顶点表内!!!\n"); DFSTraverse(G); } //n=LocateVex(G,x); visited[m]=1; for(j=0;j<G.vexnum;++j){ if(G.arcs[n][j].adj!=0 && visited[j]==0){ // 如果有邻接点则继续递归 DFS(G,j); } } //DFS(G,m); for(v=0;v<G.vexnum;++v){ // 判断是否还有没有被遍历的图 if(visited[v]==0){ DFS(G,v); // 调用DFS遍历单个图 } } return OK;}//-------------------------------------------------------------------------------------//构建空队int InitQueue_Q(linkQueue &Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); if(!Q.front){ printf("队存储空间分配失败!!"); exit(OVERFLOW); } Q.front->next=NulL; return OK;}//队尾插入元素int EnQueue_Q(linkQueue &Q,int &e){ QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if(!p){ //存储分配失败 printf("队存储空间分配失败!!!\n"); exit(OVERFLOW); } p->data=e; //e赋值给p指向的空间 p->next=NulL; //p指向NulL Q.rear->next=p; Q.rear=p; //将p赋给Q return OK;}// 删除队列头元素int DeQueue_Q(linkQueue &Q,int &e){ QNode *P; if(Q.front==Q.rear) return ERROR; P=Q.front->next ; e=P->data; Q.front ->next =P->next; //将原对头的后继p->next赋值给头结点后继 if(Q.rear ==P) //当队列中只有一个元素时,q->rear指向头结点 Q.rear =Q.front; free(P); return OK;}// 队判空int QueueEmpty(linkQueue Q){ if(Q.front->next==NulL) return ERROR; else return OK; }//-----------------------------------------------------------------------------------------------------// BFSTraversed调用BFS每一个节点都被访问voID BFS(MGraph &G,int i){ int j; linkQueue Q; InitQueue_Q(Q); if(visited[i]==0){ //未访问过该顶点 printf("访问到顶点:%d\n\n",G.vexs[i]); visited[i]=1; // 置1 EnQueue_Q(Q,i); //将其入队列 while(QueueEmpty(Q)){ // 循环队不为空QueueEmpty返回1 DeQueue_Q(Q,i); //将队头元素出队列,置为v for(j=0;j<G.vexnum;j++){ if(G.arcs[i][j].adj!=0 &&visited[j]==0){ //未访问过的邻接点 printf("顶点走到的值:%d\n\n",G.vexs[j]); // i 为v中未被访问的邻接点 visited[j]=1; // 访问置1 EnQueue_Q(Q,j); //入队列 } } } }}// 广度优先遍历图int BFSTraverse(MGraph &G){ int i,m;char x; linkQueue Q; InitQueue_Q(Q); for(v=0;v<G.vexnum;v++){ // 辅助数组置零 visited[v]=0; } printf("\n请输入遍历起点:\n"); scanf("%d",x); m=LocateVex(G,x); if(m==-1){ printf("\n!!!您输入的起点不在顶点表内!!!\n"); BFSTraverse(G); } visited[m]=1; EnQueue_Q(Q,m); //将其入队列 while(QueueEmpty(Q)){ // 循环队不为空QueueEmpty返回1 DeQueue_Q(Q,m); //将队头元素出队列,置为v for(j=0;j<G.vexnum;j++){ if(G.arcs[m][j].adj!=0 &&visited[j]==0){ //未访问过的邻接点 printf("顶点走到的值:%d\n\n",j); //入队列 } } } for(i=0;i<G.vexnum;i++){ // 保证所有节点被访问 BFS(G,i ); } return OK;} // *** 作菜单voID OperateMenu(){ printf("\n\n--------------请选择元素处理方式---------\n\n"); printf("!!!!!注:测试程序过程中,输入应全为数字!!!!!\n\n"); printf("0> :退出\n\n"); printf("1>: 深度遍历\n\n"); printf("2>: 广度遍历\n\n"); printf("3>: 输出邻接矩阵\n\n"); printf("(注:选择过程中应为数字)\n\n"); printf("请选择对元素的处理:");}voID main() { MGraph G;//建立一个图的变量 int w=0,boo=1; printf("请用户选择创建图 或 退出程序:\n\n"); printf("注:程序测试过程中输入应全为数字\n\n"); printf("创建图请输入:‘1‘\n\n"); printf("退出请选择‘0‘或 其它!!\n\n"); printf("请选择:"); scanf("%d",&w); if(w==1){ boo=Createdn(G); if(boo) printf("\n建图成功!!!\n"); else printf("\n建图失败!!!\n"); OperateMenu(); scanf("%d",&k); while(k){ switch(k){ case 0:break; case 1:boo=DFSTraverse(G); // 深度遍历 if(boo) printf("\n深度遍历成功!!!\n"); else printf("\n深度遍历失败!!!\n"); break; case 2:boo=BFSTraverse(G); // 广度遍历 if(boo) printf("\n广度遍历成功!!!\n"); else printf("\n广度遍历失败!!!\n"); break; case 3:PrintGrapth(G); } OperateMenu(); scanf("%d",&k); } }}总结
以上是内存溢出为你收集整理的c_ 数据结构_图_邻接矩阵全部内容,希望文章能够帮你解决c_ 数据结构_图_邻接矩阵所遇到的程序开发问题。
如果觉得内存溢出网站内容还不错,欢迎将内存溢出网站推荐给程序员好友。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)