Java数据结构中图的进阶详解

理解概念

图（Graph）是计算机科学中的一个重要概念。它是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：$G(V, E)$，其中$G$表示一个图，$V$表示图中顶点的集合，$E$表示图中边的集合。

图中的边分为有向边和无向边两种类型，有向边表示连接的两个顶点有一个方向，而无向边则没有。图中边的实际应用会有很多种，如网格图、支配图、哈密顿图、四色问题等等。

图的存储方式

在Java中，有以下三种常见的图的存储方式：

1. 邻接矩阵：用二维数组存储图中的边，二维数组中a[i][j]表示顶点i和顶点j之间是否有边。
2. 邻接表：用链表存储图中各个顶点的关系，每个顶点对应一个链表，这个链表存储与该顶点相邻的顶点。
3. 十字链表：是邻接表的加强版，用于存储有向图，既存储顶点的出边，也存储顶点的入边。

图的常见算法

深度优先搜索（DFS）

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。DFS将从起点开始顺着一条不重复的路径到达下一个点，如果到了一个节点无路可走，则返回过去继续搜索。

以下是一个深度优先搜索的示例代码：

public static void dfs(int start) {
    visited[start] = true;
    System.out.print(start + " ");

    for (int i = 0; i < V; i++) {
        if (adj[start][i] == 1 && !visited[i]) {
            dfs(i);
        }
    }
}

广度优先搜索（BFS）

广度优先搜索（Breadth First Search，BFS）同样也是一种用于遍历或搜索树或图的算法，与DFS算法的不同点在于BFS算法是逐层进行搜索的。BFS从起点开始，先遍历与起点相邻的所有点，然后遍历与这些点相邻的所有点。

以下是一个广度优先搜索的示例代码：

public static void bfs(int start) {
    Queue<Integer> queue = new LinkedList<>();
    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int s = queue.poll();
        System.out.print(s + " ");
        for (int i = 0; i < V; i++) {
            if (adj[s][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue.offer(i);
            }
        }
    }
}

示例说明

以下是一个有向图样例，我们可以使用邻接表进行存储。起点为0，使用BFS和DFS分别进行遍历：

public class Graph {
    int V;
    LinkedList<Integer>[] adj;

    public Graph(int v) {
        this.V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
    }

    public void BFS(int s) {
        boolean[] visited = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<Integer>();
        visited[s] = true;
        queue.add(s);

        while (queue.size() != 0) {
            s = queue.poll();
            System.out.print(s + " ");

            Iterator<Integer> iterator = adj[s].listIterator();
            while (iterator.hasNext()) {
                int n = iterator.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    public void DFS(int v, boolean[] visited) {
        visited[v] = true;
        System.out.print(v + " ");

        Iterator<Integer> iterator = adj[v].listIterator();
        while (iterator.hasNext()) {
            int n = iterator.next();
            if (!visited[n]) {
                DFS(n, visited);
            }
        }
    }
}

public static void main(String[] args) {
    Graph graph = new Graph(4);
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 2);
    graph.addEdge(2, 0);
    graph.addEdge(2, 3);
    graph.addEdge(3, 3);

    boolean[] visited = new boolean[4];
    System.out.print("BFS: ");
    graph.BFS(0);
    System.out.print("\nDFS: ");
    graph.DFS(0, visited);
}

输出结果为：

BFS: 0 1 2 3 
DFS: 0 1 2 3 

以上就是Java数据结构中图的进阶详解的总体介绍和示例说明。