猿圈java 机试题

猿圈java 机试题简介

在计算机科学中，图是一个非常重要的数据结构，用来表示对象之间的关系。图由节点（或顶点）和连接到这些节点的边缘组成。根据边缘的方向，图可分为向图和无向图。根据边缘是否有权重，图可分为权重图和无权图。其中，旅行图是一种用于表示旅行路径的无向无权图。

以下是一个简单的旅行图示例，包括几个城市及其之间的旅行路径：

journey    A --> B --> C --> D    B --> E    C --> D    D --> E --> F    E --> G    F --> G --> H

在这张旅行图中，城市用字母表示，城市之间的路径用箭头表示。例如，从城市A到城市B有一条路径，可以通过节点A到节点B。

在Java中，我们可以使用相邻矩阵或相邻表来表示图。相邻矩阵是一个二维数组，其中元素表示图中节点之间的连接关系。相邻表是由链表组成的数组，每个链表都存储了节点的相邻节点。

以下是用邻接矩阵表示旅行图的代码示例:

public class TravelGraph {    private int[][] adjacencyMatrix;    private int numVertices;    public TravelGraph(int numVertices) {        this.numVertices = numVertices;        adjacencyMatrix = new int[numVertices][numVertices];    }    public void addEdge(int source, int destination) {        adjacencyMatrix[source][destination] = 1;        adjacencyMatrix[destination][source] = 1;    }    public void printGraph() {        for (int i = 0; i < numVertices; i++) {            for (int j = 0; j < numVertices; j++) {                System.out.print(adjacencyMatrix[i][j] + " ");            }            System.out.println();        }    }    public static void main(String[] args) {        TravelGraph graph = new TravelGraph(8);        graph.addEdge(0, 1);        graph.addEdge(1, 2);        graph.addEdge(2, 3);        graph.addEdge(1, 4);        graph.addEdge(3, 4);        graph.addEdge(4, 5);        graph.addEdge(5, 6);        graph.addEdge(6, 7);        graph.printGraph();    }}

我们创建了一个名为上述代码的代码。"TravelGraph"类别，它有一个相邻的矩阵和一些操作图。在主函数中，我们创建了一个8个节点的旅行图，并添加了一些路径。然后，我们调用了它"printGraph"打印相邻矩阵的方法。

遍历图是指访问图中的每个节点并执行某些操作。常用的图形遍历算法优先考虑深度搜索（DFS）和广度优先搜索（BFS）。以下是用邻接表示图实现DFS和BFS遍历的代码示例：

import java.util.LinkedList;import java.util.Queue;public class TravelGraph {    private LinkedList<Integer>[] adjacencyList;    private int numVertices;    public TravelGraph(int numVertices) {        this.numVertices = numVertices;        adjacencyList = new LinkedList[numVertices];        for (int i = 0; i < numVertices; i++) {            adjacencyList[i] = new LinkedList<>();        }    }    public void addEdge(int source, int destination) {        adjacencyList[source].add(destination);        adjacencyList[destination].add(source);    }    public void dfs(int startVertex) {        boolean[] visited = new boolean[numVertices];        dfsUtil(startVertex, visited);    }    private void dfsUtil(int vertex, boolean[] visited) {        visited[vertex] = true;        System.out.print(vertex + " ");        for (int neighbor : adjacencyList[vertex]) {            if (!visited[neighbor]) {                dfsUtil(neighbor, visited);            }        }    }    public void bfs(int startVertex) {        boolean[] visited = new boolean[numVertices];        Queue<Integer> queue = new LinkedList<>();        visited[startVertex] = true;        queue.offer(startVertex);        while (!queue.isEmpty()) {            int vertex = queue.poll();            System.out.print(vertex + " ");            for (int neighbor :