【数据结构】图

图的概念

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,bool IsDirect = false>//无向图为false；有向图为true
class Graph
{
     typedef Node<W> Node;
     typedef Node* pNode;
public:
     Graph(const 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;
};