概念:
图是另一种非线性结构，由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构。
完全图：在由n个顶点组成的无向图中，若有N(N-1)/2条边，则称为无向完全图。（也就是说任意两个顶点间都有边相连）
权重：在一些图中，边具有与之相关的数值，称为权重。（权重可以表示从一个顶点到另一个顶点的距离/花费的代价/所需的时间/次数等）
临接顶点：如果(u,v)是图中的一条边，则u和v互为临接顶点。
度：与顶点v关联的边的数目称为顶点v的度。
路径：在图G=（V,E）中，若从顶点V1出发，沿着边经过若干顶点V2,V5…到达V10，则称(V1,V2,V5,…V10)为从V1到V10的路径。
连通图：在无向图中V1到V2有路径，则称V1和V2是连通的，如图中任意两个顶点都是连通的，则称此图是连通图。
强连通图：在有向图中，若每一对顶点之间都存在路径，则称此图为强连通图。
生成树：一个无向连通图的生成树是它的极小连通子图，若图中有N个节点，则其生成树有N-1条边构成。
图的存储
一，临接矩阵
临接矩阵：将所有的顶点的信息组织成一个顶点表，然后利用矩阵来表示各顶点之间的临接关系，称为临接矩阵。
无向图的临接矩阵：
有向图的临接矩阵
//临接矩阵
template<class V,class W,bool digraph = false>
class GraphMartix
{
public:
GraphMartix(V* vertexs,size_t n)
{
_vertexs.reserve(n);//扩容
for (size_t i = 0; i < n; ++i)
{
_vertexs.push_back(vertexs[i]);
_indexMap[vertexs[i]] = i;//用下标记录
}
_martix.resize(n);//初始化二维数组
for (size_t i = 0; i < _martix.size(); ++i)
{
_martix[i].resize(n);
}
}
//获取顶点下标
size_t GetVertexIndex(const V& v)
{
assert(_indexMap.count(v) == 1);//已经存在
return _indexMap[v];
}
//添加边 源 目标 权值
void AddEdge(const V& src,const V& dst,const W& w)
{
size_t srcIndex = GetVertexIndex(src);
size_t dstIndex = GetVertexIndex(dst);
//权值
_martix[srcIndex][dstIndex] = w;
if (digraph == false)//是无向图
_martix[dstIndex][srcIndex] = w;
}
protected:
map<V,size_t> _indexMap;//顶点和权值
vector<V> _vertexs;//顶点集合
//W** _martix; //临接矩阵
vector<vector<W>> _martix;//二维数组临接矩阵
};
可以看出，临接矩阵虽然简单，但浪费的空间太多，尤其是有向图时，大多空间是0，解决这种问题的方法我们使用临接表来存储。
无向图的临接表：
有向图的临接表：
//临接表
template<class W>
struct LinKEdge
{
W _w;
size_t _srcIndex;//下标
size_t _dstIndex;//临接顶点
LinKEdge<W>* _next;
LinKEdge(size_t srcIndex,size_t dstIndex,const W& w)
:_srcIndex(srcIndex),_dstIndex(dstIndex),_w(w)
{}
};
template<class V,bool digraph = false>
class GraphTable
{
typedef LinKEdge<W> Edge;
public:
GraphTable(V* vertex,size_t n)
{
_vertex.reserve(n);
for (size_t i = 0; i < n; ++i)
{
_vertex.push_back(vertex[i]);
_indexMap[vertex[i]] = i;
}
_linkTables.resize(n,NULL);
}
//获取顶点下标
size_t GetVertexIndex(const V& v)
{
assert(_indexMap.count(v) == 1);//已经存在
return _indexMap[v];
}
void _AddEdge(size_t srcIndex,const W& w)
{
Edge* tmp = new Edge(srcIndex,dstIndex,w);
tmp->_next = _linkTables[srcIndex];
_linkTables[srcIndex] = tmp;
}
void AddEdge(const V& src,const W& w)
{
size_t srcIndex = GetVertexIndex(src);
size_t dstIndex = GetVertexIndex(dst);
_AddEdge(srcIndex,w);
if (digraph == false)//无向
_AddEdge(dstIndex,srcIndex,w);
}
private:
vector<V> _vertex;
map<V,size_t> _indexMap;
vector<Edge*> _linkTables;
};
图的遍历
广度优先遍历（GFS）
广度优先遍历相当于将一个图按照一圈一圈由里及外进行遍历，即遍历完一个父节点，就开始一次遍历它的孩子节点，所以，二叉树的层序遍历其实就是广度优先遍历.
void GFS(const V& src)
{
size_t srcIndex = GetVertexIndex(src);
queue<size_t> q;
//标记已经访问过的
vector<bool> visited;
while (!q.empty())
{
size_t front = q.front();
q.pop();
if (visited[front] == true)//已经访问过了
continue;
cout << front << _vertex[front] << "->";
visited[front] = true;
Edge* cur = _linkTables[front];
while (cur)
{
if (visited[cur->_dstIndex] == false)
{
q.push(cur->_dstIndex);
}
cur = cur->_next;
}
}
}
深度优先遍历（DFS）
深度优先遍历就是一条路走到底，相当于二叉树的前序遍历。
void DFS(const V& src)
{
size_t srcIndex = GetVertexIndex(src);
vector<bool> visited;
visited.resize(_vertex.size(),false);
_DFS(srcIndex,visited);
}
void _DFS(size_t srcIndex,vector<bool>& visited)
{
cout << srcIndex << _vertex[srcIndex] << "->";
visited[srcIndex] = true;
Edge* cur = _linkTables[srcIndex];
while (cur)
{
if (visited[cur->_dstIndex] == false)
{
_DFS(cur->_dstIndex,visited);//子问题
}
cur = cur->_next;
}
}