首页  

图论基础     所属分类 DS 浏览量 35
图论(Graph Theory)  离散数学的一个分支 研究图(Graph)
对象之间成对关系建模 
节点 或 顶点  Vertex
边 Edge
图的顶点集合不能为空,但边的集合可以为空

无向图 有向图
无权图 有权图   连接节点与节点的边是否有权值

图的连通性
无向图 G 中,若从顶点 i 到顶点 j 有路径相连,则称 i 和 j 是连通的
如果图中任意两点都是连通的,那么图被称作连通图
如果此图是有向图,则称为强连通图(注意 需要双向都有路径)

完全图
一个简单的无向图,其中每对不同的顶点之间都恰连有一条边相连

自环边 一条边的起点终点是一个点
平行边 两个顶点之间存在多条边相连接

图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具

图的表达形式
邻接矩阵  邻接表

邻接矩阵  1 表示相连接,0 表示不相连
邻接表   只表达和顶点相连接的顶点信息
4个节点 0 1 2 3 
0 1        (0 和 1 相连)
1 0 2 3    (1 和 0 2 3 相连)
2 1 3      (2 和 1 3 相连)
3 1 2      (3 和 1 2 相连)



邻接表适合表示稀疏图 (Sparse Graph)
邻接矩阵适合表示稠密图 (Dense Graph)

// 邻接矩阵
public class DenseGraph {
    // 节点数
    private int n;
    // 边数
    private int m;
    // 是否为有向图
    private boolean directed;
    // 图的具体数据
    private boolean[][] g;
    
    

// 邻接表
public class SparseGraph {
    // 节点数
    private int n;
    // 边数
    private int m;
    // 是否为有向图
    private boolean directed;
    // 图的具体数据
    private Vector< Integer>[] g;
    

完整代码 https://gitee.com/dyyx/hellocode/blob/master/web/tech/DS/cainiaods/src/main/java/runoob/graph/DenseGraph.java https://gitee.com/dyyx/hellocode/blob/master/web/tech/DS/cainiaods/src/main/java/runoob/graph/SparseGraph.java https://gitee.com/dyyx/hellocode/blob/master/web/tech/DS/cainiaods/src/main/java/runoob/graph/read/GraphReadTest.java

上一篇     下一篇
希尔排序

快速排序

Java assert

Linux dd 命令

微积分人类精神的最高胜利