图的基本操作(邻接矩阵).docx

/*图的邻接矩阵储存表示*#define INFINITY INT_MAX /最大值为无穷大#define MAX_VERTEX_NUM 20 /最大顶点个数#includeusing namespace std;typedef enum DG,DN,AG,ANGraphKind; /有向图，有向网，无向图，无向网typedef int Status;typedef int VRType;typedef char InfoType;typedef struct ArcCellVRType adj; /表示顶点关系，对于无向图有向图用0和1表示是否相邻，对于有向图有向网用权值类型表示InfoType* info; /该弧相关信息的指针ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct /点的值char name;char* data;VertexTypeMAX_VERTEX_NUM; typedef structVertexType vexs; /顶点向量AdjMatrix arcs; /邻接矩阵int vexnum; /图的当前顶点数int arcnum; /图的当前弧数GraphKind kind; /图的种类标志MGraph;/*以下操作默认是无向网，即Kind = AG*/*顶点是名称字母。书上的是数字，例如v*Status LocateVex(MGraph G,char u)if(G.vexnum = 0) return -1; /图不存在int i;for(i = 0;i G.vexnum;i+)if(G. = u)return i;return -2; /图中不存在与u相等的点Status CreateGraph(MGraph& G)int i,j,k;VRType w; char v1,v2;char data50;cout 你想要创建几个顶点？ G.vexnum;cout 你想要创建几条弧？ G.arcnum;cout 依次输入顶点名称: endl;for(i = 0;i G.; /构造顶点向量for(i = 0;i G.vexnum;i+)for(j = 0;j G.vexnum;j+)G.arcsij.adj = INFINITY; /初始化邻接矩阵G. = NULL;for(k = 0;k G.arcnum;k+) /构造邻接矩阵cout v1 v2;cout 输入这条边的权值: w;cout 输入这条边的信息: data;i = LocateVex(G,v1);j = LocateVex(G,v2);G.arcsij.adj = w; G. = data;G.arcsji = G.arcsij;return 1;Status DestroyGraph(MGraph& G)G.vexnum = NULL;G.arcnum = NULL;return 1;char* GetVex(MGraph G,char v)if(G.vexnum = 0) return NULL;int i;i = LocateVex(G,v);if(i = 0) /判断是否是图上的顶点，后面的函数省略了这一步return G.vexsi.data;else return NULL;Status PutVex(MGraph& G,char v,char* value)if(G.vexnum = 0) return 0;int i;i = LocateVex(G,v);G.vexsi.data = value;return 1;/VertexType FirstAdjVex(MGraph G,char v) /返回第一个邻接顶点，邻接表操作/VertexType NextAdjVex(MGraph G,char v,char w) /邻接表操作Status InsertVex(MGraph& G,char v)if(G.vexnum = 0) return 0;int i;G.vexsG. = v;G.vexnum+;for(i = 0;i G.vexnum;i+)G.arcsiG.vexnum - 1.adj = INFINITY;G.arcsG.vexnum - 1i.adj = INFINITY;return 1;Status DeleteVex(MGraph& G,char v)if(G.vexnum = 0) return 0;int i,j,k;k = LocateVex(G,v);for(i = 0,j = 0;i G.vexnum;i+)if(G.arcsik.adj != INFINITY)j+;for(i = k;i data = NULL;G.vexnum-;G.arcnum = G.arcnum - j;return 1;Status InsertArc(MGraph& G,char v,char w)if(G.vexnum = 0) return 0;int i,j;VRType q;char data50;i = LocateVex(G,v);j = LocateVex(G,w); cout 输入这条边的权值: q;cout 输入这条边的信息: data;G.arcsij.adj = q;G. = data;G.arcsji = G.arcsij;G.arcnum = G.arcnum + 2;return 1;Status DeleteArc(MGraph& G,char v,char w)if(G.vexnum = 0) return 0;int i,j;i = LocateVex(G,v);j = LocateVex(G,w);G.arcsij.adj = INFINITY;G. = NULL;G.arcsji = G.arcsij;G.arcnum = G.arcnum - 2;return 1;Status Print(MGraph G)int i,j;for(i = 0;i G.vexnum ;i+)for(j = 0;j G.vexnum ;j+)cout G.arcs ij.adj ;cout endl;return 1;int main()int j;char i,c,d;MGraph G;CreateGraph(G);cout 此时矩阵为: endl;Print(G);cout i;j = LocateVex(G,i);cout i为第 j+1 个顶点 endl;cout 为两个点添加边，输入添加边的两个顶点: c d;InsertArc(G,c,d);cout 此时矩阵为: endl;Print(G);DeleteArc(G,c,d);cout 添加顶点V； endl;cout 此时矩阵