图

[yifanzheng]

图

图中的元素叫作顶点，顶点之间的连接关系叫作边。图的存储方式有两种：邻接距阵和邻接表。

邻接矩阵存储

邻接表存储
]

实践

• 邻接表实现图
• 邻接矩阵实现图

[yifanzheng]

邻接表实现图

/**
 * Graph-邻接表
 *
 * @author star
 */
public class Graph {

    /**
     * 顶点个数
     */
    private int n;

    /**
     * 邻接表
     */
    private LinkedList<Integer>[] adj;

    /**
     * 是否是有向图
     */
    private boolean directed;

    public Graph(int n, boolean directed) {
        this.n = n;
        this.directed = directed;
        // 初始化一个空图
        this.adj = new LinkedList[n];
        for (int i = 0; i < n; i++) {
            this.adj[i] = new LinkedList<>();
        }
    }

    /**
     * 向图中添加一条边
     */
    public void addEdge(int v, int w) {
        if (v < 0 || v >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        if (w < 0 || w >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        adj[v].add(w);
        if (v != w && !directed) {
            adj[w].add(v);
        }
    }

    /**
     * 判断图中是否有从 v 到 w 的边
     */
    public boolean hasEdge(int v, int w) {
        if (v < 0 || v >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        if (w < 0 || w >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        for (int i = 0; i < adj[v].size(); i++) {
            if (adj[v].get(i) == w) {
                return true;
            }
        }
        return false;
    }

    /**
     * 获取一个顶点的所有邻边
     */
    public List<Integer> edges(int v) {
        if (v < 0 || v >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        LinkedList<Integer> edges = adj[v];
        return Collections.unmodifiableList(edges);
    }

    /**
     * 显示图的信息
     */
    public void show() {
        for (int i = 0; i < n; i++) {
            System.out.print("vertex " + i + ":\t");
            for (int j = 0; j < adj[i].size(); j++) {
                System.out.print(adj[i].get(j) + "\t");
            }
            System.out.println();
        }
    }
}

[yifanzheng]

邻接矩阵实现图

/**
 * Graph - 邻接矩阵
 *
 * @author star
 */
public class Graph2 {

    private int n;

    private boolean[][] graph;

    private boolean directed;

    public Graph2(int capacity, boolean directed) {
        this.n = capacity;
        this.directed = directed;
        this.graph = new boolean[n][n];
    }

    public void addEdge(int v, int w) {
        if (v < 0 || v >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        if (w < 0 || w >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        if (hasEdge(v, w)) {
            return;
        }
        graph[v][w] = true;
        if (!this.directed) {
            graph[w][v] = true;
        }
    }

    /**
     * 判断图中是否有从 v 到 w 的边
     */
    public boolean hasEdge(int v, int w) {
        if (v < 0 || v >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        if (w < 0 || w >= n) {
            throw new IllegalArgumentException("Index out of range");
        }

        return graph[v][w];
    }

    /**
     * 返回图中一个顶点的所有邻边
     */
    public List<Integer> edges(int v) {
        if (v < 0 || v >= n) {
            throw new IllegalArgumentException("Index out of range");
        }
        List<Integer> edges = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (graph[v][i]) {
                edges.add(i);
            }
        }
        return Collections.unmodifiableList(edges);
    }

    public void show() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.print(graph[i][j] + "\t");
            }
            System.out.println();
        }
    }

    /**
     * dfs 搜索 s 到 t 的路径
     */
    public List<Integer> dfs(int s, int t) {
        if (s == t) {
            return Collections.emptyList();
        }
        boolean[] visited = new boolean[n];
        int[] from = new int[n];
        for (int i = 0; i < n; i++) {
            from[i] = -1;
        }
        Deque<Integer> stack = new LinkedList<>();
        stack.push(s);
        visited[s] = true;
        while (!stack.isEmpty()) {
            Integer v = stack.pop();
            // 获取 v 相连的顶点
            List<Integer> edges = edges(v);
            for (int q : edges) {
                if (!visited[q]) {
                    from[q] = v;
                    if (q == t) {
                        break;
                    }
                    visited[q] = true;
                    stack.push(q);
                }
            }
        }
        int temp = t;
        LinkedList<Integer> path = new LinkedList<>();
        while (temp != -1 && s != temp) {
            path.addFirst(temp);
            temp = from[temp];
        }
        return Collections.unmodifiableList(path);
    }

    /**
     * 使用 bfs 搜索 s 到 t 的路径
     */
    public List<Integer> bfs(int s, int t) {
        if (s == t) {
            return Collections.emptyList();
        }
        boolean[] visited = new boolean[n];
        int[] from = new int[n];
        for (int i = 0; i < n; i++) {
            from[i] = -1;
        }
        Deque<Integer> queue = new LinkedList<>();
        queue.offer(s);
        visited[s] = true;
        while (!queue.isEmpty()) {
            Integer v = queue.poll();
            List<Integer> edges = edges(v);
            for (int e : edges) {
               if (!visited[e]) {
                   from[e] = v;
                   if (e == t) {
                       break;
                   }
                   queue.offer(e);
                   visited[e] = true;
               }
            }
        }
        int temp = t;
        LinkedList<Integer> path = new LinkedList<>();
        while (temp != -1 && s != temp) {
            path.addFirst(temp);
            temp = from[temp];
        }

        return path;
    }
}