2017-10-20

图论基础篇

一. 图的介绍

说起图这个词，很多人可能首先会想到的就是图片，地图……等，但这里所说的图是一个抽象的概念。

定义：图是由一组顶点和一组能将两个顶点相连的边组成的。

图论一直以来都是数学领域的一个重要分支，但在计算机科学领域的应用中，基于图论的由一系列结点和边的模型起到了非常重要的作用，图的算法能够解决实际生活中许多比较复杂的问题，例如我们的地图、电路、社会中人与人之间的关系网已级计算机网络等无法通过一般的数据结构来描述的。所以它也是许多高级算法的基石，直到现在图论算法的研究一直在进行，因为仍有许多领域无法解决的问题。这里就总结一些图的基础算法。

二. 图的表示

图的分类有很多，按方向可分为有向图和无向图，按密度可分为稀疏图和稠密图。
而对于稀疏图一般的表示方法就是邻接表，而对于稠密图一般的表示就是邻接矩阵。这里对于有向性我们可以用一个简单的布尔类型的变量来表示，然后用int型的变量v、e分别表示顶点和边。
首先是稀疏图的表示，看看如下代码

// 稀疏图 - 邻接表
public class SparseGraph {
    private int v;  // 节点数
    private int e;  // 边数
    private boolean directed;    // 是否为有向图
    private Vector<Integer>[] g; // 图的具体数据
    // 构造函数
    public SparseGraph( int n , boolean directed ){
        assert n >= 0;
        this.v = v;
        this.e = e;    // 初始化没有任何边
        this.directed = directed;
        // g初始化为n个空的vector, 表示每一个g[i]都为空, 即没有任和边
        g = (Vector<Integer>[])new Vector[n];
        for(int i = 0 ; i < n ; i ++)
            g[i] = new Vector<Integer>();
    }
    public int V(){ return v;} // 返回节点个数
    public int E(){ return e;} // 返回边的个数
    // 向图中添加一个边
    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);
        e ++;
    }
    // 验证图中是否有从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;
    }
}

这里用了一个hasEdge()来进行边的方法来进行边的验证,用addEdge()方法来添加边，注意方法中的判断，如果顶点没有产生自环（自环就是边以一个顶点出发最后又回到这个顶点），且图为无向图则将v也添加到w的链表中，然后看看稠密图的表示

// 稠密图 - 邻接矩阵
public class DenseGraph {
    private int v;  // 节点数
    private int e;  // 边数
    private boolean directed;   // 是否为有向图
    private boolean[][] g;      // 图的具体数据
    // 构造函数
    public DenseGraph( int n , boolean directed ){
        assert n >= 0;
        this.n = n;
        this.e = 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;
        e ++;
    }
    // 验证图中是否有从v到w的边
    boolean hasEdge( int v , int w ){
        assert v >= 0 && v < n ;
        assert w >= 0 && w < n ;
        return g[v][w];
    }
}

同样的道理，不过邻接矩阵比起邻接链表具有更高的空间复杂度

三.常见的图处理方式

先定义一个adj()方法

// 计算和顶点v相邻的所有边数
public Iterable<Integer> adj(int v) {
	return adj[v];
}

1.计算顶点的度数

这里度指的的依附某个顶点的边的数量

public static int degree(Graph G,int v) {
	int degree = 0;
	for (int w : G.adj(v))
		degree++;
	return degree;
}

2.计算所有顶点的最大度数

public static int maxDegree(Graph G) {
        int max = 0;
        for (int v = 0;v<G.V();v++) {
            if (degree(G,v) > max) {
                max = degree(G,v);
            }
        }
        return max;
    }

3.计算自环的个数

public static int numberOfSelfLoops(Graph G) {
        int count = 0;
        for (int v=0;v<G.V();v++) {
            for (int w : G.adj(v))
                if (v == w)
                    count++;
        }
        return count/2;  // 每条边都被标记过两次
    }