图数据类型的定义
程序员文章站
2022-12-21 23:31:54
图 介绍 图是相较于树更复杂的一种数据结构类型,它表示了多对多的对应关系。图的结构其实就是一些顶点和一些边的集合。图又分为有向图和无向图。存储图的方法有很多,比如使用邻接矩阵,邻接表,十字链表和邻接多重表等等。下面我们一一介绍一下这些内容。 图的结构: 无向图: 无向图其实就 ......
图
介绍
图是相较于树更复杂的一种数据结构类型,它表示了多对多的对应关系。图的结构其实就是一些顶点和一些边的集合。图又分为有向图和无向图。存储图的方法有很多,比如使用邻接矩阵,邻接表,十字链表和邻接多重表等等。下面我们一一介绍一下这些内容。
图的结构:
无向图:
无向图其实就是说顶点与顶点之间的关系没有方向,只有说是连接的还是断开的。
有向图:
相对的,有向图就是顶点与顶点之间不仅有断开还是连接的关系,还要明确到是谁指向谁。
对顶点和边的定义
先是顶点
class node //顶点类 { public: char m_cdata; //顶点数据 bool m_bisvisited; //判断此顶点是否被访问过,这是为了后面实现某些功能设定的 node() {} //无参构造函数 node(char data) //含参构造函数 { m_cdata = data; m_bisvisited = false; //默认没有被访问过 } };
再是边
class edge { public: int m_inodeindexa; //边连接的a顶点 int m_inodeindexb; //边连接的b顶点 int m_iweightvalue; //边上的权值,这也是为了后面某些功能设定的 bool m_bis_selected;//标记这个边是否被选过 edge(int nodeindexa, int nodeindexb, int weightvalue) //构造函数 { m_inodeindexa = nodeindexa; m_inodeindexb = nodeindexb; m_iweightvalue = weightvalue; m_bis_selected = false; //初始默认这个边没有被选择过 } edge(){} //无参构造函数 };
图的存储方法
这里只介绍一种邻接矩阵,剩下的以后再补充。顾名思义,邻接矩阵其实就是一个矩阵,用一个二维数组来定义它。我们将顶点存储在一个数组里面,假如有5个顶点,那么邻接矩阵就应该是一个5*5的二维数组。
对于无向图来说,我们用1表示连接,用0表示未连接,设数组名为maritx,那么matrix[1][3] = 0表示顶点数组中下标为1的顶点和下标为3的顶点没有连接关系,matrix[1][0] = 1表示下标为1的顶点和下标为0的顶点连接在了一起。通过观察可以发现,无向图的邻接矩阵是一个上三角和下三角对称的矩阵,而其主对角线上元素全为0,比较不能自己和自己连接在一起。
而对于有向图,如果下标为1的元素指向了下标为2的元素,而下标为2的元素却没有指向下标为1的元素,那么matrix[1][2] = 1且matrix[2][1] = 0
对图的定义(代码实现)
定义里面有些一下数据成员是为了后面实现某些算法才加的。
class cmap { private: int m_icapacity; //图中最多可以容纳的顶点数 int m_inodecount; //已经添加的顶点数 node* m_pnodearray; //用来存放顶点数组 int* m_pmatrix; //用来存放邻接矩阵 edge* m_pedge; //用来存最小生成树的边 public: cmap(int capacity) { m_icapacity = capacity; m_inodecount = 0; m_pnodearray = new node[m_icapacity]; //分配内存 m_pmatrix = new int[m_icapacity * m_icapacity]; memset(m_pmatrix, 0, m_icapacity * m_icapacity * sizeof(int));//将m_pmatrix所有元素初始化为0 m_pedge = new edge[m_icapacity - 1]; //最小生成树边的个数就等于顶点个数减一 } ~cmap() { delete[]m_pnodearray; delete[]m_pmatrix; delete[]m_pedge; } }