福州企业网站维护价格低,酒店网站建设一般考虑哪些因素,网站的建设与维护就业方向,怎么样用ps做网站一、图介绍
1、定义
图由结点的有穷集合V和边的集合E组成。其中#xff0c;结点也称为顶点。一对结点#xff08;x#xff0c; y#xff09;称为边#xff08;edge#xff09;#xff0c;表示顶点x连接到顶点y。边可以包含权重/成本#xff0c;显示从顶点x到y所需的成…一、图介绍
1、定义
图由结点的有穷集合V和边的集合E组成。其中结点也称为顶点。一对结点x y称为边edge表示顶点x连接到顶点y。边可以包含权重/成本显示从顶点x到y所需的成本。若两个顶点之前存在一条边就表示这两个顶点具有相邻关系。
2、类型
1无向图 2有向图 3、表示方法
1邻接矩阵
邻接矩阵存储结构就是用矩阵表示图中各顶点之间的邻接关系两个顶点有邻接关系就记录为1否则为0。 2邻接表
邻接表是图的一种顺序存储与链式存储相结合的存储方式。 4、遍历方法
1广度优先搜索 2深度优先搜索 二、面试常考的算法
1、实现深度优先搜索 题目如下无向图从节点A开始遍历其深度优先搜索为A B D E F C。 思路深度优先搜索创建visited数组用于记录所有被访问过的顶点。
1从A出发访问A。
2找出A的第一个没有被访问的邻接点访问该点。以该顶点为新顶点重复此步骤直至刚访问过的顶点没有未被访问的邻接点为止。
3返回前一个访问过的仍有未被访问邻接点的顶点,继续访问该顶点的下一个未被访问邻接点。
4重复2,3步骤直至所有顶点均被访问搜索结束。
#includeiostream
using namespace std;
#includevector
#includeset
#includeunordered_set
#includemapclass Graph{private:mapchar, vectorchar graph; //创建图graph记录图的节点及邻接关系public:void add_edge(char node, vectorchar neibors){graph[node] neibors;}void dfs_helper(char node, mapchar, int visited){visited[node] 1;cout node ;for(auto n: graph[node]){// 判断当前节点的邻接节点有无被访问if(visited[n] ! 1)dfs_helper(n, visited);}}void dfs(char start_node){mapchar,int visited; // visited数组用来记录所有被访问过的顶点被访问过就记为1dfs_helper(start_node, visited);}
};int main(){Graph graph;graph.add_edge(A, {B, C});graph.add_edge(B, {A, D, E});graph.add_edge(C, {A, F});graph.add_edge(D, {B});graph.add_edge(E, {B, F});graph.add_edge(F, {C, E});graph.dfs(A);
} 2、实现广度优先搜索
题目如下无向图从节点A开始遍历其广度优先搜索为A B D C E从节点B开始遍历其广度优先搜索为B A C D E。 思路广度优先搜索利用队列来实现。把访问到的顶点入队再访问该顶点的所有相邻的顶点等访问完了该顶点的邻接点再出队顶点和其相邻的顶点每出队一个就入队该顶点的未访问过的邻接顶点重复上述步骤直到队列为空。
#includeiostream
#includequeue
#includemap
using namespace std;
class Graph{private:mapchar, vectorchar graph; //创建图graph记录图的节点及邻接关系public:void add_edge(char node, vectorchar neibors){graph[node] neibors;}// 层次广度遍历void bfs(char node){mapchar, int visited; // visited数组用来记录所有被访问过的顶点被访问过就记为1queuechar que;que.push(node);visited[node] 1;while(!que.empty()){char temp que.front(); //出队que.pop();cout temp ;node temp; //记录出队的点for(auto neibor: graph[node]){if(visited[neibor] ! 1)que.push(neibor); //访问出队点的邻接点并入队visited[neibor] 1; //已访问的顶点标记为1}}}
};int main(){Graph graph;graph.add_edge(A, {B, D});graph.add_edge(B, {A, C, D});graph.add_edge(C, {B, D, E});graph.add_edge(D, {A, B, C, E});graph.add_edge(E, {C, D});graph.bfs(B);
} 3、利用拓扑排序判断图是否有环路。
题目如下有向图判断是否存在环路。如果不为树输出其拓扑排序。 思路通过BFS实现拓扑排序。
1首先计算每个节点的入度将所有入度为0的节点放入队列中
2开始执行BFS我们取队首的节点u放入结果中移除u的所有出边即将u的所有相邻节点的入度减少1判断如果某个相邻的节点v的入度变为0就将v放入队列中。
3当BFS结束后如果答案中包含的节点数和图中的节点数相等那么就得到了图G的拓扑排序否则说明图中存在环不存在拓扑排序。
// 利用拓扑排序判断有向图是否存在回路
#includeiostream
#includemap
#includevector
#includequeue
using namespace std;
class Graph{private:mapchar, vectorchar graph;public:void add_edge(char node, vectorchar neibors){graph[node] neibors;}// 广度优先搜索队列判断void has_cycle(){mapchar, int indegree; //记录每个顶点的入度默认为0for(auto g: graph){indegree[g.first] 0;}//计算每个顶点的入度for(auto g: graph){char n g.first;for(auto nei: graph[n]){indegree[nei] 1;}}// 1、将所有入度为0的顶点入队queuechar que;for(auto in: indegree){char c in.first;if(in.second 0)que.push(c);}// 2、开始执行BFS每出队一个顶点就将该顶点的所有边移除// 即将该顶点所有相邻节点的入度减1如果某个相邻节点的入度变为0就将该节点放入队列中vectorchar tuopu;while(!que.empty()){char temp que.front();que.pop();tuopu.push_back(temp);for(auto neibor: graph[temp]){indegree[neibor] - 1;if(indegree[neibor] 0)que.push(neibor);}}// 3.判断拓扑排序结果里的顶点个数如果和图的个数相等则没有环if(tuopu.size() graph.size()){cout 该图没有环为树 endl 拓扑排序为;for(auto t: tuopu){cout t ;} }elsecout 该图有环不为树;}
};int main(){// 没有环Graph graph;graph.add_edge(A, {B, C});graph.add_edge(B,{});graph.add_edge(C,{D,E});graph.add_edge(D, {B});graph.add_edge(E, {});graph.has_cycle();// 有环Graph graph2;graph2.add_edge(A, {B, C});graph2.add_edge(B, {C});graph2.add_edge(C,{D,E});graph2.add_edge(D, {B});graph2.add_edge(E, {});graph2.has_cycle();return 0;
} 4、计算图的边数
题目给定如下无向图输出该图的边数7。 思路遍历图中的节点若该节点的邻接节点没有被访问则边数count1。
#includeiostream
#includequeue
#includemap
using namespace std;
class Graph{private:mapchar, vectorchar graph; //创建图graph记录图的节点及邻接关系public:void add_edge(char node, vectorchar neibors){graph[node] neibors;}// 计算图的边数void getNumsofEdge(){mapchar, int visited; //记录节点是否访问int count 0;// 遍历graph中的节点与邻接节点for(auto g: graph){char n g.first;for(auto neibor: graph[n]){if(visited[neibor] ! 1){count 1;}// 每遍历一个节点就将该节点标记为1visited[n] 1;}}cout count;}
};
int main(){Graph graph;graph.add_edge(A, {B, D});graph.add_edge(B, {A, C, D});graph.add_edge(C, {B, D, E});graph.add_edge(D, {A, B, C, E});graph.add_edge(E, {C, D});graph.getNumsofEdge();
} 5、找到两个顶点之间的最短路径
题目如下无向图A到F的路径有A-B-C-E-FA-B-C-FA-D-E-F输出最短路径A-D-E-F。 思路广度优先搜索BFS 队列实现。
1准备queue和mapqueue用于BFSmapchar, vectorchar用于存储当前最短距离。
2BFS将顶点node1入队并向Map中添加键值对。
3当队列非空时进行循环。现将队首元素x出队当前路径等x的当前路径然后遍历x的邻接节点如果邻接点中的某个节点tmp不在map键值对中相当于未访问过 就向Map中加入键值对tmp当前路径并将tmp入队如果tmp为node2就返回Map中tmp对应的路径。
#includeiostream
#includequeue
#includemap
using namespace std;
class Graph{private:mapchar, vectorchar graph; //创建图graph记录图的节点及邻接关系public:void add_edge(char node, vectorchar neibors){graph[node] neibors;}// 计算两个顶点的最短路径A-B-D-Fvectorchar getShortPath(char node1, char node2){mapchar, vectorchar ShortPath; //用于存储当前最短路径queuechar q; //用于广度优先搜索// 如果求自身到自身的最短路径返回node1-node2if(node1 node2){return {node1, node2};}//否则将node1入队并向map中加入键值对q.push(node1);ShortPath[node1] {node1};while(!q.empty()){char temp q.front();q.pop();vectorchar path ShortPath[temp];for(auto neibor: graph[temp]){if(ShortPath.find(neibor) ShortPath.end()){// 如果邻接节点不在map中相当于未访问过就向map中加入键值对ShortPath[neibor] path;ShortPath[neibor].push_back(neibor);q.push(neibor);if(neibor node2)return ShortPath[neibor];}}}return {};}
};
int main(){Graph graph;graph.add_edge(A, {B, D});graph.add_edge(B, {A, C, D});graph.add_edge(C, {B, D, E});graph.add_edge(D, {A, B, C, E});graph.add_edge(E, {C, D, F});graph.add_edge(F, {C,E});vectorchar short_path graph.getShortPath(A, F);for(auto s: short_path){cout s;}
}
