图
2020-05-02 16:00:29来源:博客园 阅读 ()
图
图在数据结构中是多对多的关系,一个顶点可以和多个顶点有联系。其通常表示为:G(V,E)
,其中G
表示一个图,V
表示图的顶点集合,E
表示图的边集合。
1.图的定义
有向图:
图中任意两个顶点间的边都是有向边,则称该图为有向图。连接两个顶点间的有向边称为弧,弧起点称为弧头,终点称为弧尾,表示方法为<A,B>
,A
为弧尾,B
为弧头。
如果图中任意两个顶点间都存在互为来往的有向边,则称该图为有向完全图。有向完全图的边长总数为\(n*(n-1)\),其中n
是顶点个数。
有向图顶点的度和弧的关系:\(e=\sum_{i=1}^{n}ID(v_i)=\sum_{i=1}^{n}OD(v_i)\)。其中e
是图的边长总数,n
为图的顶点总数,\(ID(v_i)\)是顶点的入度,\(OD(v_i)\)是顶点的出度。
无向图:
图中任意两个顶点间的边都是无向的,则称该图为无向图。无向边表示方法为(A,B)
。
如果图中任意两个顶点间都存在无向边,则称该图为无向完全图。无向完全图的边长总数是\(n*(n-1)/2\),其中n
是顶点个数。
无向图顶点的度和边长的关系:\(e=\frac{1}{2}\sum_{i=1}^{n}TD(v_i)\)。其中\(TD(v_i)\)是顶点\(v_i\)的度,e
是图的边长总数,n
为图的顶点总数。
网:
边或弧带权的图称为网。
2.图的存储结构
邻接矩阵:
图的邻接矩阵存储方式是将图的顶点和图的边或弧分开存储,将图的顶点存入到一个一维数组,图的边或弧存储到二维数组。
邻接矩阵是一个\(n*n\)的方阵,表示方法如下:
\(arc[i][j]=\left\{\begin{array}{}1,若(v_i,v_j)\in\textbf{E}或<v_i,v_j>\in\textbf{E}, \\ 0,反之\end{array}\right.\)
定义数据结构为:
const int MAXVEX=100;//顶点的最大个数
template<class VertexType,class EdgeType>
class MGraph
{
//成员数据私有化
private:
VertexType vexs[MAXVEX]; //顶点表
EdgeType arc[MAXVEX][MAXVEX];//邻接矩阵
int numVertexs,numEdges;
};
构造一个图:
void Creat
原文链接:https://www.cnblogs.com/cqy-wt1124/p/12818829.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 数据结构—链表 2020-05-29
- 【数据结构】树套树——线段树套平衡树 2020-04-18
- 数据结构之顺序表的实现 2020-04-06
- 数据结构-线性表 2020-03-28
- 单调队列 2020-02-07
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash