图论基础,如何快速上手图论?
目录
引言-对前面数据结构的总结和图论的引导
一.图的基础概念和基本术语
1.1,图的定义
1.2,图的种类 -有向图和无向图以及完全图
1.2.1有向图和无向图
1.2.2完全图和非完全图
1.3,图的基本术语
1.3.1度,路径,环...
1.3.2强连通图和弱连通图
1.3.3权与网
1.3.4连通分量->生成树
二,图的存储结构
2.1邻接矩阵法
2.2邻接表法
2.3.1无向图的邻接表法编辑
2.3.2有向图的邻接表法
2.3 邻接表和邻接矩阵的比较
三.图的遍历-BFS/DFS
3.1,DFS遍历
3.2,BFS遍历
引言-对前面数据结构的总结和图论的引导
前面我们学过了一些基本的数据结构,像顺序表,链表,栈,队列,树等...其中最有难度的就属树的部分了,而图论的与树也是有关联的,在后续我们经常可以看到一些图类似树,但是又不是树,他们的区别在哪?二叉树是父亲节点和孩子的关联,是从上到下的,而图没有父亲节点和孩子节点,他主要使用节点描述各个事件之间的关系;
一.图的基础概念和基本术语
1.1,图的定义
图是由顶点集合及顶点间的关系组成的一种数据结构：G（Graph） = (V， E)，其中：V代表顶点,E代表边;
1.2,图的种类 -有向图和无向图以及完全图
1.2.1有向图和无向图
这里我举个例子就十分显而易见了:所谓向就是方向的意思,有向,就是节点的连接是有方向性的;
上图的G2就是一个无向图,各个节点之间连接的边是没有箭头的;
而G1是一个有向图,G1的各个节点之间连接的边是有箭头的,那就是方向;
1.2.2完全图和非完全图
什么完全图呢,完全图就是每个节点都要与其他所有的节点连接;
对于无向图来说:假设图的节点个数是n,如果满足这个图的边数是n(n-1)/2,那他就是无向完全图;
对于有向图来说:假设图的节点个数是n,如果满足这个图的边数是n(n-1),那他就是有向完全图;
注意:无向完全图一定成环;
非完全图:不是完全图的图就是非完全图;
是否是完全图的判断方法:因为完全图是每个顶点之间都有连接的,所以我们只要发现有任意两个顶点之间没有连接,就说明不是完全图;反之,如果找不到,就是完全图;
1.3,图的基本术语
1.3.1度,路径,环...
1.3.2强连通图和弱连通图
强连通图(相对有向图)):任意顶点到达其他的顶点,也能从其他顶点回到该顶点;
就下图来说:强连通图部分;因为是连通图,所有V1是可以到达V2,V3,V0的;如果要说他强不强,那就看V2,V3,V4可不可以回到V1;可以回来,就是强连通图;
1.3.3权与网
权:就是边所代表的值,一般是长度,也叫权值;
网:边有权值的图叫网;
子图:从原图中抽出至少一条边或者一个顶点以及该顶点有关的边的图就是子图;子图要满足的条件是定点与原图的顶点数量一样,但是边的数量要小于原图的边的数量;
图(b)抽掉了V0-V3,V1-V2,
1.3.4连通分量->生成树
连通分量:是原图的连通子图,
极大连通分量:在该连通子图中,在加上任意一条边或一个顶点,都不再联通;
上图中,(V0,V1,V2,V3)所组成的联通子图和(V4,V5)组成联通子图都是极大联通子图;
下面是有向图的联通分量;
同理极小联通子图就是本身是联通的,但是再删除任意一条边和定点就不联通了,通常极小联通子图中,两个顶点之间只有一条边;(正因如此,才可以转化为二叉树)
最小生成树:就是权值之和最小的生成树;后序会提到求最小生成树的两种算法:克鲁斯卡尔(kruskal)和普利姆(Prim)算法;
二,图的存储结构
2.1邻接矩阵法
邻接矩阵法是以顶点映射的下标创建二维数组:通常需要两步;
一:创建顶点集合:这里需要获取定点的个数和提供通过顶点映射对应下标的方法;
二:通过顶点的数量构建二维数组:横坐标表示顶点的出度,纵坐标表示顶点的入度;如果是无向图且V1->V2连接,那么graph[V1][V2]=1(二维矩阵初始化为0);如果是有向图,还需要令graph[V2][V1]=0;
下面是邻接矩阵的code模拟:
//非类型模版参数分别为 定点类型,权值,权值最大值(标示值/无穷大),有向/无相
template <class V,class W,W MAX_W=INT_MAX,bool direction=true>
class Graph
{
public:
Graph() = default;
Graph(const V*a,size_t n)
{
_vertexs.reserve(n);//预留空间
//初始化顶点集
for (size_t i = 0; i < n; i++)
{
_vertexs.push_back(a[i]); //把数组中的顶点放到容器中
_indexMap[a[i]] = i;//映射下标
}
_matirx.resize(n);//可有可无
//初始化邻接矩阵
for (size_t i = 0; i < _matirx.size(); i++)
{
//使用最大的权值去表示
_matirx[i].resize(n, MAX_W);
//size_t src=_indexMap[]
}
}
//根据起点,终点,权值添加边
void Addedge(const V& src, const V& dst, const W& w)
{
//获取定点下标
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
//在邻接矩阵中对应位置更新权值
_matirx[srci][dsti] = w;
if (direction == false)//无向图
{
_matirx[dsti][srci] = w; //多添加一次
}
}
//打印邻接矩阵
void showmatirx()
{
cout << "邻接矩阵:" << endl;
cout << " ";
for (int i = 0; i < _vertexs.size(); i++)
printf("%3c", _vertexs[i]);
cout << endl;
for (int i = 0; i < _matirx.size(); i++)
{
printf("%3c", _vertexs[i]);
for (int j = 0; j < _matirx.size(); j++)
{
if (_matirx[i][j] != INT_MAX)
printf("%3d", _matirx[i][j]);//如果有权值,就打印
else
printf(" *");
}
cout << endl;
}
}
private:
//确定顶点的下标
size_t GetVertexIndex(const V& v)
{
//检查定点是否合法
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
assert(false);//如果没有找到就断死
return -1;
}
}
vector<V>_vertexs;//顶点集合
map<V, int>_indexMap;//获得定点对应的下标关系
vector<vector<W>>_matirx;//邻接矩阵
};2.2邻接表法
邻接表法就是采用链表的方式存储;下面是无向图和有向图的邻接表法示意图;
2.3.1无向图的邻接表法
2.3.2有向图的邻接表法
下面是邻接表的code模拟实现:
namespace GraphLink
{
template<class W>
struct Edge
{
int _dsti;
W _w;
Edge<W>* _next;
Edge(const int& dsti, const W& w)
:_dsti(dsti),
_w(w),
_next(nullptr)
{}
};
template <class V, class W, W MAX_W = INT_MAX, bool direction = true>
class Graph
{
public:
typedef Edge<W> Edge;
Graph() = default;
Graph(const V* a, size_t n)
{
_vertexs.reserve(n);//预留空间
//初始化顶点集
for (size_t i = 0; i < n; i++)
{
_vertexs.push_back(a[i]); //把数组中的顶点放到容器中
_indexMap[a[i]] = i;//映射下标
}
//初始化邻接表
_tables.resize(n, nullptr);
//开出n个指针,指向空
}
//根据起点,终点,权值添加边
void Addedge(const V& src, const V& dst, const W& w)
{
//获取定点下标
size_t srci = GetVertexIndex(src);
size_t dsti = GetVertexIndex(dst);
Edge* eg=new Edge(dsti,w);//创建节点
//头插
eg->_next = _tables[srci];
_tables[srci] = eg;
//如果是无向图就需要再添加一条边
if (direction == false)
{
Edge* eg = new Edge(srci, w);
eg->_next = _tables[dsti];
_tables[dsti] = eg;
}
}
//打印邻接表
void show()
{
cout << "顶点信息" << endl;
//打印顶点信息
for (int i = 0; i < _vertexs.size(); i++)
cout << '[' << i << ']' << _vertexs[i] << endl;
cout << endl;
//遍历邻接表
cout << "邻接表:" << endl;
for (int i = 0; i < _tables.size(); i++)
{
cout << _vertexs[i] << '[' << i << "]->";
Edge* cur = _tables[i];//该行的头结点
while (cur)
{
cout << _vertexs[cur->_dsti] << '[' << cur->_dsti << ']'<<"("<<cur->_w<<")"<<"->";
cur = cur->_next;
}
cout << "nullptr";
cout << endl;
}
}
private:
//确定顶点的下标
size_t GetVertexIndex(const V& v)
{
//检查定点是否合法
auto it = _indexMap.find(v);
if (it != _indexMap.end())
{
return it->second;
}
else
{
assert(false);//如果没有找到就断死
return -1;
}
}
vector<V>_vertexs;//顶点集合
map<V, int>_indexMap;//获得定点对应的下标关系
vector<Edge*>_tables;//邻接表
};
void graphtest()
{
const char str[4] = { 'A','B','C','D' };
cout << "无向图:" << endl;
Graph<char, int, INT_MAX, false>g(str, 4);
g.Addedge('A', 'B', 6);
g.Addedge('A', 'C', 3);
g.Addedge('B', 'C', 10);
g.Addedge('A', 'D', 4);
g.show();
cout << endl << "有向图:" << endl;
Graph<char, int, INT_MAX, true>g2(str, 4);
g2.Addedge('A', 'B', 6);
g2.Addedge('A', 'C', 3);
g2.Addedge('B', 'C', 10);
g2.Addedge('A', 'D', 4);
g2.show();
return;
}
};2.3 邻接表和邻接矩阵的比较
区别:对于任意无向图和有向图,邻接矩阵都是唯一的(编号按照顶点顺序),但是邻接表是不唯一的,因为他的连接顺序跟顶点编号无关;
空间复杂度:
1.邻接矩阵因需要双层循环遍历,所以空间复杂度是O(n2);
2.邻接表的空间复杂度是O(n);
三.图的遍历-BFS/DFS
图的遍历主要氛围两种:1.深度优先遍历(DFS),2.广度优先遍历(BFS);
深度优先遍历主要实现方法是赌递归调用(堆栈),而广度优先遍历的实现方法是队列;
3.1,DFS遍历
分析:深度优先遍历每次每的每一层都会遍历顶点集合,找到没有访问过的顶点就会递归调用;
void _DFS(size_t srci, vector<bool>& check) //下一个位置的起点以及需要一个标记数组
{
cout << srci << ":" << _vertexs[srci] << " " << endl; //先访问 然后标记为访问过
check[srci] = true;
for (size_t i = 0; i < _vertexs.size(); ++i)
if (_matrix[srci][i] != MAX_W && check[i] == false)
_DFS(i, check);
}
void DFS(const V& src) //需要有一个起点
{
size_t srci = GetVertexIndex(src);//找到起点的下标
vector<bool> check(_vertexs.size()); //标记数组
_DFS(srci, check);
//如果是一个非连通图，可以在后面再进行一层检查check数组，然后对false的数组再进行一次访问
}3.2,BFS遍历
广度优先遍历其实就是层序遍历,一层一层的扩散;需要用到普通队列;
层序遍历 但是没有一层一层出
void BFS(const V& src) //src表示我们的起点
{
size_t srci = GetVertexIndex(src);//找到起点的下标
queue<int> q;//存储下标的队列
size_t n = _vertexs.size();//表示有多少个节点
vector<bool> check(n);
q.push(srci);
check[srci] = true;//入队列就标记
while (!q.empty())
{
int front = q.front();//取队头
q.pop();
cout << _vertexs[front] << ":"<<front<<endl;
//然后让他的朋友进
for (size_t i = 0; i < n; ++i)
if (_matrix[front][i] != MAX_W && check[i] == false)
{
q.push(i);
check[i] = true;
}
}
}