网站网页设计有哪些,高要区公路建设规划局网站,宁波外贸公司招聘信息,口碑营销案例及分析图论#xff08;Graph Theory#xff09;是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形#xff0c;这种图形通常用来描述某些实体之间的某种特定关系#xff0c;用点代表实体#xff0c;用连接两点的线表示两个实体间具有的…图论Graph Theory是数学的一个分支。它以图为研究对象。图论中的图是由若干给定的点及连接两点的线所构成的图形这种图形通常用来描述某些实体之间的某种特定关系用点代表实体用连接两点的线表示两个实体间具有的某种关系。 相比矩阵、张量、序列等结构图结构可以有效建模和解决社会关系、交通网络、文法结构和论文引用等需要考虑实体间关系的各种实际问题。因此为了能够有效利用图结构这种工具我们必须要对图的定义、类型和性质有一定的认识。 概念
图是由顶点vertex和边edge组成的数据结构
如下图 节点node用红色标出通过黑色的边edge连接。
图可用于表示 社交网络网页生物网络… 我们可以在图上执行怎样的分析 研究拓扑结构和连接性群体检测识别中心节点预测缺失的节点预测缺失的边… 为了方便大家的学习下面我先来介绍一下图的基本术语。
基本术语
图的分类
有向图Directed Graph 在有向图中每条边都有一个方向从一个顶点指向另一个顶点。如果顶点 A 到顶点 B 有一条有向边则我们称顶点 A 直接指向顶点 B。这意味着从顶点 A 出发可以到达顶点 B但反之则不一定成立。有向图常用于表示具有方向性关系的问题例如交通流向、网页链接、任务依赖关系等。 无向图Undirected Graph 在无向图中边没有方向即连接两个顶点的边可以被看作是双向的。如果顶点 A 与顶点 B 之间有一条边那么顶点 A 与顶点 B 之间是相互连通的可以双向移动。无向图常用于表示无方向性关系的问题例如社交网络中的好友关系、道路交通图等。 无向完全图无向图中任意两个顶点之间都存在边。
有向完全图有向图中任意两个顶点之间都存在方向互为相反的两条弧。
简单图图中不存在顶点到其自身的边且同一条边不重复出现。
稀疏图有很少条边。
稠密图有很多条边。
子图Subgraph假设GV,{E}和G‘V,{E}如果V包含于V且E包含于E则称G为G的子图。
边
边顶点之间的逻辑关系用边来表示边集可以是空的。
无向边(Edge)若顶点V1到V2之间的边没有方向则称这条边为无向边。
无向图(Undirected graphs)图中任意两个顶点之间的边都是无向边。A,DD,A 对于无向图G来说G1V1,{E1}其中顶点集合V1{A,B,C,D}边集和E1{A,BB,CC,DD,AA,C} 有向边若从顶点V1到V2的边有方向则称这条边为有向边也称弧(Arc)。用V1,V2表示V1为弧尾(Tail)V2为弧头(Head)。V1V2≠V2V1。
度
度是指与该顶点相邻的边的数量。 例如上图图中 A、B、C、E、F 这几个顶点度数为 2 D 顶点度数为 4
有向图中细分为入度和出度参见下图 分析上图可知个顶点的出度与入度如下 A (2 out / 0 in) 两个出度没有入度 B、C、E (1 out / 1 in) D (2 out / 2 in) F (0 out / 2 in) 权
边可以有权重代表从源顶点到目标顶点的距离、费用、时间或其他度量。 路径
路径被定义为从一个顶点到另一个顶点的一系列连续边例如上图中【北京】到【上海】有多条路径。 北京 - 上海 北京 - 武汉 - 上海 路径长度 不考虑权重长度就是边的数量 考虑权重一般就是权重累加 环
在有向图中从一个顶点开始可以通过若干条有向边返回到该顶点那么就形成了一个环。
如下图 图的连通性
如果两个顶点之间存在路径则这两个顶点是连通的所有顶点都连通则该图被称之为连通图若子图连通则称为连通分量。
graph LRA --- BA --- CC --- DD --- EB --- EF --- GG --- HH --- FI --- J
根据上面给出的点与点之间的连通性可得出下图 强连通分量有向图中的极大强连通子图。
生成树无向图中连通且n个顶点n-1条边叫生成树。
有向树有向图中一顶点入度为0其余顶点入度为1。
森林一个有向图由若干棵有向树构成生成森林。
图的表示方法
图可以用邻接矩阵和邻接表表示
比如说下面的图 用邻接矩阵可以表示为 A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 1
D 0 1 1 0 用邻接表可以表示为 A - B - C
B - A - D
C - A - D
D - B - C有向图的例子: graph LR A---B A---C B---D C---D 用邻接矩阵可以表示为 A B C D A 0 1 1 0 B 0 0 0 1 C 0 0 0 1 D 0 0 0 0 用邻接表可以表示为 A - B - C B - D C - D D - empty 图的存储结构
邻接矩阵
邻接矩阵用两个数组一个数组保存顶点集一个数组保存边集。
无向图
无向图的邻接矩阵如图 代码示例
我们先将表示顶点和边的类定义出来
假设顶点的类型为 Vertex
class Vertex {int value;// 其他顶点属性
}
假设边的类型为 Edge
class Edge {int startVertexId;int endVertexId;// 其他边属性
}
class Graph {Vertex[] vertices;Edge[] edges;int[][] adjacencyMatrix;public Graph(Vertex[] vertices, Edge[] edges) {this.vertices vertices;this.edges edges;this.adjacencyMatrix new int[vertices.length][vertices.length];// 初始化邻接矩阵将相应位置设为 1 表示边的连接关系for (Edge edge : edges) {adjacencyMatrix[edge.startVertexId][edge.endVertexId] 1;// 如果是无向图还需要设置对称位置adjacencyMatrix[edge.endVertexId][edge.startVertexId] 1;}}
}
有向图
有向图的邻接矩阵如图 代码示例
class Digraph {Vertex[] vertices;Edge[] edges;int[][] adjacencyMatrix;public Digraph(Vertex[] vertices, Edge[] edges) {this.vertices vertices;this.edges edges;this.adjacencyMatrix new int[vertices.length][vertices.length];// 初始化邻接矩阵将相应位置设为 1 表示边的连接关系for (Edge edge : edges) {adjacencyMatrix[edge.startVertexId][edge.endVertexId] 1;}}
}
邻接表
邻接表数组与链表相结合的存储方法。
邻接表表示法(链式)表示如下图 顶点 按编号顺序将顶点数据存储在一维数组中。关联同一顶点的边 用线性链表存储。如果有边\弧的信息还可以在表结点中增加一项 无向图
无向图的邻接表如下图 特点 邻接表不唯一若无向图中有n个顶点、e条边则其邻接表需要n个头结点和2e个表结点。适宜存储稀疏图。无向图中顶点vi的度为第i个单链表中的结点数 代码示例
import java.util.ArrayList;
import java.util.List;class Graph {int numVertices;ListListInteger adjacencyList;public Graph(int numVertices) {this.numVertices numVertices;this.adjacencyList new ArrayList(numVertices);// 初始化邻接表for (int i 0; i numVertices; i) {adjacencyList.add(new ArrayList());}}public void addEdge(int src, int dest) {// 添加双向边的连接关系adjacencyList.get(src).add(dest);adjacencyList.get(dest).add(src);}
}有向图 特点 顶点vi的出度为第i个单链表中的结点个数。顶点vi的入度为整个单链表中邻接点域值是i-1的结点个数。找出度易找入度难 逆邻接表 逆邻接表特点 顶点vi的入度为第i个单链表中的结点个数。顶点vi的出度为整个单链表中邻接点域值是i-1的结点个数。找入度易找出度难。 当邻接表的存储结构形成后图便唯一确定。
代码示例
import java.util.ArrayList;
import java.util.List;class Digraph {int numVertices;ListListInteger adjacencyList;public Digraph(int numVertices) {this.numVertices numVertices;this.adjacencyList new ArrayList(numVertices);// 初始化邻接表for (int i 0; i numVertices; i) {adjacencyList.add(new ArrayList());}}public void addEdge(int src, int dest) {// 添加单向边的连接关系adjacencyList.get(src).add(dest);}
} 图的遍历
广度优先遍历BFS
广度优先遍历(Breadth First Search)又称为广度优先搜索简称BFS。是一种分层的查找过程每向前走一步可能访问一批顶点不像深度优先搜索那样有往回退的情况因此它不是一个递归的算法。为了实现逐层的访问算法必须借助一个辅助队列以记忆正在访问的顶点的下一层顶点。 其实他本意就是先遍历一个节点然后遍历那个节点所连接的的周边节点之后再一个结点一个结点的往外遍历重复循环。
下面举个例子 这张图我们设从“3”开始遍历运用广度优先的方法那么我们所得到的遍历顺序为323451
深度优先遍历DFS
所谓DFS就是从起点开始找准一个方向直到走不了为止然后再原路返回再找到一个能走的地方继续走的思路。
下面举个例子 遍历顺序为12478536
这里这两种算法我只是概述一下后面我还会写两篇博文来专门讲这两种遍历方式
上面差不多就是刷图论的题所需要具备的图的基础知识了后续我会继续更新一些我在刷图论题的一些体会。
