《图的基本操作.docx》由会员分享，可在线阅读，更多相关《图的基本操作.docx（5页珍藏版）》请在三一办公上搜索。
1、图的基本操作/*图的邻接矩阵储存表示* #define INFINITY INT_MAX /最大值为无穷大 #define MAX_VERTEX_NUM 20 /最大顶点个数 #include using namespace std; typedef enum DG,DN,AG,ANGraphKind; /有向图，有向网，无向图，无向网 typedef int Status; typedef int VRType; typedef char InfoType; typedef struct ArcCell VRType adj; /表示顶点关系，对于无向图有向图用0和1表示是否相邻，对于有向图
2、有向网用权值类型表示 InfoType* info; /该弧相关信息的指针 ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct /点的值 char name; char* data; VertexTypeMAX_VERTEX_NUM; typedef struct VertexType vexs; /顶点向量 AdjMatrix arcs; /邻接矩阵 int vexnum; /图的当前顶点数 int arcnum; /图的当前弧数 GraphKind kind; /图的种类标志 MGraph; /*以下操作默认是无向网，
3、即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.vexsi.name = 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 你想要创
4、建几条弧？ G.arcnum; cout 依次输入顶点名称: endl; for(i = 0;i G.vexsi.name; /构造顶点向量 for(i = 0;i G.vexnum;i+) for(j = 0;j G.vexnum;j+) G.arcsij.adj = INFINITY; /初始化邻接矩阵 G.arcsij.info = NULL; for(k = 0;k G.arcnum;k+) /构造邻接矩阵 cout v1 v2; cout 输入这条边的权值: w; cout 输入这条边的信息: data; i = LocateVex(G,v1); j = LocateVex(G,v2
5、); G.arcsij.adj = w; G.arcsij.info = 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 retu
6、rn 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 =
7、0) return 0; int i; G.vexsG.vexnum.name = 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.a
8、dj != 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.arcsij.in
9、fo = 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.arcsij.info = NULL; G.arcsji = G.arcsij; G.arcnum = G.arcnum - 2; return 1; Status Print
10、(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 此时矩阵为: endl; Print(G); c = V; InsertVex(G,c); cout 此时矩阵为: endl; Print(G); cout 删除顶点B； endl; d = B; DeleteVex(G,d); cout 此时矩阵为: endl; Print(G); DestroyGraph(G); return 0;
