戴尔官方网站建设启示,h5免费制作网站模板,wordpress插件 订阅,广西智能网站建设制作概念#xff1a;
数据结构图#xff08;Graph#xff09;是一种非线性的数据结构#xff0c;用于表示节点之间的关系。它由节点#xff08;Vertex#xff09;和边#xff08;Edge#xff09;组成#xff0c;每个节点可以与其他节点通过边连接起来。图分为有向图和无向…概念
数据结构图Graph是一种非线性的数据结构用于表示节点之间的关系。它由节点Vertex和边Edge组成每个节点可以与其他节点通过边连接起来。图分为有向图和无向图顾名思义在有向图中边是有方向的而在无向图中边是没有方向的。图也可以分为有权图和无权图有权图是指边具有一个相关联的权重值无权图是指边没有权重值。
特点
非线性结构图中的节点和边形成复杂的连接关系不同于数组、链表等线性结构。可变大小图可以动态增长或缩小并且支持添加、删除、修改节点和边。实体关系表示适合用于表示实体对象之间的相互关系如社交网络中用户之间的好友关系。
优点
模型灵活性高可以模拟各种现实情况下复杂而多样化的问题并提供了多种算法来解决这些问题。具备强大搜索能力通过遍历算法如深度优先搜索 (DFS) 和广度优先搜索 (BFS)能够有效地查找特定元素或路径。
缺点
占用更多内存空间相比线性结构图可能需要更多的空间来存储节点和边之间的关系。高复杂度某些图算法的时间复杂度相对较高尤其在大规模数据上进行操作时。
适用场景
社交网络分析。地图导航系统。网络拓扑结构表达和分析。
实现代码
无向有权图的简单实现
import java.util.*;class WeightedGraph {private MapString, ListEdge adjacencyList;public WeightedGraph() {this.adjacencyList new HashMap();}//添加节点public void addVertex(String vertex) {adjacencyList.put(vertex, new ArrayList());}//添加边public void addEdge(String source, String destination, int weight) {Edge edge new Edge(source, destination, weight);adjacencyList.get(source).add(edge);// For undirected graphEdge reverseEdge new Edge(destination, source, weight);adjacencyList.get(destination).add(reverseEdge);}//删除节点public void removeVertex(String vertex) {if (!adjacencyList.containsKey(vertex)) return;// Remove all edges connected to the vertexfor (String v : adjacencyList.keySet()) {removeEdge(v, vertex);}// Remove the vertex from the graphadjacencyList.remove(vertex);}public void removeEdge(String source, String destination) {if (!adjacencyList.containsKey(source)) return;ListEdge edges adjacencyList.get(source);for (int i 0; i edges.size(); i) {if (edges.get(i).getDestination().equals(destination)) {edges.remove(i);break;}}}public boolean hasVertex(String vertex) {return adjacencyList.containsKey(vertex);}public boolean hasEdge(String source, String destination) {if (!adjacencyList.containsKey(source)) return false;ListEdge edges adjacencyList.get(source);for (Edge edge : edges) {if (edge.getDestination().equals(destination)) {return true;}}return false;}public ListString depthFirstSearch(String startVertex) {SetString visited new HashSet();ListString result new ArrayList();dfsHelper(startVertex, visited, result);return result;}private void dfsHelper(String vertex, SetString visited, ListString result) {visited.add(vertex);result.add(vertex);for (Edge edge : adjacencyList.get(vertex)) {String neighbor edge.getDestination();if (!visited.contains(neighbor)) {dfsHelper(neighbor, visited, result);}}}public ListString breadthFirstSearch(String startVertex) {SetString visited new HashSet();QueueString queue new LinkedList();ListString result new ArrayList();queue.offer(startVertex);visited.add(startVertex);while (!queue.isEmpty()) {String vertex queue.poll();result.add(vertex);for (Edge edge : adjacencyList.get(vertex)) {String neighbor edge.getDestination();if (!visited.contains(neighbor)) {queue.offer(neighbor);visited.add(neighbor);}}}return result;}public int shortestPath(String source, String destination) {MapString, Integer distances new HashMap();PriorityQueueVertexDistancePairing pq new PriorityQueue(Comparator.comparingInt(VertexDistancePairing::getDistance));// Initialize distances to infinity, except for the source vertexfor (String vertex : adjacencyList.keySet()) {distances.put(vertex, Integer.MAX_VALUE);}distances.put(source, 0);pq.offer(new VertexDistancePairing(source, 0));while (!pq.isEmpty()) {VertexDistancePairing pair pq.poll();String currentVertex pair.getVertex();if (currentVertex.equals(destination)) {return pair.getDistance();}if (distances.get(currentVertex) pair.getDistance()) {continue;}for (Edge edge : adjacencyList.get(currentVertex)) {int newDistance distances.get(currentVertex) edge.getWeight();String neighbor edge.getDestination();if (newDistance distances.get(neighbor)) {distances.put(neighbor, newDistance);pq.offer(new VertexDistancePairing(neighbor, newDistance));}}}// If there is no path between source and destinationreturn -1;}public boolean isConnected(String startVertex, String endVertex) {SetString visited new HashSet();dfsHelper(startVertex, visited);return visited.contains(endVertex);}private void dfsHelper(String vertex, SetString visited) {visited.add(vertex);for (Edge edge : adjacencyList.get(vertex)) {String neighbor edge.getDestination();if (!visited.contains(neighbor)) {dfsHelper(neighbor, visited);}}}// Additional operationspublic ListEdge getEdges(String vertex) {return adjacencyList.containsKey(vertex) ? adjacencyList.get(vertex) : Collections.emptyList();}public MapString,ListEdge getAdjacencyList() {return this.adjacencyList;}public int getWeight(String source,String destination){if(hasEdge(source, destination)){for(Edge edge: adjacencyList.get(source)){if(edge.getDestination().equals(destination)){return edge.getWeight();}}}return -1; // If there is no edge between source and destination}public int getVertexCount() {return adjacencyList.size();}public int getEdgeCount() {int count 0;for (String vertex : adjacencyList.keySet()) {count adjacencyList.get(vertex).size();}// Divide by 2 as the graph is undirected and each edge is counted twicereturn count / 2;}public ListString getAllVertices() {return new ArrayList(adjacencyList.keySet());}
}class Edge {private String source;private String destination;private int weight;public Edge(String source, String destination, int weight) {this.source source;this.destination destination;this.weight weight;}public String getSource() {return source;}public String getDestination() {return destination;}public int getWeight() {return weight;}
}class VertexDistancePairing {private String vertex;private int distance;public VertexDistancePairing(String vertex, int distance) {this.vertex vertex;this.distance distance;}public String getVertex(){return vertex ;}public void setVertex(String v){this.vertexv ;}public Integer getDistance(){return distance ;}public void setDistance(int d){this.distanced ;}
}常用操作测试
public class Main {public static void main(String[] args) {// 创建一个无向加权图对象WeightedGraph graph new WeightedGraph();// 添加节点graph.addVertex(A);graph.addVertex(B);graph.addVertex(C);graph.addVertex(D);// 添加边graph.addEdge(A, B, 5);graph.addEdge(B, C, 3);graph.addEdge(C, D, 2);graph.addEdge(D, A, 4);// 深度优先搜索System.out.println(graph.depthFirstSearch(A));// 广度优先搜索System.out.println(graph.breadthFirstSearch(A));// 查找最短路径int shortestPath graph.shortestPath(A,D);if (shortestPath ! -1) {System.out.println(shortestPath);} else {System.out.println(节点A,D不相连);}boolean isConnected graph.isConnected(A,D);if (isConnected) {System.out.println(节点 A,D相连);} else {System.out.println(节点A,D不相连);}
// 删除节点和边System.out.println(graph.getAdjacencyList()); // 输出初始图graph.removeEdge(A,B);System.out.println(graph.getAdjacencyList()); // 移除边 A-Bgraph.removeVertex(C);System.out.println(graph.getAdjacencyList()); // 移除顶点 C}
}
