建设网站需要几个人完成,pc网站,最新新闻事件摘抄,网页小游戏怎么玩一.图的基本知识1.图的定义在计算机科学中#xff0c;图(Graph)是一种非常重要的非线性数据结构#xff0c;用于表示对象(称为顶点或节点)以及它们之间的关系(称为边)1.基本定义图由两个集合组成#xff1a;顶点集(V, Vertices / Nodes)#xff1a;代表实体。例如城市、人、…一.图的基本知识1.图的定义在计算机科学中图(Graph)是一种非常重要的非线性数据结构用于表示对象(称为顶点或节点)以及它们之间的关系(称为边)1.基本定义图由两个集合组成顶点集(V, Vertices / Nodes)代表实体。例如城市、人、网页、计算机等边(E, Edges)代表顶点之间的连接或关系。例如道路、友谊关系、超链接、网络链接等2.图的分类根据边的性质图可以分为多种类型1.无向图(Undirected Graph)边没有方向。如果A和B之间有边意味着A可以到BB也可以到A像双向通道A 边 / \ 边 / \ B C \ / 边 \ / 边 D 注A、B、C、D为顶点2.有向图(Directed Graph /Digraph)边有方向通常用箭头表示。从A到B的边并不意味着可以从B到AA | \ | \ v v B C ^ | | | | v D --- | E 不能直接从B到A可以直接从A到B 不能直接从D到C可以直接从C到E 注C和E都指向D但是C不指向E3.加权图(Weighted Graph)每条边都有一个数值(权重)代表距离、时间、成本或强度等5 A ------- B | \ | 2| \ 3 | 4 | \ | | \ | C-------- D 1 解释 A到B的距离(权重)是5 B到A的距离(权重)也是5 A到D的距离(权重)是3 D到A的距离(权重)也是3 注加权只是给边增加了一个属性它并不改变边的方向。上图表示的是无向加权图4.无权图(Unweighted Graph)边没有权重通常只表示“有向”或“无向”如前两幅图都是无权图3.图的常见术语1.度(Degree)与一个顶点相连的边的数量在有向图中分为入度指向该点的边数出度从该点指出的边数A | \ | \ v v B C ^ | | | | v D --- | E D的度是3 D的出度是1D的入度是2 C的度是2 C的出度是1C的入度是12.路径(Path)从一个顶点到另一个顶点所经过的边简单路径路径中不重复经过任何顶点路径长度经过的边的数量(如果是加权图则是权重的总和)A | \ | \ v v B C ^ | | | | v D ------E 现在我们需要寻找从顶点A到顶点D的路径 路径一(经过C)A -- C -- D 可行√ 路径二(经过B)A -- B -- D 不可行× 因为没有箭头从B指向D 路径三(经过E)A -- C -- E -- D 不可行× C没有指向EE是一个源头只能从E出不能进入E 结论从A到D的路径只有一条长度为2顶点序列为A、C、D3.环(Cycle)一条起点和终点相同的路径(该路径起点和终点是同一个顶点并且中间至少经过了一条边)A-------- | \ | | \ | v v | B C | ^ | | | | | | v | D -------E这个图里面就没有环如果让B也指向A此时就有环了A-------- ^ | | \ | | \ | v v | B C | ^ | | | | | | v | D -------E 环路径A -- C -- D -- B -- A 你可以无限地在这个环里绕圈圈加权图的最短路径如果给边加上权重路径的选择就变了。我们要寻找总权重最小的路径10 A -------- C | \ | 1 | \ 100 | 1 | \ v v ---- D B ^ ^ | 5 |___________| (直接连) 从A到D 路径一A -- C -- D 经过2条边总代价为11 路径二A -- D 经过1条边总代价为100 路径三A -- B -- D 经过2条边总代价为6 所以在加权图中最短路径不一定指的就是“经过的顶点数最少”的那条而是“花费的总权重最小” 这就是导航软件为什么有时候会让你绕远路(因为那条路不堵车权重小)的原因4.连通性(Connectivity)如果图中任意两个顶点都存在路径则称该图为连通图(针对无向图) 或 强连通图(针对有向图)连通图示例A ------- B | | | | C ------- D | | E强连通图示例A ------- B ^ | | | | v D ------- C5.连通分量(Connected Component)连通分量是图中“互相连通的最大子图”核心定义对于无向图来说如果图是连通的(所有点都能互通)那么它只有一个连通分量(就是它自己)如果图是不连通的(分成了几块)那么每一块都是一个连通分量图示[组 1] [组 2] [组 3] (A) ----- (B) (D) ----- (E) (G) | | | | | | (C) (F) (H) 分析 组1 {A,B,C,F} A能走到B、C、FB能走到A、C、F ... 它们内部完全连通 组2 {E,E,H} 它们内部连通但跟组1没有关系 组3 {G} 只有一个顶点没有边。单个孤立的点也算连通分量 结论 这个图有3个连通分量{A,B,C,F}、{E,E,H}、{G}对于有向图来说弱连通分量忽略方向后形成的连通块强连通分量在有向图中极大的强连通子图。即在这个子图里任意两点都能互相到达(顺着箭头去也能顺着箭头回)图示(A) ----- (B) ^ | | v (D) ----- (C) (E) ----- (F) 分析左半部分{A,B,C,D} A -- B -- C -- D -- A 这四个点形成了一个完美的环。任意两点都能互达 所以{A,B,C,D}是一个强连通分量 分析右半部分{E,F} E -- F 但是F不能回到E 所以{E,F}不是一个强连通分量 我们需要把它们拆开{E}自己是一个强连通分量(单个点默认强连通){F}也是一个强连通分量 只是它们两个不能合在一起因为不满足“互相连通” 结论这个图中共有3个强连通分量{A,B,C,D}、{E}、{F}4.图的存储方式在计算机内存中图主要有两种存储结构1.邻接矩阵(Adjacency Matrix)使用一个二维数组matrix[i][j]表示顶点i和顶点j之间是否有边优点判断两点之间是否有边非常快 O(1)缺点占用空间大 O(V^2) 适合稠密图(边非常多)2.邻接表(Adjacency List)使用链表加数组每个顶点对应一个列表列表中存储与该顶点相连的所有顶点优点节省空间 O(V E) 适合稀疏图(边较少)缺点判断两点之间是否右边需要遍历列表5.经典算法与场景应用图论算法是解决许多实际问题的核心1.遍历算法深度优先搜索(DFS)常用于迷宫求解、拓补排序、检测环广度优先搜索(BFS)常用于寻找无权图中的最短路径、层级遍历2.最短路径算法Dijkstra算法寻找带权图中的单源最短路径(如导航软件规划路线)Floyd-Warshall算法寻找所有顶点对之间的最短路径3.最小生成树(MST)Prim算法和Kruskal算法用于在网络设计中以最低成本链接所有节点(如铺设电缆构建通信网)4.拓扑排序 (Topological Sort)用于解决依赖关系问题如编译顺序、课程安排先修课。5.实际应用社交网络分析人际关系、推荐好友。搜索引擎PageRank 算法利用网页链接图对网页进行排名。地图导航计算两地之间的最快或最短路线。知识图谱表示实体及其复杂的语义关系。电路设计逻辑门之间的连接。总结来说图是计算机科学中建模“关系”最强大的工具几乎所有涉及网络、连接和依赖的问题都可以转化为图问题来求解。二.Java代码1.用Java代码表示图------------ B ---------- | | | v A D | ^ | | ----------- C -----------package algorithm.datastructure.graph; public class Edge { Vertex linked; // 边所连接的顶点 int weight; // 边的权值 // 构造方法链也称为构造方法重载 // this(linked, 1)表示调用当前类的另一个构造方法传入linked和默认权值1 // 这样设计的好处是当用户只需要指定连接的顶点而使用默认权值时可以简化代码 public Edge(Vertex linked) {this(linked, 1);}; public Edge(Vertex linked, int weight) { this.linked linked; this.weight weight; } }package algorithm.datastructure.graph; import java.util.List; public class Vertex { String name; // 顶点名称 ListEdge edges; // 顶点所连接的边 public Vertex(String name) { this.name name; } public String getName() { return name; } public static void main(String[] args) { // IDEA中直接输入psv回车就可以快速生成main方法的框架 // 创建顶点对象 Vertex a new Vertex(A); // ctrl d 向下快速复制当前行 Vertex b new Vertex(B); Vertex c new Vertex(C); Vertex d new Vertex(D); a.edges List.of(new Edge(b), new Edge(c)); // List.of()是Java9引入的静态工厂方法用于快速、便捷地创建不可变列表(不能添加、删除、修改元素) b.edges List.of(new Edge(d)); c.edges List.of(new Edge(d)); d.edges List.of(); // List.of()中什么都不写表示创建一个空列表 } }2.深度优先搜索(Depth First Search)遍历的时候要尽可能走得更远