四个月没见，甚是想念，你是否和我一样沉淀了四个月，废话少说，现在我们继续数据结构-图的学习。
什么是图？
图是一种数学结构，由节点（顶点）和边组成。在图论中，每个节点代表一个实体或数据对象，而边则表示节点之间的连接或关系。边可以是有向的，即从一个节点指向另一个特定节点；也可以是非定向的，即两个节点相互连接。图通常分为两类：无向图，其中边没有方向；有向图，边的方向是明确的。
图的存储结构
我们知道图是由“边”和“节点”组成的，对于节点，我们可以维护一个vector数组，来进行顶点值的存储，那么边我们该如何存储呢？
首先，存在两个顶点就会有一个边，那么我们就可以通过顶点-顶点之间的关系，来表示边。这就衍生出两种表示方法：邻接矩阵和邻接表
邻接矩阵
因为节点与节点之间的关系就是连通与否，即为0或者1，因此邻接矩阵(二维数组)即是：先用一 个数组将定点保存，然后采用矩阵来表示节点与节点之间的关系。
邻接矩阵表示中我们需要区分：有向图和无向图
对于无向图，并且不考虑权值，我们可以通过edge[i][j] = 0表示这两个点没有联通，edge[i][j] = 1表示这两个点联通。如果需要考虑权值，那么不联通表示为edge[i][j] = INT_MAX，联通表示为edge[i][j] = weight
而对于有向图，我们也是通过邻接矩阵，不联通表示为edge[i][j] = INT_MAX，联通表示为edge[i][j] = weight
具体实现也是非常之简单的，看一下代码就能学会的
template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
class Graph
{
public:
Graph(const V* array, size_t size)
{
_vertex.reserve(size);
for (int i = 0; i < size; i++)
{
_vertex.emplace_back(array[i]);
_index_map[array[i]] = i;
}
// 初始化
_matrix.resize(size);
for (int i = 0; i < size; i++)
{
_matrix[i].resize(size, MAX_W); // 无穷大表示，没有连接
}
}
int GetVertexIndex(const V& vertex)
{
auto it = _index_map.find(vertex);
if (it == _index_map.end())
{
return -1; // 节点不存在就返回-1，因为矩阵下标为-1肯定不合法
}
return it->second;
}
void AddEdge(const V& src, const V& dest, const W& weight)
{
int src_index = GetVertexIndex(src);
int dest_index = GetVertexIndex(dest);
_matrix[src_index][dest_index] = weight;
// 无向图需要两方连接
if (Direction == false)
{
_matrix[dest_index][src_index] = weight;
}
}
void PrintGraph()
{
std::cout << "-------顶点-------" << std::endl;
for (const auto& num : _vertex)
{
std::cout << "[" << _index_map[num] << "]->" << num << std::endl;
}
std::cout << std::endl;
std::cout << "-------邻接矩阵------" << std::endl;
for (int i = 0; i < _matrix.size(); i++)
{
for (int j = 0; j < _matrix.size(); j++)
{
if (_matrix[i][j] == MAX_W)
{
std::cout << "* ";
}
else
{
std::cout << _matrix[i][j] << " ";
}
}
std::cout << std::endl;
}
std::cout << std::endl;
}
private:
std::vector<V> _vertex; // 存储顶点
std::vector<std::vector<W>> _matrix; // 存储边
std::map<V, int> _index_map; // 顶点映射下标
};
void TestGraph()
{
Graph<char, int, INT_MAX, true> g("0123", 4);
g.AddEdge('0', '1', 1);
g.AddEdge('0', '3', 4);
g.AddEdge('1', '3', 2);
g.AddEdge('1', '2', 9);
g.AddEdge('2', '3', 8);
g.AddEdge('2', '1', 5);
g.AddEdge('2', '0', 3);
g.AddEdge('3', '2', 6);
g.PrintGraph();
}领接表
如图：对于邻接表，就是对应每个顶点，如果顶点间有连接关系，有边，就维护在对应的链表中。跟我们哈希表的链式结构类似
所以和邻接矩阵作为区分，领接表就是维护一个数组，数组里面存储链表，链表节点结构如下
template<class W>
struct Edge
{
Edge(int dest, const W& w) : dest_index(dest), weight(w), next(nullptr)
{}
//int src_index;
int dest_index; // 目标点的下标
W weight; // 边的权值
Edge<W>* next;
};如果是有向图，那么就维护一端的链表关系即可
领接表方案也同样很简单 ，核心就是将二维数组改为，一个数组中维护一个链表
// 邻接表方案
namespace Table
{
template<class W>
struct Edge
{
Edge(int dest, const W& w) : dest_index(dest), weight(w), next(nullptr)
{}
//int src_index;
int dest_index; // 目标点的下标
W weight; // 边的权值
Edge<W>* next;
};
template<class V, class W, bool Direction = false>
class Graph
{
using Edge = Edge<W>;
public:
Graph(const V* array, size_t size)
{
_vertex.reserve(size);
for (int i = 0; i < size; i++)
{
_vertex.emplace_back(array[i]);
_index_map[array[i]] = i;
}
_table.resize(size, nullptr);
}
int GetVertexIndex(const V& vertex)
{
auto it = _index_map.find(vertex);
if (it == _index_map.end())
{
return -1;
}
return it->second;
}
void AddEdge(const V& src, const V& dest, const W& weight)
{
int src_index = GetVertexIndex(src);
int dest_index = GetVertexIndex(dest);
Edge* edge = new Edge(dest_index, weight);
// 这里我们之间进行头插
edge->next = _table[src_index]; // _table[src_index]对应的就是链表的头节点
_table[src_index] = edge;
// 尾插实现，比较麻烦
//if (current == nullptr)
//{
// _table[src_index] = edge;
//}
//else
//{
// while (current->next != nullptr)
// {
// current = current->next;
// }
// current->next = edge;
//}
if (Direction == false)
{
Edge* edge = new Edge(src_index, weight);
// 直接头插
edge->next = _table[dest_index];
_table[dest_index] = edge;
// 尾插实现，比较麻烦
//if (current == nullptr)
//{
// _table[dest_index] = edge;
//}
//else
//{
// while (current->next != nullptr)
// {
// current = current->next;
// }
// current->next = edge;
//}
}
}
void PrintGraph()
{
std::cout << "-------顶点-------" << std::endl;
for (const auto& num : _vertex)
{
std::cout << "[" << _index_map[num] << "]->" << num << std::endl;
}
std::cout << std::endl;
std::cout << "-------邻接表------" << std::endl;
for (int i = 0; i < _table.size(); i++)
{
Edge* current = _table[i];
while (current != nullptr)
{
std::cout << "[" << _vertex[i] << "]->" <<
_vertex[current->dest_index] << ", weight = " << current->weight << std::endl;
current = current->next;
}
std::cout << std::endl;
}
}
private:
std::vector<V> _vertex; // 存储顶点
std::map<V, int> _index_map; // 顶点映射下标
std::vector<Edge*> _table; // 邻接表
};
void TestGraph()
{
//Graph<char, int, true> g("0123", 4);
//g.AddEdge('0', '1', 1);
//g.AddEdge('0', '3', 4);
//g.AddEdge('1', '3', 2);
//g.AddEdge('1', '2', 9);
//g.AddEdge('2', '3', 8);
//g.AddEdge('2', '1', 5);
//g.AddEdge('2', '0', 3);
//g.AddEdge('3', '2', 6);
std::string strs[] = {"珠海", "广州", "深圳","中山"};
Graph<std::string, int, true> g(strs, 4);
g.AddEdge("珠海", "广州", 100);
g.AddEdge("珠海", "深圳", 160);
g.AddEdge("深圳", "广州", 19);
g.AddEdge("深圳", "中山", 59);
g.AddEdge("深圳", "珠海", 200);
g.AddEdge("广州", "中山", 100);
g.PrintGraph();
}
}图的相关概念
完全图
在有n个顶点的无向图中，若有n * (n-1)/2条边，即任意两个顶点之间有且仅有一条边，则称此图为无向完全图。在n个顶点的有向图中，若有n * (n-1)条边，即任意两个顶点之间有且仅有方向相反的边，则称此图为有向完全图
顶点的度
某一个顶点相关的边数。分为出度和进度，假设我们现在有顶点V，出度表示以V为顶点，箭头指向其他节点的边数。进度表示，其他节点为顶点，指向V这个节点的边数。
路径
在图G=(V, E)中，从一个顶点Vi出发，可以找到一组边，最终可以到达顶点Vj，这时这组边就是一条路径。
路径长度
对于不带权值的图，一条路径的路径长度是边的条数。对于带权图则是，各条边权值的和。
连通图
在无向图中，若顶点Vi到顶点Vj之间存储在路径，那么这两个顶点式联通的。如果图中的任意一对顶点都按都是联通的，那么这个图为连通图。
如果是有向图，我们只要实现任意的Vi到Vj有路径，任意的Vj到Vi有路径，就是强连通图。
图的遍历
图的遍历有两种对应的策略，一种是从目标节点走到最深的位置，一种是一层一层遍历。对应为深度优先、广度优先遍历。
深度优先遍历
深度优先遍历，就是从一个节点一路走到黑，不断的回溯。
我们在二叉树的学习中，前序、中序、后续遍历的本质就是深度优先搜索，不过，因为二叉树最多只有两条分支，而图可能有n条分支，对应就需要for循环在查找哪些分支是合法的。
我们可能会对下面深度优先遍历的代码有一点点疑惑，为什么要for循环，其实for循环核心就是遍历所有可能可以走的节点，对于二叉树而言能走的只有左右孩子，而对于图那么就可能有一个节点和无数个节点节点相连
下面就是深度优先遍历的代码
// 递归函数，通过下标进行搜索，hash来进行回溯时判断，是否走过
void dfs(size_t src_index, std::unordered_set<int>& hash)
{
std::cout << src_index << ":" << _vertex[src_index] << std::endl;
hash.insert(src_index);
// 当前对于src这个节点，我们要知道能走到哪些位置，也就是连接的节点
for (int i = 0; i < _matrix.size(); i++)
{
if (_matrix[src_index][i] != MAX_W && hash.count(i) == 0)
{
dfs(i, hash);
}
}
}
// 深度优先遍历
void DFS(const V& src)
{
std::unordered_set<int> hash;
int src_index = _index_map[src];
dfs(src_index, hash);
}广度优先遍历
广度优先遍历就是我们常说的，层序遍历，那么具体实现也就是和二叉树的层序遍历类似。
值得注意的是：二叉树的层序遍历，一定是自上往下的，而图的层序遍历，我们可能会出现暗某一个顶点重复入队，导致出现死循环的问题。
这个问题也跟图的性质有关，如果是图中两个顶点Vi, Vj互相指向，那么当我们出队Vi，入队Vj后，我们需要对Vj进行出队然后寻找Vj指向的节点，这时候又会把Vi重新插入队列中，这时就死循环！
所以在实际编写代码时我们要考虑，对于任意的节点只能够入队一次，这时我们可以通过哈希表来实现这个逻辑功能
实现代码：
// 广度优先遍历
void BFS(const V& src)
{
std::queue<int> q;
std::unordered_set<int> hash; // 谁进入队列，就插入哈希表
int src_index = _index_map[src];
q.push(src_index);
hash.insert(src_index);
int floor = 0; // 表示第几层
// 队列为空时，表示已经遍历完了
while (q.size() != 0)
{
int flag = q.size();
std::cout << "----第" << floor << "层-----" << std::endl;
floor++;
// 表示这一层有几个数需要出队
for (int i = 0; i < flag; i++)
{
int front = q.front();
q.pop();
std::cout << "pop: " << _vertex[front] << ", push: ";
for (int j = 0; j < _matrix.size(); j++)
{
if (_matrix[front][j] != MAX_W) // 权值合法，表示有链接
{
if (hash.count(j) == 0)
{
q.push(j);
hash.insert(j); // 谁进入队列，就插入哈希表
}
std::cout << _vertex[j] << ", ";
}
}
std::cout << std::endl;
}
std::cout << std::endl;
}
}测试样例
void TestBFS()
{
// 测试dfs、bfs
std::string strs[] = { "珠海", "广州", "深圳","中山","香港", "佛山" };
graph<std::string, int, int_max, false> g(strs, 6);
g.addedge("珠海", "中山", 100);
g.addedge("珠海", "深圳", 160);
g.addedge("中山", "广州", 19);
g.addedge("深圳", "香港", 59);
g.addedge("广州", "佛山", 200);
g.addedge("广州", "深圳", 100);
g.printgraph();
std::cout << "-------深度优先遍历-------------" << std::endl;
g.dfs();
std::cout << "-------广度优先遍历-------------" << std::endl;
g.bfs();
}到了这里什么是图、图的存储结构、如何遍历图我们已经完成了，这一部分较为简单。在下一篇博客中，我们将学习图的应用，图的最小生成树算法和最短路径算法。