用邻接矩阵表示图形数据结构的方法

#pragma once //图的邻接矩阵存储结构 #include "SeqList.h" typedef struct { SeqList Vertices; //存放顶点的顺序表 int edge[MaxVertices][MaxVertices];//存放边的邻接矩阵 int numOfEdges; //边的条数 }AdjMGraph; //图的结构体定义 //初始化 void Initiate(AdjMGraph *G, int n) { int i, j; for(i=0;i<n;i++) for (j = 0; j < n; j++) { if (i == j) { G->edge[i][j] = 0; } else { G->edge[i][j] = MaxWeight; //MaxWeight表示无穷大 } } G->numOfEdges = 0; //边的条数置零 ListInitiate(&G->Vertices); //顺序表初始化 } //插入顶点 void InsertVertex(AdjMGraph *G, DataType vertex) { //在途中插入顶点Vertex ListInsert(&G->Vertices, G->Vertices.size, vertex);//在顺序表尾部插入 } /* 插入边 在有向图中插入一条有向边。对于增加无向边的操作，可通过增加两条有向边完成。 */ void InsertEdge(AdjMGraph *G, int v1, int v2, int weight) { //在图中插入边<v1,v2>,边<v1,v2>的权为weight if (v1 < 0 || v1 >= G->Vertices.size || v2 < 0 || v2 >= G->Vertices.size) { printf("参数v1或v2越界出错!\n"); return; } G->edge[v1][v2] = weight; G->numOfEdges++; } /* 删除边 在图中删除一条有向边。对于删除无向边的操作，可通过取消两条有向边完成 */ void DeleteEdge(AdjMGraph *G, int v1, int v2) { //在图中删除边<v1,v2> if (v1 < 0 || v1 >= G->Vertices.size || v2 < 0 || v2 >= G->Vertices.size || v1 == v2) { printf("参数v1或者v2越界出错!\n"); return; } if (G->edge[v1][v2] == MaxWeight || v1 == v2) { printf("该边不存在!\n"); return; } G->edge[v1][v2] = MaxWeight; G->numOfEdges--; } /* 取第一个邻接顶点 对于邻接矩阵来说，顶点v的第一个邻接顶点，就是邻接矩阵的顶点v行中 从第一个矩阵元素开始的非0且非无穷大的顶点 */ int GetFirstVex(AdjMGraph G, int v) //在图G中寻找序号为v的顶点的第一个邻接顶点 //如果这样的邻接顶点存在，则返回该邻接顶点的序号，否则返回-1 { int col; if (v < 0 || v >= G.Vertices.size) { printf("参数v1越界出错"); return -1; } else { for (col = 0; col < G.Vertices.size; col++) { if (G.edge[v][col] > 0 && G.edge[v][col] < MaxWeight) return col; } return -1; } } /* 取下一个邻接顶点 对于邻接矩阵存储结构来说，顶点v1的邻接顶点v2的下一个邻接顶点，就是邻接矩阵的顶点 v行中从第v2+1个矩阵元素开始的非0且非无穷大的顶点 */ int GetNextVex(AdjMGraph G, int v1, int v2) { //在图中寻找v1的顶点的邻接顶点v2的下一个邻接顶点 //如果这样的邻接顶点存在，则返回该邻接顶点的序号，否则返回-1 //v1和v2都是相应顶点的序号 int col; if (v1 < 0 || v1 >= G.Vertices.size || v2 < 0 || v2 >= G.Vertices.size) { printf("参数v1或v2越界出错!\n"); return -1; } for (col = v2 + 1; col < G.Vertices.size; col++) { if (G.edge[v1][col] > 0 && G.edge[v1][col] < MaxWeight) return col; } return -1; }