使用Java实现图的遍历算法的函数

图遍历算法是许多基础算法和图论算法的基础，包括深度优先搜索（DFS，Depth-First Search）、广度优先搜索（BFS，Breadth-First Search）等。这些算法对于处理各类图形应用问题非常有用，如迷宫问题、拓扑排序、最短路径问题等等。在Java中实现图遍历算法的函数，可以使用邻接矩阵或邻接表进行表示。本文将重点介绍邻接表的实现方式。

邻接表是一种基于链式存储结构的图表示方式。它比邻接矩阵更为灵活，可以有效降低图的空间复杂度。实现邻接表的关键是设计节点类型，该类型需要保存与该节点相邻的所有其他节点的信息，以及权重等信息或其他数据。通常，我们可以使用链表或数组来实现邻接表结构。前者较为灵活但需要较多的空间，后者空间利用率高但不太灵活。在本文中，我们将采用链表方式来实现邻接表结构。

首先，我们需要定义边和节点类型：

class Edge {
    int to;    // 边指向的节点
    int weight;    // 边权重
    Edge next;    // 指向下一条边的指针
    public Edge(int to, int weight, Edge next) {
        this.to = to;
        this.weight = weight;
        this.next = next;
    }
}
class Node {
    int val;    // 节点值
    Edge edge;    // 指向这个节点相邻的      条边的指针
    public Node(int val, Edge edge) {
        this.val = val;
        this.edge = edge;
    }
}

这里的 Edge 类型包含了指向所连的节点的指针 to，边的权重 weight，以及指向下一条边的指针 next。 Node 类型包含了节点值 val，以及指向 条边的指针 edge。这个指针可以形成一个链表，通过多级指针的方式串联所有相邻的节点。这里的链表可以用一个单向链表实现，也可以用 Java 中的数组实现并行的链表。

接下来，我们可以实现基于邻接表的图表示和遍历算法:

class Graph {
    Node[] adjList;    // 存储该图的邻接表
    int size;    // 图中节点的数量
    boolean[] visited;    // 标记节点是否被访问过
    public Graph(int size) {
        this.size = size;
        adjList = new Node[size];
        for(int i = 0; i < size; i++) {
            adjList[i] = new Node(i, null);
        }
        visited = new boolean[size];
    }
    public void addEdge(int from, int to, int weight) {
        Edge edge = new Edge(to, weight, adjList[from].edge);
        adjList[from].edge = edge;
    }
    // 深度优先搜索
    void dfs(int node) {
        if(visited[node]) return;
        visited[node] = true;
        System.out.print(node + " ");
        Edge edge = adjList[node].edge;
        while(edge != null) {
            dfs(edge.to);
            edge = edge.next;
        }
    }
    // 广度优先搜索
    void bfs(int node) {
        Queue<Integer> q = new LinkedList<>();
        visited[node] = true;
        q.offer(node);
        while(!q.isEmpty()) {
            int cur = q.poll();
            System.out.print(cur + " ");
            Edge edge = adjList[cur].edge;
            while(edge != null) {
                if(!visited[edge.to]) {
                    visited[edge.to] = true;
                    q.offer(edge.to);
                }
                edge = edge.next;
            }
        }
    }
}

这里的 Graph 类包含了三个重要的成员变量：邻接表 adjList，节点数量 size 和访问状态数组 visited。在构造函数中，我们初始化每一个节点，并将节点之间的邻接关系存储在邻接表中。addEdge 函数用于向邻接表中插入新的一条边。而节点的遍历算法则是分别使用 dfs 和 bfs 函数来实现。需要注意的是，在 dfs 函数中，首先对当前节点进行标记，然后依次递归到其相邻的节点，访问完后回溯到上一个节点；而在 bfs 函数中，则是通过队列的方式先访问当前节点的相邻节点，依次从队列中取出相邻节点并做处理，直到队列为空为止。

使用这个 Graph 类型，我们就可以轻松构建并操作各种图结构，如下所示：

public static void main(String[] args) {
    Graph g = new Graph(6);
    g.addEdge(0, 1, 2);
    g.addEdge(0, 2, 3);
    g.addEdge(1, 3, 4);
    g.addEdge(2, 3, 5);
    g.addEdge(2, 4, 6);
    g.addEdge(3, 4, 4);
    g.addEdge(3, 5, 7);
    g.addEdge(4, 5, 3);
    System.out.print("DFS: ");
    g.dfs(0);
    System.out.println();
    g.visited = new boolean[6];
    System.out.print("BFS: ");
    g.bfs(0);
}

这里在 main 函数中构建了一个简单的图结构，然后依次对其做了深度优先搜索和广度优先搜索，并输出了相应的遍历结果。

总结而言，使用邻接表来实现图遍历算法的 Java 功能函数，很大程度上是通过链表或数组的方式记录节点之间的邻接关系，从而通过递归或队列等方式进行遍历处理。对于邻接表的实现，可以参考本文提供的代码方式，也可以根据实际需求做出适当调整。