[宝典]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵

[宝典]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵[宝典]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵 /* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */ #include "stdio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; #define INFINITY INT_MAX /*最大值“无穷”*/ #defin...

[宝典]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵 /* 采用邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操作 */ #include "stdio.h" #include "string.h" #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 typedef int Status; #define INFINITY INT_MAX /*最大值“无穷”*/ #define MAX_VERTEX_NUM 20 /*最大顶点个数*/ typedef int Boolean; typedef char VertexType[20]; typedef int VRType; /**************以下为队列的操作************/ /****队列的类型定义****/ typedef int QElemType; typedef struct QNode {QElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; } LinkQueue; /****初始化队列****/ Status InitQueue(LinkQueue *Q) { (*Q).front=(*Q).rear=(QueuePtr)malloc(sizeof(QNode)); if (!(*Q).front) exit(OVERFLOW); (*Q).front->next=NULL; return OK; } /****判断队列是否为空****/ Status QueueEmpty (LinkQueue Q) { if (Q.front==Q.rear) return TRUE; else return FALSE; } /****入队列****/ Status EnQueue(LinkQueue *Q, QElemType e) { QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data=e; p->next=NULL; (*Q).rear->next=p; (*Q).rear=p; return OK; } /****出队列****/ Status DeQueue(LinkQueue *Q, QElemType *e) { QueuePtr p; if ((*Q).front==(*Q).rear) return ERROR; p=(*Q).front->next; *e=p->data; (*Q).front->next=p->next; if ((*Q).rear==p) (*Q).rear=(*Q).front; free(p); return OK; } /**************以下为图的操作************/ /*图的类型定义*/ typedef struct ArcCell { VRType adj; /*图中有1/0 表示是否有边，网中表示边上的权值*/ /* InfoType *info; 与边相关的信息*/ } ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; /*顶点向量*/ AdjMatrix arcs; /*邻接矩阵*/ int vexnum,arcnum; /*图中当前顶点数和边数*/ } MGraph; /*建立无向图的邻接矩阵*/ void CreateGraph(MGraph *G) { int i,j,k; VertexType v1,v2; printf("\nInput MG vexnum,arcnum:"); scanf("%d,%d",&(*G).vexnum,&(*G).arcnum); printf("Input %d vexs:",(*G).vexnum); for(i=0;i<(*G).vexnum;i++) /*输入顶点向量*/ { scanf("%s",(*G).vexs[i]); } printf("vexs list\n"); for(i=0;ivexnum;i++) /*输出顶点向量*/ puts(G->vexs[i]); for(i=0;i<(*G).vexnum;i++) /*邻接矩阵初始化*/ for(j=0;j<(*G).vexnum;j++) (*G).arcs[i][j].adj=0; printf("\nInput %d arcs(vi vj):\n",(*G).arcnum); for(k=0;k<(*G).arcnum;k++) /*输入无权图的边*/ { scanf("%s%s",v1,v2); i=LocateVex(*G,v1); j=LocateVex(*G,v2); (*G).arcs[i][j].adj=1; (*G).arcs[j][i]=(*G).arcs[i][j]; } } /* 顶点在顶点向量中的定位*/ int LocateVex(MGraph G,VertexType v) { int i; for(i=0;i=0; w=NextAdjVex(G,v,w)) if(!visited[w]) Dfs(G,w); } void DfsTraverse(MGraph G) { int v; for (v=0; v=0; w=NextAdjVex(G,u,w)) if (!visited[w]) { visited[w]=TRUE; printf("%s",G.vexs[w]); EnQueue(&Q,w); } } } } /*主函数*/ main() { int w; MGraph G; CreateGraph(&G); PrintGraph(G); printf("\nDfs:"); DfsTraverse(G); /* 深度遍历 */ printf("\nBfs:"); BfsTraverse(G); /* 广度遍历 */ }

                    本文档为【[宝典]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

[宝典]采纳邻接矩阵完成无向图的“建立、深度遍历、广度遍历”操纵

你可能还喜欢