长春企业网站seo首页百度

概念：

数据结构图（Graph）是一种非线性的数据结构，用于表示节点之间的关系。它由节点（Vertex）和边（Edge）组成，每个节点可以与其他节点通过边连接起来。图分为有向图和无向图，顾名思义在有向图中边是有方向的，而在无向图中边是没有方向的。图也可以分为有权图和无权图，有权图是指边具有一个相关联的权重值，无权图是指边没有权重值。

特点：

• 非线性结构：图中的节点和边形成复杂的连接关系，不同于数组、链表等线性结构。
• 可变大小：图可以动态增长或缩小，并且支持添加、删除、修改节点和边。
• 实体关系表示：适合用于表示实体对象之间的相互关系，如社交网络中用户之间的好友关系。

优点：

1. 模型灵活性高：可以模拟各种现实情况下复杂而多样化的问题，并提供了多种算法来解决这些问题。
2. 具备强大搜索能力：通过遍历算法如深度优先搜索 (DFS) 和广度优先搜索 (BFS)，能够有效地查找特定元素或路径。

缺点：

1. 占用更多内存空间：相比线性结构，图可能需要更多的空间来存储节点和边之间的关系。
2. 高复杂度：某些图算法的时间复杂度相对较高，尤其在大规模数据上进行操作时。

适用场景：

• 社交网络分析。
• 地图导航系统。
• 网络拓扑结构表达和分析。

实现代码：

无向有权图的简单实现

import java.util.*;class WeightedGraph {private Map<String, List<Edge>> 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;List<Edge> 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;List<Edge> edges = adjacencyList.get(source);for (Edge edge : edges) {if (edge.getDestination().equals(destination)) {return true;}}return false;}public List<String> depthFirstSearch(String startVertex) {Set<String> visited = new HashSet<>();List<String> result = new ArrayList<>();dfsHelper(startVertex, visited, result);return result;}private void dfsHelper(String vertex, Set<String> visited, List<String> 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 List<String> breadthFirstSearch(String startVertex) {Set<String> visited = new HashSet<>();Queue<String> queue = new LinkedList<>();List<String> 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) {Map<String, Integer> distances = new HashMap<>();PriorityQueue<VertexDistancePairing> 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) {Set<String> visited = new HashSet<>();dfsHelper(startVertex, visited);return visited.contains(endVertex);}private void dfsHelper(String vertex, Set<String> visited) {visited.add(vertex);for (Edge edge : adjacencyList.get(vertex)) {String neighbor = edge.getDestination();if (!visited.contains(neighbor)) {dfsHelper(neighbor, visited);}}}// Additional operationspublic List<Edge> getEdges(String vertex) {return adjacencyList.containsKey(vertex) ? adjacencyList.get(vertex) : Collections.emptyList();}public Map<String,List<Edge>> 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 List<String> 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.vertex=v ;}public Integer getDistance(){return distance ;}public void setDistance(int d){this.distance=d ;}
}

常用操作测试：

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}
}