数据结构图的建立与计算.docVIP

数据结构图的建立与计算 #includestdio.h #includestdlib.h #includemath.h #includemalloc.h #includestring.h #define NULL 0 #define INFINITY 2000 //权值很大，表示两顶点不相关联 #define MAX 20 //图顶点数目最大值 #define NameLength 20 //顶点名称字符串容许的最大字符个数 typedef enum{ DG,DN,UDG,UDN //{有向图，有向网，无向图，无向网} }Graphkind; typedef struct ArcCell{ int adj; //无权图，用1和0表示相邻否，对带权图，为权值 char *info; //该弧相关信息的指针 }ArcCell,AdjMatrix[MAX][MAX]; typedef struct{ char vexs[MAX][NameLength]; //顶点名称 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 Graphkind kind; //图的种类标志 }MGraph; typedef struct QNode{ int data; struct QNode *next; }QNode,*QueuePtr; //队列的结点结构体,存储的是指向二叉树结点的指针 typedef struct{ QueuePtr front; QueuePtr rear; }LinkQueue; //该结构体含指向队头的指针和队尾的指针 //新建一个队列 void InitQueue(LinkQueue Q){ Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode)); Q.front-next=NULL; } //将一个元素T插入队列 void EnQueue(LinkQueue Q,int i){ QueuePtr p; p=(QueuePtr)malloc(sizeof(QNode)); p-data=i; p-next=NULL; Q.rear-next=p; Q.rear=p; } //将一个元素从队列中删除，返回该元素 int DeQueue(LinkQueue Q,int i){ QueuePtr p; if(Q.front==Q.rear) return 0; p=Q.front-next; i=p-data; Q.front-next=p-next; if(Q.rear==p) Q.rear=Q.front; free(p); return 1; } //判断队列是否为空，若为空，返回1，若不为空，则返回0 int QueueEmpty(LinkQueue Q){ if(Q.front==Q.rear) return 1; else return 0; } //取得队头元素 int GetHead(LinkQueue Q){ return(Q.front-next-data); } //定位函数，求得字符串v在图G中的顶点序号，若不存在，返回-1，若存在，返回该序号 int LocateVex(MGraph G,char v[5]){ int i; for(i=0;iG.vexnum;i++) if(strcmp(G.vexs[i],v)==0) return i; //查找 printf(该顶点不存在！\n); return -1; } //该函数用于求与图G中序号为v的顶点相关联的第一个顶点（由于图用邻接矩阵表示，故有先后关系， //返回该顶点的序号 int FirstAdjVex(MGraph G,int v){ int i; for(i=0;iG.vexnum;i++) if(G.arcs[v][i].adj!=INFINITY) return(i); return -1; } //该函数用于求与图G中序号为v的顶点相关联的各顶点中序号为w的顶点的后一个顶点 int NextAdjVex(MGraph G,int v,int w){ int i; for(i=w+1;iG.vexnum;i++) if(G.arcs[v][i].adj!=INFINITY) return(i); return -1; } //采用邻接矩