图论基础和表示

一、概念及其介绍

图论(Graph Theory)是离散数学的一个分支，是一门研究图(Graph)的学问。

图是用来对对象之间的成对关系建模的数学结构，由"节点"或"顶点"(Vertex）以及连接这些顶点的"边"（Edge）组成。

值得注意的是，图的顶点集合不能为空，但边的集合可以为空。图可能是无向的，这意味着图中的边在连接顶点时无需区分方向。否则，称图是有向的。下面左图是一个典型的无向图结构，右图则属于有向图。本章节介绍的图都是无向图。

图的分类：无权图和有权图，连接节点与节点的边是否有数值与之对应，有的话就是有权图，否则就是无权图。

图的连通性： 在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点 i 到顶点 j 有路径相连（当然从j到i也一定有路径），则称 i 和 j 是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径）。图的连通性是图的基本性质。

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

自环边： 一条边的起点终点是一个点。

平行边： 两个顶点之间存在多条边相连接。

二、适用说明

图可用于在物理、生物、社会和信息系统中建模许多类型的关系和过程，许多实际问题可以用图来表示。因此，图论成为运筹学、控制论、信息论、网络理论、博弈论、物理学、化学、生物学、社会科学、语言学、计算机科学等众多学科强有力的数学工具。在强调其应用于现实世界的系统时，网络有时被定义为一个图，其中属性(例如名称)之间的关系以节点和或边的形式关联起来。

三、图的表达形式

邻接矩阵： 1 表示相连接，0 表示不相连。

邻接表： 只表达和顶点相连接的顶点信息

邻接表适合表示稀疏图 (Sparse Graph)

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

Java 实例代码

源码包下载： Download

(1) 邻接矩阵

src/yssmx/graph/DenseGraph.java 文件代码：

package yssmx.graph ;

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

    // 构造函数
    public DenseGraph ( int n , boolean directed ) {
        assert n >= ;
        this . n = n ;
        this . m = ;
        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 >= && v < n ;
        assert w >= && 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 >= && v < n ;
        assert w >= && w < n ;
        return g [ v ] [ w ] ;
    }
}

（2）邻接表

src/yssmx/graph/SparseGraph.java 文件代码：

package yssmx.graph ;

import java.util.Vector ;

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

    // 构造函数
    public SparseGraph ( int n , boolean directed ) {
        assert n >= ;
        this . n = n ;
        this . m = ;  
        this . directed = directed ;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = ( Vector < Integer > [ ] ) new Vector [ n ] ;
        for ( int i = ; i < n ; i ++ )
            g [ i ] = new Vector < Integer > ( ) ;
    }
    // 返回节点个数
    public int V ( ) { return n ; }
    // 返回边的个数
    public int E ( ) { return m ; }
    // 向图中添加一个边
    public void addEdge ( int v, int w ) {
        assert v >= && v < n ;
        assert w >= && 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 >= && v < n ;
        assert w >= && w < n ;

        for ( int i = ; i < g [ v ] . size ( ) ; i ++ )
            if ( g [ v ] . elementAt ( i ) == w )
                return true ;
        return false ;
    }
}