图——图的定义与操作

时间:2019-05-26 15:37:00 来源:互联网 作者: 神秘的大神 字体:

1,树中结点可以有多个后继,而每个结点都只有一个直接前驱,因此形成了一种层次结构;如果树中的每个结点也可以有多个直接前驱,那么这种层次结构都被破坏了;这样就会形成网状结构,会是一种新的数据结构,图;

  

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,图在程序中表现为特殊的数据类型;