图的存储结构（1）：数组表示法

2024-07-11 04:47| 来源: 网络整理| 查看: 265

引言：图是一种较线性表和树更为复杂的数据结构。在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；在树形结构中，数据元素之间有明显的层次关系，每一层的数据元素只能与下一层的多个元素相关，但只能和上一层中的一个元素相关；而在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。因此这对于刚掌握c语言的学生来说掌握图这种数据结构，并且可以用完整的代码实现还是有一定困难的！特别是数据结构（严蔚敏版）！但是随着时间的推移，越发觉得严蔚敏老师写的程序实在是精妙！以下程序是根据数据结构上严蔚敏老师算法片段而写的完整的数组表示法！

例子：

数组表示法的特点: 1、用二维数组存储有n个顶点的图时，需要存放n个顶点信息和n^2个弧的信息。若图是无向图，根据无向图的邻接矩阵的对称性，则可采用压缩存储的方式只存入矩阵的下三角或上三角元素。 2、根据邻接矩阵容易判定任意两个顶点之间是有边（或弧）相连，并且容易求得各个顶点的度。 3、对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的元素之和。 4、对于有向图，顶点vi的出度是邻接矩阵中第i行的元素之和。

#include using std::cin; using std::cout; using std::endl; #include #define INFINITY 0 //两个顶点之间无边或弧时的数值 #define MAX_VERTEX_NUM 26 //最大顶点个数 #define MAX_INFO 10 //弧相关信息的字符串的最大长度 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 typedef int Status; typedef int VRType; //顶点关系类型 typedef char InfoType; typedef char VertexType[MAX_VERTEX_NUM]; //顶点类型 enum GraphKind{DG,DN,UDG,UDN}; //有向图，有向网，无向图，无线网 typedef struct { VRType adj; // VRType是顶点关系类型，对无权图，用1或0 //表示相邻否，对带权图，则为权值类型 InfoType *info; // 该弧相关信息的指针 }ArcCell, AdjMartix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMartix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前顶点个数和弧数 GraphKind kind; //图的种类标志 }MGraph; int LocateVex(MGraph G,VertexType u) //若图中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息 { for(int i = 0; i < G.vexnum; ++i) if(strcmp(u,G.vexs[i]) == 0) return i; return -1; } Status CreateDG(MGraph &G) //采用数组（邻接矩阵）表示法，构造有向图 { int i,j,k,l,IncInfo; char a[MAX_INFO]; VertexType va,vb; cout

【本文地址】

公司简介

联系我们