# 【数据结构】：图

```//临接矩阵
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;//二维数组临接矩阵
};```

```//临接表
template<class W>
{
W _w;
size_t _srcIndex;//下标
size_t _dstIndex;//临接顶点

LinKEdge(size_t srcIndex, size_t dstIndex, const W& w)
:_srcIndex(srcIndex)
, _dstIndex(dstIndex)
, _w(w)
{}
};

template<class V,class W,bool digraph = false>
class GraphTable
{
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;
}
}

//获取顶点下标
size_t GetVertexIndex(const V& v)
{
assert(_indexMap.count(v) == 1);//已经存在
return _indexMap[v];
}

void _AddEdge(size_t srcIndex, size_t dstIndex, const W& w)
{
Edge* tmp = new Edge(srcIndex, dstIndex, w);
}

void AddEdge(const V& src, const V& dst, const W& w)
{
size_t srcIndex = GetVertexIndex(src);
size_t dstIndex = GetVertexIndex(dst);

if (digraph ==  false)//无向
}

private:
vector<V> _vertex;
map<V, size_t> _indexMap;
};```

```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;
while (cur)
{
if (visited[cur->_dstIndex] == false)
{
q.push(cur->_dstIndex);
}
cur = cur->_next;
}
}
}```

```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;