用邻接矩阵表示法创建有向图(数据结构).doc

#include#include#include#define MAX_VERTEX_NUM 20 /定义最多顶点个数#define INFINITY 32768 /定义无穷大/描述图的类型，用枚举型类型来说明typedef enumDG,DN,UDG,UDNGraphKind;/定义顶点数据类型typedef char VertexData;/定义邻接矩阵中元素值(即边信息）的数据类型typedef int ArcNode;/定义图的邻接矩阵类型 typedef struct VertexData vertexMAX_VERTEX_NUM;ArcNode arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;int vertexnum,arcnum;GraphKind kind; AdjMatrix;/图的邻接矩阵表示类型int LocateVertex(AdjMatrix *G,VertexData v) /求顶点位置函数int j=-1,k;for(k=0;kvertexnum;k+)if(G-vertexk=v)return k;return j;int CreateDN(AdjMatrix *G) /创建一个有向网int i,j,k,weight;VertexData v1,v2; printf(输入图的顶点数和弧数，以逗号分隔n); scanf(%d,%d,&G-vertexnum,&G-arcnum);for(i=0;ivertexnum;i+) /初始化邻接矩阵（主对角线元素全为零，其余元素为无穷大）for(j=0;jvertexnum;j+)G-arcsij=0;printf(输入图的顶点信息n);getchar();for(i=0;ivertexnum;i+)scanf(%c,&G-vertexi);printf(输出图的顶点信息n);for(i=0;ivertexnum;i+)printf(n%d,%c,i,G-vertexi);getchar();printf(输入一条弧的两个顶点以及该弧的权值，以空格分隔n); /创建邻接矩阵 for(k=0;karcnum;k+)printf(v1=);v1=getchar();getchar();printf(v2=);v2=getchar();getchar();printf(weight=);scanf(%d,&weight);getchar(); i=LocateVertex(G,v1); /寻找v1和v2在顶点数组中的位置j=LocateVertex(G,v2);G-arcsij=weight; /邻接矩阵第i行第j列元素值为weightG-arcsji=weight;return 1;void OutPutGraph(AdjMatrix G)int i,j;for(i=0;iG.vertexnum;i+)printf(n);for(j=0;jG.vertexnum;j+)if(G.arcsij=INFINITY)printf( );else printf(%-5d,G.arcsij);void m