21xrx.com
2024-06-03 00:13:50 Monday
登录
文章检索 我的文章 写文章
Java构建图的方法和案例分享
2023-06-16 22:23:12 深夜i     --     --
Java

在Java中，构建图是一个非常常见的需求，无论是网络图、机器学习的神经网络、连通图等等，都需要用到图的概念和操作。那么，如何在Java中构建图呢？本文将结合代码案例和实际应用场景，为读者介绍几种Java构建图的方法。

# 方法一：手动构建

最直接的方法就是手动构建，通过Java中的数据结构，例如数组和链表等实现。这种方法需要我们比较熟练地掌握图的基本概念和数据结构，代码量较大，但是灵活度和掌控度非常高。

假设我们需要构建下面这张简单的无向图：



 0 -- 1


/ \


2 - 3

我们可以用Java中的邻接表（Adjacency List）来表示这个图：



import java.util.*;


public class Graph {


  Map
  > adjList;
 


  public Graph() {


    adjList = new HashMap<>();


  }


  public void addEdge(int u, int v) {


    List
  neighborsU = adjList.getOrDefault(u, new ArrayList<>());
 


    neighborsU.add(v);


    adjList.put(u, neighborsU);


    // Undirected graph. So, add an edge from v to u as well


    List
  neighborsV = adjList.getOrDefault(v, new ArrayList<>());
 


    neighborsV.add(u);


    adjList.put(v, neighborsV);


  }


  public List
  getNeighbors(int vertex) {
 


    return adjList.getOrDefault(vertex, new ArrayList<>());


  }


}

然后我们可以这样使用这个类：



Graph graph = new Graph();


graph.addEdge(0, 1);


graph.addEdge(0, 2);


graph.addEdge(1, 3);


graph.addEdge(2, 3);


List
  neighbors = graph.getNeighbors(0);
 


System.out.println(neighbors);

输出结果为： `[1, 2]`

# 方法二：使用第三方库

Java中有很多第三方库可以帮助我们构建图，例如JGraphT和Apache Commons Graph。这两个库都提供了很多现成的图数据结构和算法实现，可以大大简化我们的工作。

以JGraphT为例，我们可以这样构建同样的无向图：



import org.jgrapht.Graph;


import org.jgrapht.graph.DefaultEdge;


import org.jgrapht.graph.SimpleGraph;


public class GraphJGraphT {


  public static void main(String[] args) {


    Graph
  graph = new SimpleGraph(DefaultEdge.class);
 


    graph.addVertex(0);


    graph.addVertex(1);


    graph.addVertex(2);


    graph.addVertex(3);


    graph.addEdge(0, 1);


    graph.addEdge(0, 2);


    graph.addEdge(1, 3);


    graph.addEdge(2, 3);


    System.out.println(graph.degreeOf(0));


  }


}

输出结果为：`2`

从代码上看，使用第三方库可以大大简化我们的工作。JGraphT内部使用的数据结构是邻接表（Adjacency List），因此同样适合处理大型的稀疏图。

# 方法三：使用专用的图算法库

如果我们的应用场景需要使用到图的算法、图的可视化等比较高级的功能，那么使用专门的图算法库会更加方便。

例如可以使用GraphStream这个库来进行图的可视化和算法运算。以下是一个简单的例子：



import org.graphstream.graph.Graph;


import org.graphstream.graph.Node;


import org.graphstream.graph.implementations.SingleGraph;


public class GraphDemo {


  public static void main(String[] args) {


    Graph graph = new SingleGraph("Tutorial 1");


    graph.addNode("A" );


    graph.addNode("B" );


    graph.addNode("C" );


    graph.addEdge("AB", "A", "B");


    graph.addEdge("BC", "B", "C");


    graph.addEdge("CA", "C", "A");


    graph.getNode("A").setAttribute("xyz", new double[] 0);


    graph.getNode("B").setAttribute("xyz", new double[] 0);


    graph.getNode("C").setAttribute("xyz", new double[] 0);


    graph.display(false);


  }


}

以上代码将会生成下面这个图：

![](https://cdn.jsdelivr.net/gh/zhendong233/img-bed/img/20211023163328.png)

此时我们已经可以使用一些图算法对这个图进行进一步的操作了，例如寻找最短路径等等。

三个 图, 构建

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复