首页 > 代码库 > 算法7-2:图论接口

算法7-2:图论接口

本节介绍如何在程序中表示一张图。


顶点

在程序中,顶点用整数表示就可以了。因为整数可以作为数组的下标,也可以作为哈希表的键。所以用整数是最方便的。



当然,在一张图中可能会出现一些异常情况,比如自己连接自己,两个顶点之间存在多个边。这些异常情况也是要考虑的。



接口


为了表示一张图,就要创建专门的对象来保存图。这个对象起名叫做Graph好了。它的接口是下面这样的。

public class Graph {
    // 创建一个带有V个顶点的图
    Graph(int V);
 
    // 从输入流创建一张图,输入流的格式下文有介绍
    Graph(In in);
 
    // 在两个顶点之间创建一条边。
    void addEdge(int v, int w);
 
    // 获取一个顶点的邻居顶点
    Iterable<Integer> adj(int v);
 
    // 获取这张图中顶点的数量
    int V();
 
    // 获取这张图中边的数量
    int E();
 
    // 将这张图表示成一个字符串,用于显示
    String toString();
}


输入格式


接口中提到了可以从一个输入流创建一张图。那么这个输入流的格式应该怎样呢?首先第一行是一个整数,表示这个图顶点的数量,第二行是一个整数,表示边的数量,后面的每一行中都有两个整数,表示两个顶点之间有一条边。



设施


图论中有一些简单的操作,比如计算一个顶点的度(邻居节点数量),自连接的数量等。这些操作在后面的算法中都会用到。它们的代码如下:


public static int degree(Graph G, int v) {
    int count = 0;
    for (Integer e : G.adj(v)) count++;
    return count;
}
 
public static int maxDegree(Graph G) {
    int max = 0;
    for (int v = 0; v < G.V(); v++) {
        int d = degree(G, v);
        if (d > max) max = d;
    }
    return max;
}
 
public static int averageDegree(Graph G) {
    return G.E() * 2 / G.V();
}
 
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;
}


数据结构

图主要有两种表示方法,一种是邻接矩阵,一种是邻接表。同学们别被这样的怪名字吓到,其实它们的本质都是数组或者链表。


邻接矩阵


邻接矩阵就是一个很大的二维数组a,它的维度和顶点数量相同。如果顶点数量是V,那么这个二维矩阵就是V×V大小。其中a[v][w]就表示了顶点v和顶点w是否相连,0表示没有连接,1表示相连。



邻接表


邻接表其实就是一个数组,数组中的每个元素都用来记录某个顶点有哪些邻居。



邻接表表示法的代码如下:

public class Graph {
    private List<Integer>[] adj;
 
    public Graph(int V) {
        adj = new LinkedList[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkedList<Integer>();
        }
    }
 
    public void addEdge(int v, int w) {
        adj[v].add(w);
        adj[w].add(v);
    }
 
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
 
    public int V() {
        return adj.length;
    }
 
    public int E() {
        int result = 0;
        for (List<Integer> each : adj) {
            result += each.size();
        }
        return result;
    }
 
    @Override
    public String toString() {
        String result = "";
        for (int i = 0; i < adj.length; i++) {
            result += i + ":";
            for (int v : this.adj(i)) {
                result += " " + v;
            }
            result += "\n";
        }
        return result;
    }
}


实际应用中一般使用最多的就是邻接表,因为一般的应用顶点多而边数少。如果用邻接矩阵,内存浪费会很严重,因此实际应用中更加偏向于使用邻接表。