学校网站查询个人信息,wordpress 主题盗,西安网站建设行业动态,英文公司网站一、概念及其介绍
图论(Graph Theory)是离散数学的一个分支#xff0c;是一门研究图(Graph)的学问。
图是用来对对象之间的成对关系建模的数学结构#xff0c;由节点或顶点(Vertex#xff09;以及连接这些顶点的边#xff08;Edge是一门研究图(Graph)的学问。
图是用来对对象之间的成对关系建模的数学结构由节点或顶点(Vertex以及连接这些顶点的边Edge组成。
值得注意的是图的顶点集合不能为空但边的集合可以为空。图可能是无向的这意味着图中的边在连接顶点时无需区分方向。否则称图是有向的。下面左图是一个典型的无向图结构右图则属于有向图。本章节介绍的图都是无向图。 图的分类无权图和有权图连接节点与节点的边是否有数值与之对应有的话就是有权图否则就是无权图。
图的连通性在图论中连通图基于连通的概念。在一个无向图 G 中若从顶点 i 到顶点 j 有路径相连当然从j到i也一定有路径则称 i 和 j 是连通的。如果 G 是有向图那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的那么图被称作连通图。如果此图是有向图则称为强连通图注意需要双向都有路径。图的连通性是图的基本性质。
完全图完全是一个简单的无向图其中每对不同的顶点之间都恰连有一条边相连。
自环边一条边的起点终点是一个点。
平行边两个顶点之间存在多条边相连接。
二、适用说明
图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程许多实际问题可以用图来表示。因此图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时网络有时被定义为一个图其中属性(例如名称)之间的关系以节点和或边的形式关联起来。
三、图的表达形式
邻接矩阵1 表示相连接0 表示不相连。 邻接表只表达和顶点相连接的顶点信息 邻接表适合表示稀疏图 (Sparse Graph)
邻接矩阵适合表示稠密图 (Dense Graph)
Java 实例代码
(1) 邻接矩阵
src/runoob/graph/DenseGraph.java 文件代码
package runoob.graph;/*** 邻接矩阵*/
public class DenseGraph {// 节点数private int n;// 边数private int m;// 是否为有向图private boolean directed;// 图的具体数据private boolean[][] g;// 构造函数public DenseGraph( int n , boolean directed ){assert n 0;this.n n;this.m 0;this.directed directed;// g初始化为n*n的布尔矩阵, 每一个g[i][j]均为false, 表示没有任和边// false为boolean型变量的默认值g new boolean[n][n];}// 返回节点个数public int V(){ return n;}// 返回边的个数public int E(){ return m;}// 向图中添加一个边public void addEdge( int v , int w ){assert v 0 v n ;assert w 0 w n ;if( hasEdge( v , w ) )return;g[v][w] true;if( !directed )g[w][v] true;m ;}// 验证图中是否有从v到w的边boolean hasEdge( int v , int w ){assert v 0 v n ;assert w 0 w n ;return g[v][w];}
}
2邻接表
src/runoob/graph/SparseGraph.java 文件代码
package runoob.graph;import java.util.Vector;/*** 邻接表*/
public class SparseGraph {// 节点数private int n;// 边数private int m;// 是否为有向图private boolean directed;// 图的具体数据private VectorInteger[] g;// 构造函数public SparseGraph( int n , boolean directed ){assert n 0;this.n n;this.m 0; this.directed directed;// g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边g (VectorInteger[])new Vector[n];for(int i 0 ; i n ; i )g[i] new VectorInteger();}// 返回节点个数public int V(){ return n;}// 返回边的个数public int E(){ return m;}// 向图中添加一个边public void addEdge( int v, int w ){assert v 0 v n ;assert w 0 w n ;g[v].add(w);if( v ! w !directed )g[w].add(v);m ;}// 验证图中是否有从v到w的边boolean hasEdge( int v , int w ){assert v 0 v n ;assert w 0 w n ;for( int i 0 ; i g[v].size() ; i )if( g[v].elementAt(i) w )return true;return false;}
}
