图——图的定义与操作
1，树中结点可以有多个后继，而每个结点都只有一个直接前驱，因此形成了一种层次结构；如果树中的每个结点也可以有多个直接前驱，那么这种层次结构都被破坏了；这样就会形成网状结构，会是一种新的数据结构，图；
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
2，图的定义：
1，图是由顶点集合（Vertex）及顶点间的关系集合（Edge）组成的一种数据结构 Graph = (V, E)，其中，V = {x | x 属于数据对象}，是顶点的有穷非空集合（顶点集），E = {(x, y) | x, y 属于 V } 是顶点之间的关系的有穷集合（边集，可以为空）；
3，无向边：
1，顶点 x 和 y 之间的边没有方向，则称该边为无向边；
2，(x, y) 与 (y, x) 意义相同，表示 x 和 y 之间有连接；
4，无向图：
1，图中任意两个顶点之间的边均是无向边，则称该图为无向图；
5，有向边：
1，顶点 x 和 y 之间的边有方向，则称该边为有向边；
2，<x, y> 与 <y, x> 意义不同：
1，<x, y> 表示从 x 连接到 y，x 称为尾，y 称为头；
2，<y, x> 表示从 y 连接到 x，y 称为尾，x 称为头；
6，有向图：
1，图中任意两个顶点之间的边均是有向边，则称该图为有向图；
7，无向图可以看作一种特殊的有向图，后续代码实现图的数据结构只考虑有向图；
8，顶点邻接（Adjacent）的定义：
1，无向图：
1，如果 (x, y) 属于 E，则称顶点 x 和 y 互为邻接；
2，有向图：
1，如果 <x, y> 属于 E，则称顶点 x 邻接到顶点 y；
9，度（Degree）的定义：
1，顶点 v 的度是和 v 相关联的边的数目，记为 TD(v)：
1，入度：以 v 为头的边的数目，记为 ID(v)；
2，出度：以 v 为尾的边的数目，记为 OD(v)；
2，推论：
10，权（Weight）的定义：
1，与图的边相关的数据元素叫做权；
2，权常用来表示图中顶点间的距离或者耗费；
11，图的一些常用的操作：
1，设置顶点的值；
2，获取顶点的值；
3，获取邻接顶点；
4，设置边的值；
5，删除边；
6，获取顶点数；
7，获取边数；
12，图在程序中表现为一种特殊的数据类型：
13，图抽象类的创建：
1 #ifndef GRAPH_H 2 #define GRAPH_H 3 4 #include "Object.h" 5 6 using namespace std; 7 namespace DTLib 8 { 9 10 /* 设置边的数据结构，用于邻接链表 */ 11 template < typename E > 12 struct Edge : public Object 13 { 14 int b; // 起点 15 int e; // 终点 16 E data; // 权值 17 18 Edge(int i=-1, int j=-1) 19 { 20 b = i; 21 e = j; 22 } 23 24 Edge(int i, int j, const E& value) 25 { 26 b = i; 27 e = j; 28 data = value; 29 } 30 31 /* 相等和不等不需要对权值进行比价，只比较起始点位置，删除顶点操作中查找操作用到,在此处定义了 */ 32 bool operator == (const Edge<E>& obj) 33 { 34 return (b == obj.b) && (e == obj.e); 35 } 36 37 bool operator != (const Edge<E>& obj) 38 { 39 return !(*this == obj); 40 } 41 42 bool operator < (const Edge<E>& obj) 43 { 44 return (data < obj.data); // 权值比较边的大小 45 } 46 47 bool operator > (const Edge<E>& obj) 48 { 49 return (data > obj.data); // 权值比较边的大小 50 } 51 }; 52 53 /* 抽象类不能够用来继承，能用来定义指针 */ 54 template < typename V, typename E > 55 class Graph : public Object 56 { 57 public: 58 virtual V getVertex(int i) = 0; // V 表示与顶点相关联的数据类型 59 virtual bool getVertex(int i, V& value) = 0; 60 virtual bool setVertex(int i, const V& value) = 0; 61 virtual SharedPointer< Array<int> > getAdgacent(int i) = 0; 62 virtual bool isAdjacent(int i, int j) = 0;//i和j 是否连接，只能在继承中实现 63 virtual E getEdge(int i, int j) = 0;// E表示与边相关联的数据类型,得到边上的//权值 64 virtual bool getEdge(int i, int j, E& value) = 0; 65 virtual bool setEdge(int i, int j, const E& value) = 0; 66 virtual bool removeEdge(int i, int j) = 0; 67 virtual int vCount() = 0; 68 virtual int eCount() = 0; 69 virtual int OD(int i) = 0; 70 virtual int ID(int i) = 0; 71 virtual int TD(int i) // 顶点 i 的度，即与顶点 i 相关联的边的数目 72 { 73 return OD(i) + ID(i); // 出度加上入度 74 } 75 }; 76 } 77 #endif // GRAPH_H
14，小结：
1，图是顶点与边的集合，是一种非线性的数据结构；
2，图中顶点可以与多个其他顶点产生邻接关系；
3，图中的边有与之对应的权值，表示顶点间的距离；
4，图在程序中表现为特殊的数据类型；
