带你了解Java数据结构和算法之无权无向图

什么是无权无向图？

无权无向图是图论中的重要概念，它是由若干个点以及连接这些点的边组成的。其中，无权表示边之间没有权重的区别，无向表示边没有方向。

无权无向图的表示方式

在Java中，可以使用邻接表来表示无权无向图。邻接表是由若干个链表组成的数据结构，其中每个节点表示图中的一个顶点，节点的值表示该顶点的编号，节点的下一个指针指向与该顶点相邻的其他顶点的链表。

示例代码：

public class Graph {
    private int V; // 顶点数
    private LinkedList<Integer>[] adj; // 邻接表数组

    public Graph(int v) {
        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);
        adj[w].add(v);
    }
}

在这个示例中，Graph类的构造函数初始化了一个邻接表数组，数组中的每一个元素都是一个链表；addEdge方法用于将两个顶点相邻的链表连在一起。

无权无向图的遍历

遍历无权无向图有两种通用的方法：深度优先遍历（DFS）和广度优先遍历（BFS）。

深度优先遍历

深度优先遍历是一种从图的起始点开始遍历的方法，遍历过程中不断沿着一条路径向下遍历，直到遇到死路时返回上一步，继续遍历其他路径。该方法通常使用递归实现。

示例代码：

public class GraphDFS {
    private boolean[] visited;

    public GraphDFS(Graph graph, int s) {
        visited = new boolean[graph.V()];
        dfs(graph, s);
    }

    private void dfs(Graph graph, int v) {
        visited[v] = true;
        System.out.print(v + " ");
        for (int w : graph.adj(v)) {
            if (!visited[w]) {
                dfs(graph, w);
            }
        }
    }
}

在这个示例中，GraphDFS类的构造函数使用DFS方法遍历图graph，并打印出遍历结果。

广度优先遍历

广度优先遍历是一种从图的起始点开始遍历的方法，遍历过程中逐层遍历，先遍历与起始点相连的所有点，再遍历与这些点相连的所有点，以此类推。该方法通常使用队列实现。

示例代码：

public class GraphBFS {
    private boolean[] visited;
    private Queue<Integer> queue;

    public GraphBFS(Graph graph, int s) {
        visited = new boolean[graph.V()];
        queue = new LinkedList<Integer>();

        visited[s] = true;
        queue.add(s);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            System.out.print(v + " ");

            for (int w : graph.adj(v)) {
                if (!visited[w]) {
                    visited[w] = true;
                    queue.add(w);
                }
            }
        }
    }
}

在这个示例中，GraphBFS类的构造函数使用BFS方法遍历图graph，并打印出遍历结果。

总结

无权无向图是数据结构中的重要概念，常见于网络通信、社交网络等场景。在Java中，可以使用邻接表来表示无权无向图，并使用深度优先遍历和广度优先遍历等方法进行遍历。本文简要介绍了无权无向图的基本概念、表示方式和遍历方法，并提供了相关的Java示例代码，希望对读者有所启发。

阅读剩余 57%