文章目录
- 图的基本概念
- 邻接矩阵
- 邻接表
- 图的遍历
- BFS
- DFS
图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构
顶点和边：图中结点称为顶点
权值:边附带的数据信息
路径 ： 
简单路径 和 回路：
子图：设图G = {V, E}和图G1 = {V1，E1}，若V1属于V且E1属于E，则称G1是G的子图
连通图：在无向图中，若从顶点v1到顶点v2有路径，则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的，则称此图为连通图
生成树：一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边
生成树就是用最少的边连通起来
最小生成树:构成生成树这些边加起来权值是最小的。
顶点的度：
邻接矩阵
#pragma once
#include<map>
#include<vector>
#include<algorithm>
#include<assert.h>
#include<string>
#include <functional>
#include<iostream>
using namespace std;
//矩阵
namespace matrix
{
//V是顶点 ，W是 weight 权值
template <class V, class W, W MAX_W = INT_MAX, bool Direction = false> //true是有向图 ，false是无向图
class Graph
{
public:
//手动添加边
Graph(const V* a, size_t n) //用指针数组 存储顶点
{
_vertex.reserve(n);
//初始化顶点和边
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_indexMap[a[i]] = i; //通过顶点找下标
}
_matrix.resize(n);
for (size_t i = 0; i < n; i++)
{
//将邻接矩阵的权值设置为最大值
_matrix[i].resize(n, MAX_W);
}
}
size_t GetVertexIndexMap(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else //没有找到
{
assert(false);
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
int srci = GetVertexIndexMap(src);
int dsti = GetVertexIndexMap(dst);
_matrix[srci][dsti] = w;
//无向图
if (Direction == false)
{
_matrix[srci][dsti] = w;
_matrix[dsti][srci] = w;
}
}
void Print()
{
//顶点
for (int i = 0; i < _vertex.size(); i++)
{
cout << "[" << i << "]" << "->" << _vertex[i] << endl;
}
//矩阵
cout << endl;
//打印横下标
cout << " ";
for (size_t i = 0; i < _vertex.size(); i++)
{
cout << i << " ";
}
cout << endl;
for (int i = 0; i < _matrix.size(); i++)
{
cout << i << " ";//打印竖下标
for (int j = 0; j < _matrix[0].size(); j++)
{
if (_matrix[i][j] == MAX_W)
{
cout << "*"<<" ";
}
else
{
cout << _matrix[i][j] <<" ";
}
}
cout << endl;
}
}
public:
vector<V> _vertex; //顶点集合
map<V, int> _indexMap; //顶点映射下标
vector< vector<W> > _matrix; //邻接矩阵
};
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.Print();
}
}
邻接表
邻接表：使用数组表示顶点的集合，使用链表表示边的关系
出边表：存储从各个顶点连接出去的边，出边表中下标为 i的位置存储的是从编号为i的顶点连接出去的边
入边表：存储连接到各个顶点的边，入边表中下标为i的位置存储的是连接到编号为 i的顶点的边
出边表和入边表的其中每个位置存储的都是一个链表
出边表中下标为i的位置表示从编号为i的顶点连接出去的边
入边表中下标为i 的位置表示连接到编号为i 的顶点的边
在实现邻接表时，一般只需要用一个出边表来存储从各个顶点连接出去的边即可，因为大多数情况下都是需要从一个顶点出发找与其相连的其他顶点，所以一般不需要存储入边表
//邻接表
namespace link_table
{
template<class W>
struct Edge
{
int _dsti;//目标点的下标
W _w;//权值
Edge<W> *_next; //用链表表示边的关系
Edge(int dsti, const W& w)
:_dsti(dsti)
, _w(w)
, _next(nullptr)
{
}
};
//V是顶点 ，W是 weight 权值
template <class V, class W, bool Direction = false> //true是有向图 ，false是无向图
class Graph
{
public:
typedef Edge<W> Edge;
//手动添加边
Graph(const V* a, size_t n) //用指针数组 存储顶点
{
_vertex.reserve(n);
//初始化顶点和边
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_indexMap[a[i]] = i; //通过顶点找下标
}
_table.resize(n, nullptr);
}
size_t GetVertexIndexMap(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else //没有找到
{
assert(false);
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
int srci = GetVertexIndexMap(src);
int dsti = GetVertexIndexMap(dst);
//头插
Edge *eg = new Edge(dsti,w);
//有向图
//添加从源顶点到目标顶点的边
eg->_next = _table[srci];
_table[srci] = eg;
//无向图
//添加从目标顶点到源顶点的边
if (Direction == false)
{
//????
Edge* eg = new Edge(srci, w);
eg->_next = _table[dsti];
_table[dsti] = eg;
}
}
void Print()
{
//顶点
for (int i = 0; i < _vertex.size(); i++)
{
cout << "[" << i << "]" << "->" << _vertex[i] << endl;
}
cout << endl;
//遍历顶点
for (size_t i = 0; i < _vertex.size(); i++)
{
cout << _vertex[i] << endl;
}
//遍历邻接表的目标点的下标和权值
for (size_t i = 0; i < _table.size(); i++)
{
cout << _vertex[i] << "[" << i << "]->";
Edge * cur = _table[i];
while (cur != nullptr)
{
cout << "[" << _vertex[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
public:
vector<V> _vertex; //顶点集合
map<V, int> _indexMap; //顶点映射下标
vector< Edge*> _table; //邻接表
};
void TestGraph()
{
string a[] = { "张三", "李四", "王五", "赵六" };
Graph<string, int, true> g1(a, 4);
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.Print();
}
}
图的遍历
BFS
void BFS(const V& src) //遍历顶点，通过下标找顶点
{
size_t srci = GetVertexIndexMap(src);
queue<int> q;
vector<bool> v(_vertex.size(), false); //防止走重复的路
q.push(srci);
v[srci] = true;
while (!q.empty())
{
int front = q.front();
q.pop();
cout << _vertex[front] << endl;
// 把front顶点的邻接顶点的下标入队列
for (size_t i = 0; i < _vertex.size(); i++)
{
if (_matrix[front][i] != MAX_W && v[i] == false)
{
q.push(i);
v[i] = true;
}
}
}
}
DFS
void _DFS( size_t srci ,vector<bool> & v)
{
cout << srci << ":" << _vertex[srci] << endl;
v[srci] = true;
// 找一个srci相邻的没有访问过的点，去往深度遍历
for (int i =0 ; i< _vertex.size() ; i++ )
{
if (v[i] ==false && _matrix[srci][i] != MAX_W)
{
_DFS(i ,v);
}
}
}
void DFS(const V& src) //遍历顶点，通过下标找顶点
{
vector<bool> v(_vertex.size(), false); //防止走重复的路
size_t srci = GetVertexIndexMap(src);
_DFS(srci, v);
}
完整测试代码
#pragma once
#include<map>
#include<vector>
#include<algorithm>
#include<assert.h>
#include<string>
#include <functional>
#include<iostream>
#include<queue>
using namespace std;
//矩阵
namespace matrix
{
//V是顶点 ，W是 weight 权值
//连通的,边的关系就用权值代替，如果两顶点不通，则使用无穷大代替
template <class V, class W, W MAX_W = INT_MAX, bool Direction = false> //true是有向图 ，false是无向图
class Graph
{
public:
//手动添加边
Graph(const V* a, size_t n) //用指针数组 存储顶点
{
_vertex.reserve(n);
//初始化顶点和边
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_indexMap[a[i]] = i; //通过顶点找下标
}
_matrix.resize(n);
for (size_t i = 0; i < n; i++)
{
//将邻接矩阵的权值设置为最大值
_matrix[i].resize(n, MAX_W);
}
}
size_t GetVertexIndexMap(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else //没有找到
{
assert(false);
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
int srci = GetVertexIndexMap(src);
int dsti = GetVertexIndexMap(dst);
_matrix[srci][dsti] = w;
//无向图
if (Direction == false)
{
_matrix[srci][dsti] = w;
_matrix[dsti][srci] = w;
}
}
void Print()
{
//顶点
for (int i = 0; i < _vertex.size(); i++)
{
cout << "[" << i << "]" << "->" << _vertex[i] << endl;
}
//矩阵
cout << endl;
//打印横下标
cout << " ";
for (size_t i = 0; i < _vertex.size(); i++)
{
cout << i << " ";
}
cout << endl;
for (int i = 0; i < _matrix.size(); i++)
{
cout << i << " ";//打印竖下标
for (int j = 0; j < _matrix[0].size(); j++)
{
if (_matrix[i][j] == MAX_W)
{
cout << "*"<<" ";
}
else
{
cout << _matrix[i][j] <<" ";
}
}
cout << endl;
}
}
void BFS(const V& src) //遍历顶点，通过下标找顶点
{
size_t srci = GetVertexIndexMap(src);
queue<int> q;
vector<bool> v(_vertex.size(), false); //防止走重复的路
q.push(srci);
v[srci] = true;
while (!q.empty())
{
int front = q.front();
q.pop();
cout << _vertex[front] << endl;
// 把front顶点的邻接顶点的下标入队列
for (size_t i = 0; i < _vertex.size(); i++)
{
if (_matrix[front][i] != MAX_W && v[i] == false)
{
q.push(i);
v[i] = true;
}
}
}
}
void _DFS( size_t srci ,vector<bool> & v)
{
cout << srci << ":" << _vertex[srci] << endl;
v[srci] = true;
// 找一个srci相邻的没有访问过的点，去往深度遍历
for (int i =0 ; i< _vertex.size() ; i++ )
{
if (v[i] ==false && _matrix[srci][i] != MAX_W)
{
_DFS(i ,v);
}
}
}
void DFS(const V& src) //遍历顶点，通过下标找顶点
{
vector<bool> v(_vertex.size(), false); //防止走重复的路
size_t srci = GetVertexIndexMap(src);
_DFS(srci, v);
}
public:
vector<V> _vertex; //顶点集合
map<V, int> _indexMap; //顶点映射下标
vector< vector<W> > _matrix; //邻接矩阵
};
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.Print();
}
void TestBDFS()
{
string a[] = { "张三", "李四", "王五", "赵六", "周七" };
Graph<string, int> g1(a, sizeof(a) / sizeof(string));
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.AddEdge("王五", "周七", 30);
g1.Print();
//g1.BFS("张三");
g1.DFS("张三");
}
}
//邻接表
namespace link_table
{
template<class W>
struct Edge
{
int _dsti;//目标点的下标
W _w;//权值
Edge<W> *_next; //用链表表示边的关系
Edge(int dsti, const W& w)
:_dsti(dsti)
, _w(w)
, _next(nullptr)
{
}
};
//V是顶点 ，W是 weight 权值
template <class V, class W, bool Direction = false> //true是有向图 ，false是无向图
class Graph
{
public:
typedef Edge<W> Edge;
//手动添加边
Graph(const V* a, size_t n) //用指针数组 存储顶点
{
_vertex.reserve(n);
//初始化顶点和边
for (size_t i = 0; i < n; i++)
{
_vertex.push_back(a[i]);
_indexMap[a[i]] = i; //通过顶点找下标
}
_table.resize(n, nullptr);
}
size_t GetVertexIndexMap(const V& v)
{
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else //没有找到
{
assert(false);
return -1;
}
}
void AddEdge(const V& src, const V& dst, const W& w)
{
int srci = GetVertexIndexMap(src);
int dsti = GetVertexIndexMap(dst);
//头插
Edge *eg = new Edge(dsti,w);
//有向图
//添加从源顶点到目标顶点的边
eg->_next = _table[srci];
_table[srci] = eg;
//无向图
//添加从目标顶点到源顶点的边
if (Direction == false)
{
//????
Edge* eg = new Edge(srci, w);
eg->_next = _table[dsti];
_table[dsti] = eg;
}
}
void Print()
{
//顶点
for (int i = 0; i < _vertex.size(); i++)
{
cout << "[" << i << "]" << "->" << _vertex[i] << endl;
}
cout << endl;
//遍历顶点
for (size_t i = 0; i < _vertex.size(); i++)
{
cout << _vertex[i] << endl;
}
//遍历邻接表的目标点的下标和权值
for (size_t i = 0; i < _table.size(); i++)
{
cout << _vertex[i] << "[" << i << "]->";
Edge * cur = _table[i];
while (cur != nullptr)
{
cout << "[" << _vertex[cur->_dsti] << ":" << cur->_dsti << ":" << cur->_w << "]->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
public:
vector<V> _vertex; //顶点集合
map<V, int> _indexMap; //顶点映射下标
vector< Edge*> _table; //邻接表
};
void TestGraph()
{
string a[] = { "张三", "李四", "王五", "赵六" };
Graph<string, int, true> g1(a, 4);
g1.AddEdge("张三", "李四", 100);
g1.AddEdge("张三", "王五", 200);
g1.AddEdge("王五", "赵六", 30);
g1.Print();
}
}
![[实战]API防护破解之签名验签](https://img-blog.csdnimg.cn/img_convert/d7d409f7b17f2bf4a03241991ca254d6.png)
