无向图

我们用邻接图来表示图

具体实现的代码

public class Graph {
    private final int V;
    private int E;
    private Bag<Integer>[] adj;
    public Graph(int V){
        this.V = V;
        E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new Bag<Integer>();
        }
    }
    public int V(){
        return V;
    }
    public int E(){
        return E;
    }
    public void addEdge(int v , int w){
        //将v w 连接起来
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }
    public Iterable<Integer> adj(int v){
        return adj[v];
    }
    //计算v 的度数
    public static int degree(Graph G , int v){
        int degree = 0;
        for (Integer integer : G.adj(v)) {
            degree++;
        }
        return degree;
    }
    public static int maxDegree(Graph G){
        int max = 0;
        for (int i = 0; i < G.V(); i++) {
            if (degree(G,i) > max)max = degree(G,i);
        }
        return max;
    }
    //计算所有顶点的平均度数
    public static double avgDegree(Graph G){
        return 2.0*G.E()/ G.V();
    }
    //计算所有自环的个数
    public static int numberOfSelfLoops(Graph G){
        int count = 0;
        for (int v = 0; v < G.V(); v++) {
            for (Integer item : G.adj[v]) {
                if (item == v)count++;
            }
        }
        return count/2;
    }
    public String toString(){
        String s = V + "vertices," + E + "edges\n";
        for (int v = 0; v < V; v++) {
            s += v + ":";
            for (Integer w : adj(v)) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }

}

这里注意泛型数组的创建  adj = (Bag<Integer>[]) new Bag[V];

DFS

public class DepthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s; // 起点
    public DepthFirstPaths(Graph G ,int s){
        this.s = s;
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        dfs(G,s);
    }
    private void dfs(Graph G , int v){
        marked[v] = true;
        for (Integer w : G.adj(v)) {
            if (!marked[w]){
                edgeTo[w] = v;
                dfs(G,w);
            }
        }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v){
        if (marked[v] == false)return null;
        Stack<Integer> path = new Stack<>();
        for(int x = v;x !=s; x = edgeTo[x]){
            path.push(x);
        }
        path.push(s);
        return path;
    }

dfs的主要思想：用递归的方法，先把一条路走到底。其实dfs运用了java系统自带的栈。

BFS

public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;
    private int[] dis;
    public BreadthFirstPaths(Graph G , int s){
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dis = new int[G.V()];
        bfs(G , s);
    }
    private void bfs(Graph G , int s){
        Queue<Integer> queue = new Queue<Integer>();
        marked[s] = true;
        queue.enqueue(s);
        while(!queue.isEmpty()){
            int v = queue.dequeue();
            for (Integer w : G.adj(v)) {
                if (!marked[w]){
                    edgeTo[w] = v;
                    marked[w] = true;
                    dis[w] = dis[v] + 1;
                    queue.enqueue(w);
                }
            }
        }
    }
    public int distance(int w){
        return dis[w];
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v){
        if (!marked[v] )return null;
        Stack<Integer> path = new Stack<>();
        for (int w = v;w !=s;w = edgeTo[w]){
            path.push(w);
        }
        path.push(s);
        return path;
    }

bfs 是一层一层搜索，一层搜索完再进入到下一层，运用了queue先进先出的特质。

同时bfs还能用于搜索最短路径。

CC(Connected Components)

 

这里的连通分量和之前union find 并查集中的一样。

但是这里我们用dfs来查找有多少个cc

 

public class CC {
    private boolean[] marked;
    private int count;
    private int[] id;
    public CC(Graph G){
        marked = new boolean[G.V()];
        count = 0;
        int[] id = new int[G.V()];
        for (int i = 0; i < G.V(); i++) {
            if (!marked[i]){
                dfs(G,i);
                count++;
            }
        }
    }
    private void dfs(Graph G , int v){
        marked[v] = true;
        id[v] = count;
        for (Integer w : G.adj(v)) {
            if (!marked[w]){
                dfs(G,w);
            }
        }
    }
}

 

一次dfs 可以把 与 v在一条路径上的点全部打通。