71_图的定义与操作

关键词：图的定义、无向边与无向图、无向边与无向图、顶点邻接（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