【数据结构】图

图的概念

这里写图片描述
1. 图
  图是一种非线性数据结构,由顶点的集合及顶点间的关系(边)组成;G=(V, E),其中顶点集合V是有穷非空集合;E={(x,y) | x, y属于V}或E={<x,y> | x, y属于V}是顶点间关系的有穷集合,也叫做边的集合;其中第一种圆括号表示x到y的一条双向通路,即:(x,y)(y,x)是一条边,这种边与顶点构成的图叫做无向图;第二种尖括号表示x到y的一条单向通路,也就是说:<x, y>是从x到y的一条边与<y,x>并不是同一个,这种边与顶点构成的图叫做有向图。
  
2. 完全图
  在无向图中,如果任意两条顶点之间有且仅有一条边,即:有n个顶点,就有n*(n-1)/2条边,则称此图为无向完全图;
  在有向图中,如果任意两条顶点之间有且仅有方向相反的边,那么称此图为有向完全图;若有n条边,则有n*(n-1)条边。
  
3. 邻接顶点
  在无向图中,如果(x,y)是图中的一条边,则称x与y互为邻接顶点,边(x,y)依附于顶点x和y;
  在有向图中,如果<x,y>是图中的一条边,则称顶点x邻接到y,y邻接自x,边(x,y)与顶点x,y相关联。
  
4. 顶点的度:顶点的度是与顶点相关的边的个数。在无向图中,我们把以顶点v为终点的边的条数称为入度,把以顶点v为起始点的边的个数称为出度,有向图顶点的度等于入度与出度之和。

5. 权:边附带的数据信息
例如:
这里写图片描述
6. 路径与路径长度
  从顶点x出发有一组边可以使其到达顶点y,则称这一组边为顶点x到顶点y的路径。
  对于不带权的图:路径长度是该路径上边的条数;对于带权的图,路径长度为路径上各个边的权值之和。
  
7. 子图:设图G={V, E}和图G1={V1, E1},若V1属于V且E1属于E,则称G1是G的子图。

8. 连通图与强连通图
  在无向图中,任意两个顶点之间都有一条路径,那么称此图为连通图;n个顶点的连通图至少有n-1条边。
  在有向图中,任意两个顶点v1,v2之间都存在一条从v1到v2,从v2到v1的路径,那么称此图为强连通图。
  
9. 生成树:一个连通图的最小连通子图叫做该图的生成树。生成树不唯一。
这里写图片描述

图的存储

邻接矩阵

  我们将用一个数组表示顶点的集合,利用矩阵表示顶点间的关系
例如:
这里写图片描述
可以看到如果是无向图,我们得到的邻接矩阵是对称的。
代码如下:

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
template <class V, class W, bool IsDirect = false>//false表示为无向图
class Graph
{
public:
     Graph(const V* arr, size_t size)
          : _v(arr, arr + size)
     {
          _edges.resize(size);
          for (size_t i = 0; i < size; i++)
               _edges[i].resize(size);
     }
     int GetIndex(const V& v)
     {
          for (size_t i = 0; i < _v.size(); i++)
          {
               if (_v[i] == v)
                    return i;
          }
          assert(false);
          return -1;
     }
     void AddEdges(const V v1, const V v2, const W& weight)//存储边
     {
          size_t index1 = GetIndex(v1);
          size_t index2 = GetIndex(v2);
          _edges[index1][index2] = weight;
          if (!IsDirect)//无向图需要两次,有向图只需要一次 false为无向图
               _edges[index2][index1] = weight;
     }
     void Print()//打印矩阵
     {
          for (size_t i = 0; i < _v.size(); i++)
          {
               printf("%c ", _v[i]);
               for (size_t j = 0; j < _v.size(); j++)
               {
                    printf("%2d ", _edges[i][j]);
               }
               cout << endl;
          }
     }
     size_t Dev(const V& v)//计算顶点的度
     {
          size_t index = GetIndex(v);
          size_t count = 0;//false表示无向图,无向图度的计算是遍历一行,
                           //true是有向图,有向图度的计算:出度+入度
          for (size_t i = 0; i < _v.size(); i++)
          {
               if (_edges[index][i] > 0)
                    count++;
               if (IsDirect && _edges[i][index] > 0)
                    count++;
          }
          return count;
     }
private:
     vector<V> _v;
     vector<vector<W>> _edges;
};

  对于带权的图,我们可以将1改成权值;如果没有某条边,可以把0改成无穷大;对角线上自己到自己的边,仍然存为0。
  利用邻接矩阵存储图结构,有可能出现顶点很多,边却很少的情况,此时就会有大量的0元素,造成空间浪费。

邻接表

  利用数组表示顶点的集合,利用好链表表示边的关系。把顶点在数组中的下标存放到链表的数据域中。
  对于无向图,每条边在邻接表中出现两次;要计算某个结点的,只需要将vi对应的链表遍历一遍即可。例如,下图中,A的度为2,D的度为1
  对于有向图,每条边在邻接表中只出现一次;与顶点vi对给你个的邻接表,其结点的个数为出度;检测其他所有顶点对应的边链表,结点中的dst为i的个数是入度。例如:A的出度为1,入度为1,所以A的度为2。
  对于有向图,我们可以选择出度表或者入度表,出度表,简单来说,就是箭头指向的顶点对应的下标存储在链表结点中;入度表,箭头的根部对应的顶点的下标。如下图所示:
例如:
这里写图片描述
下面看代码:

#include <vector>
#include <iostream>
using namespace std;
template <class W>
struct Node
{
     Node(const W& weight, size_t src, size_t dst)
     : _weight(weight)
     , _src(src)
     , _dst(dst)
     , _pNext(NULL)
     {}
     W _weight;
     size_t _src;
     size_t _dst;
     Node* _pNext;
};
template <class V, class W, bool IsDirect = false>//无向图为false;有向图为true
class Graph
{
     typedef Node<W> Node;
     typedef Node* pNode;
public:
     Graph(const V* arr, size_t size)
          : _v(arr, arr + size)
     {
          _linkEdges.resize(size);
     }
     int GetIndex(const V& v)
     {
          for (size_t i = 0; i < _v.size(); i++)
          {
               if (_v[i] == v)
                    return i;
          }
          return -1;
     }
     void AddEdges(const V& v1, const V& v2, const W& weight)
     {
          size_t srcIndex = GetIndex(v1);
          size_t dstIndex = GetIndex(v2);
          _Add(srcIndex, dstIndex, weight);
          if (!IsDirect)//false 无向图
               _Add(dstIndex, srcIndex, weight);
     }
     size_t Dev(const V& v)
     {
          size_t count = 0;
          size_t index = GetIndex(v);
          pNode pCur = _linkEdges[index];
          while (pCur)//如果是无向图,直接计算度,如果是有向图先计算出度
          {
               count++;
               pCur = pCur->_pNext;
          }
          if (IsDirect)
          {
               for (size_t i = 0; i < _v.size(); i++)//计算有向图的入度
               {
                    if (i != index)
                    {
                         pCur = _linkEdges[i];
                         while (pCur)
                         {
                              if (pCur->_dst == index)
                                   count++;
                              pCur = pCur->_pNext;
                         }
                    }
               }
          }
          return count;
     }
private:
     void _Add(const size_t src, const size_t dst, const W& weight)
     {
          pNode pNew = new Node(weight, src, dst);
          pNode pCur = _linkEdges[src];

          pNew->_pNext = _linkEdges[src];
          _linkEdges[src] = pNew;
     }
private:
     vector<V> _v;
     vector<pNode> _linkEdges;
};
相关文章
相关标签/搜索