nodejs适合网站开发,专业公司网站制作公司,上海外贸网站推广公司,网站买了服务器后该怎么做文章目录 图的基本概念邻接矩阵邻接表图的遍历BFSDFS 图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构 顶点和边#xff1a;图中结点称为顶点
权值:边附带的数据信息 路径 #xff1a;
简单路径 和 回路#xff1a;
子图#xff1a;设图G {V, E}和图G1… 文章目录 图的基本概念邻接矩阵邻接表图的遍历BFSDFS 图的基本概念
图是由顶点集合及顶点间的关系组成的一种数据结构 顶点和边图中结点称为顶点
权值:边附带的数据信息 路径
简单路径 和 回路
子图设图G {V, E}和图G1 {V1E1}若V1属于V且E1属于E则称G1是G的子图
连通图在无向图中若从顶点v1到顶点v2有路径则称顶点v1与顶点v2是连通的。如果图中任意一对顶点都是连通的则称此图为连通图
生成树一个连通图的最小连通子图称作该图的生成树。有n个顶点的连通图的生成树有n个顶点和n-1条边
生成树就是用最少的边连通起来
最小生成树:构成生成树这些边加起来权值是最小的。
顶点的度
邻接矩阵 #pragma once
#includemap
#includevector
#includealgorithm
#includeassert.h
#includestring
#include functional
#includeiostream
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:vectorV _vertex; //顶点集合 mapV, int _indexMap; //顶点映射下标 vector vectorW _matrix; //邻接矩阵};void TestGraph(){Graphchar, 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
{templateclass Wstruct Edge{int _dsti;//目标点的下标 W _w;//权值EdgeW *_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 EdgeW 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:vectorV _vertex; //顶点集合 mapV, int _indexMap; //顶点映射下标 vector Edge* _table; //邻接表};void TestGraph(){string a[] { 张三, 李四, 王五, 赵六 };Graphstring, 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);queueint q;vectorbool 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 ,vectorbool 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) //遍历顶点通过下标找顶点{vectorbool v(_vertex.size(), false); //防止走重复的路size_t srci GetVertexIndexMap(src);_DFS(srci, v);}完整测试代码
#pragma once
#includemap
#includevector
#includealgorithm
#includeassert.h
#includestring
#include functional
#includeiostream
#includequeue
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);queueint q;vectorbool 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 ,vectorbool 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) //遍历顶点通过下标找顶点{vectorbool v(_vertex.size(), false); //防止走重复的路size_t srci GetVertexIndexMap(src);_DFS(srci, v);}public:vectorV _vertex; //顶点集合 mapV, int _indexMap; //顶点映射下标 vector vectorW _matrix; //邻接矩阵};void TestGraph(){Graphchar, 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[] { 张三, 李四, 王五, 赵六, 周七 };Graphstring, 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
{templateclass Wstruct Edge{int _dsti;//目标点的下标 W _w;//权值EdgeW *_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 EdgeW 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:vectorV _vertex; //顶点集合 mapV, int _indexMap; //顶点映射下标 vector Edge* _table; //邻接表};void TestGraph(){string a[] { 张三, 李四, 王五, 赵六 };Graphstring, int, true g1(a, 4);g1.AddEdge(张三, 李四, 100);g1.AddEdge(张三, 王五, 200);g1.AddEdge(王五, 赵六, 30);g1.Print();}
}
