关键词：图的定义、无向边与无向图、无向边与无向图、顶点邻接（Adjacent）的定义、度（Degree）的定义、 权（Weigh）的定义、图的一些常用操作、 图的继承关系
0. 图的定义
图是由顶点集合（Vertex）及顶点间的关系集合（Edge）组成的一种数据结构：Graph=(V, E)
- V = {x | x ∈ 某个数据对象} 是顶点的有穷非空集合
- E = {(x, y) | x, y ∈V}是顶点之间关系的有穷集合
1. 无向边与无向图
- 无向边：顶点x和顶点y之间的边没有方向，则称该边为无向边，(x, y)与(y, x)意义相同，表示x和y之间有连接
- 无向图：途中任意两个顶点之间的边均为无向边，则称该图为无向图
2. 有向边与有向图
- 有向边：顶点x和y之间的边有方向，则称该边为有向边
- <x,y>与<y, x> 意义不同：
<x,y>表示从x连接到y，x称为尾，y称为头；
<y, x>表示从y连接到x，y称为尾，x称为头。 - 有向图：图中任意两个顶点之间的边均是有向边，则称该图为有向图
无向图可以看作是一种特殊的有向图
3. 顶点邻接（Adjacent）的定义
- 无向图：如果(x, y) ∈ E，则称顶点x和y互为邻接
- 有向图：如果<x, y> ∈ E，则称顶点x邻接到顶点y
4. 度（Degree）的定义
- 顶点v的度是和v相关联的边的数目，记为
TD(v) - 入度：以v为头的边的数目，记为
ID(v) - 出度：以v为尾的边的数目，记为
OD(v) - 推论：
TD(v) = ID(v) + OD(v)
Count(E) = ID(v1) + ID(v2) + ... + ID(vn)
Count(E) = OD(v1) + OD(v2) + ... + OD(vn)
Count(E) = [ TD(v1) + TD(v2) + ... + TD(vn)] / 2
5. 权（Weigh）的定义
- 与图的边相关的数据元素叫做权
-
权常用来表示图中顶点间的距离或者耗费
带权有向图
6. 图的一些常用操作
- 设置顶点的值
- 获取顶点的值
- 获取邻接顶点
- 设置边的值
- 删除边
- 获取顶点数
- 获取边数
等等
7. 图的继承关系
template < typename T, typename E >
class Graph : public Object
{
public:
virtual V getVertex(int i) = 0;
virtual bool getVertex(int i, V& value) = 0;
virtual bool setVertex(int i, const V& value) = 0;
virtual SharedPointer< Array<int> > getAdjacent(int i) = 0;
virtual E getEdge(int i, int j) = 0;
virtual bool getEdge(int i, int j, E& value) = 0;
virtual bool setEdge(int i, int j, const E& value) = 0;
virtual bool removeEdge(int i, int j) = 0;
virtual int vCount() = 0;
virtual int eCount() = 0;
virtual int OD(int i) = 0;
virtual int ID(int i) = 0;
virtual int TD(int i)
{
return OD(i) + ID(i);
}
};
8. 小结
- 图是顶点与边的集合，是一种给非线性的数据结构
- 图中顶点可以与多个其他顶点产生邻接关系
- 图中的边有与之对应的权值，表示顶点间的距离
- 图在程序中表现为特殊的数据类型
声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4
网友评论