如果要实现一个邻接表无向图的Java程序,需要进行以下几个步骤:
1. 定义节点类
首先定义一个节点类来存储图中的每个节点以及它们之间的关系(边):
class Node {
int label; // 节点编号
List<Node> edges = new LinkedList<>(); // 存储与该节点相连的边
Node(int label) {
this.label = label;
}
}
这里使用了Java集合框架的LinkedList
来存储边,而不是数组。因为在邻接表中,节点不一定和每个节点都相连,而数组必须分配固定大小,会浪费很多空间。而LinkedList
则可以根据需要调整大小,只分配必要的空间。
2. 定义图类
接下来,我们需要定义一个图类来管理所有节点和它们之间的关系。
class Graph {
List<Node> nodes = new LinkedList<>(); // 存储所有节点
void addNode(Node node) {
nodes.add(node);
}
void addEdge(Node source, Node dest) {
// 添加无向边
source.edges.add(dest);
dest.edges.add(source);
}
}
Graph
类内部维护了一个节点列表nodes
,通过addNode()
方法可以向这个列表添加新的节点,通过addEdge()
方法可以在两个节点之间添加一条无向边。这里我们对于无向图的每条边,都需要同时在它链接的两个节点之间建立双向连接。
3. 示例1:创建一个简单的图并输出所有节点和它们之间的关系
现在我们已经定义了邻接表无向图的节点和图类,可以用以下代码创建一个简单的图:
Graph g = new Graph();
Node a = new Node(1);
Node b = new Node(2);
Node c = new Node(3);
Node d = new Node(4);
g.addNode(a);
g.addNode(b);
g.addNode(c);
g.addNode(d);
g.addEdge(a, c);
g.addEdge(b, c);
g.addEdge(b, d);
这个图包含了四个节点(标签分别为1到4)和三条边,其中1和3相连,2和3相连,2和4相连。现在我们可以用以下代码输出所有节点以及它们之间的关系:
for(Node n : g.nodes) {
System.out.print(n.label + ": ");
for(Node e : n.edges) {
System.out.print(e.label + " ");
}
System.out.println();
}
输出结果应该为:
1: 3
2: 3 4
3: 1 2
4: 2
4. 示例2:查找某一个节点的所有相邻节点
如果想要查询某一节点的所有相邻节点,可以写一个adjacentNodes()
方法来实现:
List<Node> adjacentNodes(Node node) {
return node.edges;
}
这是一个很简单的方法,它接受一个节点作为参数,返回一个列表,其中包含该节点连接的所有边对应的另外一个节点。接下来可以调用这个方法来查询节点2的所有相邻节点:
List<Node> adjNodes = g.adjacentNodes(b);
for(Node n : adjNodes) {
System.out.println(n.label);
}
输出结果应该为:
3
4
这些就是实现邻接表无向图的Java语言源代码的完整攻略和示例说明。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:邻接表无向图的Java语言实现完整源码 - Python技术站