1、创建一个普通的Graph
package com.datastructure.graph;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
//图是由节点(顶点)和连接它们的边组成的一种数据结构。它可以用来表示实际世界中的各种关系,比如社交网络中的用户关系、道路网络中的城市连接等。
//在图中,节点表示实体,边表示节点之间的关系。边可以有方向,也可以没有。具有方向的边称为有向边,没有方向的边称为无向边。图可以是有向图(digraph)或无向图。
//图可以用多种方式来表示,最常见的方式包括邻接列表(adjacency list)和邻接矩阵(adjacency matrix)。
//- 邻接列表:将每个节点的邻居节点列表存储在列表或数组中。对于有向图,可以为每个节点维护出度和入度的邻接列表。这种表示方法在稀疏图中通常更有效。
//- 邻接矩阵:使用二维数组来表示图,其中行和列分别表示节点,矩阵的值表示边的存在与否。对于有向图,可以使用一个矩阵表示出边,另一个矩阵表示入边。这种表示方法在稠密图中通常更有效。
//图可以进行多种操作,如添加节点、添加边、删除节点、删除边、判断节点是否相邻、遍历图等。图还可以通过深度优先搜索、广度优先搜索等算法来解决一些图问题。
//图的表示和操作在不同语言和库中有所不同。在Java中,可以使用图的相关类和接口来创建和操作图,如Java中的JGraphT库或使用邻接列表或邻接矩阵自行实现。
//创建一个图类
public class Graph {
private Map<String, List<String>> adjacencyList;
public Graph() {
this.adjacencyList = new HashMap<>();
}
public void addVertex(String vertex) {
if (!adjacencyList.containsKey(vertex)) {
adjacencyList.put(vertex, new ArrayList<>());
}
}
public void addEdge(String vertex1, String vertex2) {
if (adjacencyList.containsKey(vertex1) && adjacencyList.containsKey(vertex2)) {
adjacencyList.get(vertex1).add(vertex2);
adjacencyList.get(vertex2).add(vertex1);
}
}
public void removeVertex(String vertex) {
if (adjacencyList.containsKey(vertex)) {
List<String> adjacentVertices = adjacencyList.get(vertex);
adjacencyList.remove(vertex);
for (List<String> vertices : adjacencyList.values()) {
vertices.remove(vertex);
}
}
}
public void removeEdge(String vertex1, String vertex2) {
if (adjacencyList.containsKey(vertex1) && adjacencyList.containsKey(vertex2)) {
adjacencyList.get(vertex1).remove(vertex2);
adjacencyList.get(vertex2).remove(vertex1);
}
}
public void printGraph() {
for (Map.Entry<String, List<String>> entry : adjacencyList.entrySet()) {
System.out.print(entry.getKey() + " -> ");
List<String> adjacentVertices = entry.getValue();
for (String vertex : adjacentVertices) {
System.out.print(vertex + ", ");
}
System.out.println();
}
}
}
package com.datastructure.graph;
public class GraphDemo {
public static void main(String[] args) {
// 创建图的实例
Graph graph = new Graph();
// 添加顶点
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
// 添加边
graph.addEdge("A", "B");
graph.addEdge("B", "C");
graph.addEdge("C", "A");
// 打印图
graph.printGraph();
// 删除一个顶点和边
graph.removeVertex("A");
graph.removeEdge("B", "C");
// 打印修改后的图
graph.printGraph();
}
}
2、邻接矩阵:
package com.datastructure.graph;
//创建一个大小为5的邻接矩阵,并添加一些边。
public class AdjacencyMatrixDemo {
private final int V;
private final int[][] matrix;
public AdjacencyMatrixDemo(int V) {
this.V = V;
this.matrix = new int[V][V];
}
public void addEdge(int u, int v) {
matrix[u][v] = 1;
}
public void removeEdge(int u, int v) {
matrix[u][v] = 0;
}
public boolean hasEdge(int u, int v) {
return matrix[u][v] == 1;
}
public void printMatrix() {
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
AdjacencyMatrixDemo graph = new AdjacencyMatrixDemo(5);
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.printMatrix();
}
}
3、邻接表:
package com.datastructure.graph;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
//邻接表是一种常见的图表示方法,其中使用一个数组来存储图的顶点,并使用链表来存储每个顶点的邻接顶点。
//创建了Graph类来表示图。
//构造方法中,初始化邻接表的数组,并初始化每个顶点对应的链表。
//addEdge()方法用于添加边,在邻接表中的两个顶点的链表中添加对方。
//print()方法用于打印邻接表,输出每个顶点的邻接顶点。
//在main方法中,创建一个图,并使用addEdge()方法添加边。
//最后,调用print()方法打印邻接表。
//可以使用邻接表来表示图的数据结构,并进行相关的图算法操作。
public class GraphAdjacencyList {
private int numVertices;
private List<List<Integer>> adjList;
// 构造方法
public GraphAdjacencyList(int numVertices) {
this.numVertices = numVertices;
adjList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjList.add(new LinkedList<>());
}
}
// 添加边
public void addEdge(int src, int dest) {
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
// 打印邻接表
public void print() {
for (int i = 0; i < numVertices; i++) {
System.out.print("顶点 " + i + ": ");
for (Integer neighbor : adjList.get(i)) {
System.out.print(neighbor + " -> ");
}
System.out.println();
}
}
public static void main(String[] args) {
GraphAdjacencyList graph = new GraphAdjacencyList(5);
// 添加边
graph.addEdge(0, 1);
graph.addEdge(0, 4);
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
// 打印邻接表
graph.print();
}
}