青海公路建设信用信息服务网站,深圳全网营销,ui设计网课一般多少钱,小俊哥网站建设文章目录 1.原题2.算法思想3.关键代码4.完整代码5.运行结果 1.原题
有n个顶点的无向图#xff0c;使用邻接矩阵作为存储结构。为减少存储空间#xff0c;使用数组按照行主映射方式仅保存下三角矩阵。请给出映射公式#xff0c;并编写算法计算给定顶点的度。叙述算法思想并用… 文章目录 1.原题2.算法思想3.关键代码4.完整代码5.运行结果 1.原题
有n个顶点的无向图使用邻接矩阵作为存储结构。为减少存储空间使用数组按照行主映射方式仅保存下三角矩阵。请给出映射公式并编写算法计算给定顶点的度。叙述算法思想并用C实现说明算法的复杂性
2.算法思想
对于左下三角直接用映射公式对于右上三角通过对称的特点转为左下三角再用映射公式
3.关键代码
/*** brief 压缩邻接矩阵为一维数组左下三角** 将二维邻接矩阵压缩为一维数组仅存储左下三角部分的数据。** param adjMatrix 二维数组表示的邻接矩阵* param compressedMatrix 用于存储压缩后的矩阵的一维数组*/
void compressAdjacencyMatrix(int adjMatrix[NUM_VERTICES][NUM_VERTICES],int compressedMatrix[NUM_VERTICES * (NUM_VERTICES 1) / 2]) {int index 0;// 遍历二维矩阵的左下三角部分for (int i 0; i NUM_VERTICES; i) {for (int j 0; j i; j) {// 将左下三角的数据压缩到一维数组中compressedMatrix[index] adjMatrix[i][j];index;}}
}/*** brief 计算给定顶点的度利用压缩矩阵** 使用压缩的邻接矩阵计算给定顶点的度数。** param vertex 给定顶点的索引* param compressedMatrix 压缩后的矩阵存储图的连接关系* return int 给定顶点的度数*/
int calculateDegree(int vertex, int compressedMatrix[NUM_VERTICES * (NUM_VERTICES 1) / 2]) {int degree 0;// 遍历矩阵中与给定顶点相关的元素for (int i 0; i NUM_VERTICES; i) {// i 大于 vertex 表示右上部分的矩阵if (i vertex) {// 根据公式 i * (i 1) / 2 vertex 计算出压缩后的矩阵位置degree compressedMatrix[i * (i 1) / 2 vertex];}// i 小于 vertex 表示左下部分的矩阵else if (i vertex) {// 根据公式 vertex * (vertex 1) / 2 i 计算出压缩后的矩阵位置degree compressedMatrix[vertex * (vertex 1) / 2 i];}}return degree;
}4.完整代码
/*** file main.c* brief 实现了邻接矩阵及其操作。*/#include stdio.h#define NUM_VERTICES 6/*** brief 压缩邻接矩阵为一维数组左下三角** 将二维邻接矩阵压缩为一维数组仅存储左下三角部分的数据。** param adjMatrix 二维数组表示的邻接矩阵* param compressedMatrix 用于存储压缩后的矩阵的一维数组*/
void compressAdjacencyMatrix(int adjMatrix[NUM_VERTICES][NUM_VERTICES],int compressedMatrix[NUM_VERTICES * (NUM_VERTICES 1) / 2]) {int index 0;// 遍历二维矩阵的左下三角部分for (int i 0; i NUM_VERTICES; i) {for (int j 0; j i; j) {// 将左下三角的数据压缩到一维数组中compressedMatrix[index] adjMatrix[i][j];index;}}
}/*** brief 计算给定顶点的度利用压缩矩阵** 使用压缩的邻接矩阵计算给定顶点的度数。** param vertex 给定顶点的索引* param compressedMatrix 压缩后的矩阵存储图的连接关系* return int 给定顶点的度数*/
int calculateDegree(int vertex, int compressedMatrix[NUM_VERTICES * (NUM_VERTICES 1) / 2]) {int degree 0;// 遍历矩阵中与给定顶点相关的元素for (int i 0; i NUM_VERTICES; i) {// i 大于 vertex 表示右上部分的矩阵if (i vertex) {// 根据公式 i * (i 1) / 2 vertex 计算出压缩后的矩阵位置degree compressedMatrix[i * (i 1) / 2 vertex];}// i 小于 vertex 表示左下部分的矩阵else if (i vertex) {// 根据公式 vertex * (vertex 1) / 2 i 计算出压缩后的矩阵位置degree compressedMatrix[vertex * (vertex 1) / 2 i];}}return degree;
}/*** brief 打印邻接矩阵* param adjMatrix 邻接矩阵*/
void printAdjacencyMatrix(int adjMatrix[NUM_VERTICES][NUM_VERTICES]) {for (int i 0; i NUM_VERTICES; i) {for (int j 0; j NUM_VERTICES; j) {printf(%d , adjMatrix[i][j]);}printf(\n);}
}/*** brief 主函数用于测试邻接矩阵及其操作*/
int main() {int adjMatrix[NUM_VERTICES][NUM_VERTICES] {{0, 1, 1, 0, 0, 0},{1, 0, 0, 1, 0, 0},{1, 0, 0, 1, 1, 0},{0, 1, 1, 0, 0, 1},{0, 0, 1, 0, 0, 1},{0, 0, 0, 1, 1, 0}};printf(Adjacency Matrix:\n);printAdjacencyMatrix(adjMatrix);int compressedMatrix[NUM_VERTICES * (NUM_VERTICES 1) / 2];compressAdjacencyMatrix(adjMatrix, compressedMatrix);printf(Compressed Matrix:\n);for (int i 0; i NUM_VERTICES * (NUM_VERTICES 1) / 2; i) {printf(%d , compressedMatrix[i]);}int vertex 3; // 输入要计算度的顶点int degree;degree calculateDegree(vertex - 1, compressedMatrix);printf(\nDegree of vertex %d is %d\n, vertex, degree);return 0;
}5.运行结果
