猿圈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 :
![](/images/780-200-2.jpg)