Java Graph

2025年5月2日 | 阅读 11 分钟

在 Java 中，**图**是一种存储一定数据的结构。**图**的概念源自数学，能够满足计算机科学领域的需求。它表示连接多个点的网络。在本节中，我们将详细学习 Java 图数据结构。此外，我们还将学习**图的类型**、它们的实现以及图的**遍历**。

Graph

**图**是一种存储连接数据的数据结构。换句话说，图 G (或 g) 被定义为一组顶点 (V) 和连接顶点的边 (E)。图的例子有社交网络、计算机网络、谷歌地图等。

每个图由**边**和**顶点**（也称为节点）组成。每个顶点和边都有关系。其中顶点表示数据，边表示它们之间的关系。顶点用带标签的圆圈表示。边用连接节点的线表示（顶点）。

图术语

**顶点：** 顶点是连接边的点。它代表数据。它也称为节点。它用圆圈表示，并且必须带标签。要构建一个图，至少需要一个节点。例如，房屋、公交车站等。

**边：** 边是连接两个顶点的线。它表示顶点之间的关系。边用线表示。例如，从你家到公交车站的路。

**权重：** 它是加在边上的标签。例如，两座城市之间的距离是 100 公里，那么距离就是边的权重。

**路径：** 路径是从初始点到目标点的顺序到达方式。

图的类型

**带权图：** 在带权图中，每条边都包含一些**数据**（权重），如距离、重量、高度等。它表示为 w(e)。它用于计算从一个顶点到另一个顶点的遍历成本。下图表示一个带权图。
**无权图：** 边不与任何值关联的图称为无权图。下图表示一个无权图。
**有向图：** 边表示方向的图称为有向图。在有向图中，我们使用箭头而不是线条（边）。方向表示从一个节点到另一个节点的路径。请注意，在有向图中，我们可以朝一个方向或两个方向移动。下图表示一个有向图。
**无向图：** 边是双向的图称为无向图。在无向图中，我们可以朝任何方向遍历。请注意，我们可以使用与来时相同的路径返回。而在有向图中，我们不能通过相同的路径返回。
**连通图：** 如果任意两个顶点之间都存在至少一条路径，则称该图为连通图。请注意，只有一个顶点的图是连通图。

连通图有两种类型。
1. **弱连通图：** 无法通过单条路径访问节点的图称为弱连通图。
2. **强连通图：** 可以通过单条路径访问节点的图称为强连通图。
**不连通图：** 如果任意两个顶点之间不存在路径，则该图称为不连通图。不连通图可能由两个或多个连通图组成。
**多重图：** 连接同一对节点的多条边的图。下图表示一个多重图。
**稠密图：** 边数接近最大可能边数的图称为稠密图。下图表示一个稠密图。
**稀疏图：** 边数接近最小可能边数的图称为稀疏图。它可以是不连通图。下图表示一个稀疏图。

Java 图实现

要在 Java 中实现图，我们将使用泛型类。要创建 Java 泛型类的对象，我们使用以下语法

请记住，我们不能将原始类型用作参数类型。

让我们创建一个实现图的 Java 程序。

GraphImplementation.java

import java.util.*; 
class Graph<T> 
{ 
//creating an object of the Map class that stores the edges of the graph
private Map<T, List<T> > map = new HashMap<>(); 
//the method adds a new vertex to the graph
public void addNewVertex(T s) 
{ 
map.put(s, new LinkedList<T>()); 
} 
//the method adds an edge between source and destination 
public void addNewEdge(T source, T destination, boolean bidirectional) 
{ 
//    
if (!map.containsKey(source)) 
addNewVertex(source); 
if (!map.containsKey(destination)) 
addNewVertex(destination); 
map.get(source).add(destination); 
if (bidirectional == true) 
{ 
map.get(destination).add(source); 
} 
} 
//the method counts the number of vertices
public void countVertices() 
{ 
System.out.println("Total number of vertices: "+ map.keySet().size()); 
} 
//the method counts the number of edges
public void countEdges(boolean bidirection) 
{ 
//variable to store number of edges    
int count = 0; 
for (T v : map.keySet()) 
{ 
count = count + map.get(v).size(); 
} 
if (bidirection == true) 
{ 
count = count / 2; 
} 
System.out.println("Total number of edges: "+ count); 
} 
//checks a graph has vertex or not
public void containsVertex(T s) 
{ 
if (map.containsKey(s)) 
{ 
System.out.println("The graph contains "+ s + " as a vertex."); 
} 
else 
{ 
System.out.println("The graph does not contain "+ s + " as a vertex."); 
} 
} 
//checks a graph has edge or not
//where s and d are the two parameters that represent source(vertex) and destination (vertex)
public void containsEdge(T s, T d) 
{ 
if (map.get(s).contains(d)) 
{ 
System.out.println("The graph has an edge between "+ s + " and " + d + "."); 
} 
else 
{ 
System.out.println("There is no edge between "+ s + " and " + d + "."); 
} 
} 
//prints the adjacencyS list of each vertex
//here we have overridden the toString() method of the StringBuilder class
@Override
public String toString() 
{ 
StringBuilder builder = new StringBuilder(); 
//foreach loop that iterates over the keys
for (T v : map.keySet()) 
{ 
builder.append(v.toString() + ": "); 
//foreach loop for getting the vertices
for (T w : map.get(v)) 
{ 
builder.append(w.toString() + " "); 
} 
builder.append("\n"); 
} 
return (builder.toString()); 
} 
} 
//creating a class in which we have implemented the driver code
public class GraphImplementation
{ 
public static void main(String args[]) 
{ 
//creating an object of the Graph class
Graph graph=new Graph();
//adding edges to the graph
graph.addNewEdge(0, 1, true); 
graph.addNewEdge(0, 4, true); 
graph.addNewEdge(1, 2, true); 
graph.addNewEdge(1, 3, false); 
graph.addNewEdge(1, 4, true); 
graph.addNewEdge(2, 3, true); 
graph.addNewEdge(2, 4, true); 
graph.addNewEdge(3, 0, true); 
graph.addNewEdge(2, 0, true); 
//prints the adjacency matrix that represents the graph
System.out.println("Adjacency List for the graph:\n"+ graph.toString()); 
//counts the number of vertices in the graph 
graph.countVertices(); 
//counts the number of edges in the graph 
graph.countEdges(true); 
//checks whether an edge is present or not between the two specified vertices
graph.containsEdge(3, 4); 
graph.containsEdge(2, 4); 
//checks whether vertex is present or not 
graph.containsVertex(3); 
graph.containsVertex(5); 
} 
}

输出

有向图实现

DirectedGraph.java

import java.util.*;
//Creating a class named Edge that stores the edges of the graph
class Edge 
{
//the variable source and destination represent the vertices     
int s, d;
//creating a constructor of the class Edge
Edge(int s, int d) 
{
this.s = s;
this.d = d;
}
}
//a class to represent a graph object
class Graph
{
//note that we have created an adjacency list (i.e. List of List)    
List<List<Integer>> adjlist = new ArrayList<>();
//creating a constructor of the class Graph that construct a graph
public Graph(List<Edge> edges)
{
int n = 0;
//foreach loop that iterates over the edge
for (Edge e: edges) 
{
//determines the maximum numbered vertex    
n = Integer.max(n, Integer.max(e.s, e.d));
}
//reserve the space for the adjacency list
for (int i = 0; i <= n; i++) 
{
adjlist.add(i, new ArrayList<>());
}
//adds the edges to the undirected graph
for (Edge current: edges)
{
//allocate new node in adjacency list from source to destination
adjlist.get(current.s).add(current.d);
}
}
//Function to print adjacency list representation of a graph
public static void showGraph(Graph graph)
{
int s = 0;
//determines the size of the adjacency list
int n = graph.adjlist.size();
while (s < n)
{
//prints the neighboring vertices including the current vertex
for (int d: graph.adjlist.get(s)) 
{
System.out.print("Adjacency List for the graph is:");    
//prints the edge between the two vertices    
System.out.print("(" + s + " -- > " + d + ")\t");
}
System.out.println();
//increments the source by 1
s++;
}
}
}
//implementing driver code
public class DirectedGraph
{
public static void main (String args[])
{
//creating a List of edges
List<Edge> edges = Arrays.asList(new Edge(0, 1), new Edge(1, 2), new Edge(2, 4), new Edge(4, 1),new Edge(3, 2), new Edge(2, 5), new Edge(3, 4), new Edge(5, 4), new Edge(1, 1));
// construct a graph from the given list of edges
Graph graph = new Graph(edges);
//prints the adjacency list that represents graph
Graph.showGraph(graph);
}
}

输出

带权图实现

WeightedGraph.java

import java.util.*;
//the class stores the edges of the graph
class Edge 
{
int s, d, w;
//creating a constructor of the class Edge
Edge(int src, int dest, int weight) 
{
this.s = src;
this.d = dest;
this.w = weight;
}
}
//a class to store adjacency list nodes
class Node 
{
int value, weight;
//creating a constructor of the class Vertex
Node(int value, int weight) 
{
this.value = value;
this.weight = weight;
}
//overrides the toString() method
@Override
public String toString() 
{
return this.value + " (" + this.weight + ")";
}
}
//a class to represent a graph object
class Graph
{
//note that we have created an adjacency list (i.e. List of List)    
List<List<Node>> adjlist = new ArrayList<>();
//creating a constructor of the class Graph that creates graph
public Graph(List<Edge> edges)
{
//find the maximum numbered vertex
int n = 0;
//iterates over the edges of the graph
for (Edge e: edges) 
{
//determines the maximum numbered vertex         
n = Integer.max(n, Integer.max(e.s, e.d));
}
//reserve the space for the adjacency list
for (int i = 0; i <= n; i++) 
{
adjlist.add(i, new ArrayList<>());
}
//adds the edges to the undirected graph
for (Edge e: edges)
{
//creating a new node (from source to destination) in the adjacency list 
adjlist.get(e.s).add(new Node(e.d, e.w));
//uncomment the following statement for undirected graph
//adj.get(e.dest).add(new Node(e.src, e.weight));
}
}
//method that prints adjacency list of a graph
public static void printGraph(Graph graph)
{
int src = 0;
int n = graph.adjlist.size();
System.out.printf("Adjacency List for the Graph is: ");    
while (src < n)
{
//for-each loop prints the neighboring vertices with current vertex   
for (Node edge: graph.adjlist.get(src)) 
{
System.out.printf("%d -- > %s\t", src, edge);
}
System.out.println();
//increments the source by 1
src++;
}
}
}
//implementing driver code
public class WeightedGraph
{
public static void main (String args[])
{
//creating a list of edges with their associated weight 
List<Edge> edges = Arrays.asList(new Edge(1, 4, 3), new Edge(4, 2, 5), new Edge(2, 5, 10), new Edge(5, 1, 6), new Edge(3, 2, 9), new Edge(1, 5, 1), new Edge(3, 5, 2));
//creates a graph with the edges declared above
Graph graph = new Graph(edges);
//prints the corresponding adjacency list for the graph
Graph.printGraph(graph);
}
}

输出

图遍历

图的遍历是指至少访问一次每个顶点和边。为了遍历图，图数据结构提供了两种算法

深度优先搜索 (DFS)
广度优先搜索 (DFS)

深度优先搜索 (DFS)

DFS 算法是一种基于回溯概念的递归算法。该算法从初始节点开始，并深入搜索，直到找到目标节点（一个没有子节点的节点）。回溯允许我们在向前遍历的同一条路径上向后移动。

让我们在 Java 程序中实现 DFS 算法。

DepthFirstSearch.java

import java.io.*; 
import java.util.*; 
//creates an undirected graph
class Graph 
{ 
//stores the number of vertices		
private int Vertices;   
//creates a linked list for the adjacency list of the graph 
private LinkedList<Integer> adjlist[]; 
//creating a constructor of the Graph class 
Graph(int count_v) 
{ 
//assigning the number of vertices to the passed parameter	
Vertices = count_v; 
adjlist = new LinkedList[count_v]; 
//loop for creating the adjacency lists
for (int i=0; i<count_v; ++i) 
adjlist[i] = new LinkedList(); 
} 
//method that adds a new edge to the graph
void addNewEdge(int v, int w) 
{ 
adjlist[v].add(w);  // Add w to v's list. 
} 
//logic of the DFS
//traversal starts from the root node 
void traversalDFS(int v, boolean vnodelist[]) 
{ 
//if current node (root node) is visited, add it to the vnodelist 
vnodelist[v] = true; 
System.out.print(v+" "); 
//detrmines the negihboring nodes of the current node
//iterates over the list  
Iterator<Integer> i = adjlist[v].listIterator(); 
while (i.hasNext()) 
{ 
//returns the next element in the iteration and store that element in the variable n	
int n = i.next(); 
if (!vnodelist[n]) 
//calling the function that performs depth first traversal	
traversalDFS(n, vnodelist); 
} 
} 
void DFS(int v) 
{ 
//creates an array of boolean type for visited node 
//initially all nodes are unvisited
boolean visited[] = new boolean[Vertices]; 
//call recursive traversalDFS() function for DFS 
traversalDFS(v, visited); 
} 
}
//implementing driver code
public class DepthFirstSearch
{
public static void main(String args[]) 
{ 
//creates a graph having 10 vertices
Graph g = new Graph(10); 
//add edges to the graph  
g.addNewEdge(1, 2); 
g.addNewEdge(2, 3); 
g.addNewEdge(3, 4); 
g.addNewEdge(4, 5); 
g.addNewEdge(5, 7);
g.addNewEdge(1, 3); 
g.addNewEdge(1, 5); 
g.addNewEdge(5, 5); 
g.addNewEdge(2, 6); 
g.addNewEdge(3, 7);
//print sequencnce in which BFS traversal done 
System.out.println("Depth-first traversal of graph is: ");
//traversal starts from the node 3 (as root node)
g.DFS(1); 
} 
}

输出

广度优先搜索 (BFS)

BFS 算法是遍历图最常见的方法。遍历从源节点开始，并扫描其邻居节点（当前节点的子节点）。简而言之，水平遍历并访问当前层的所有节点。然后，移动到下一层并执行相同的操作。

让我们在 Java 程序中实现 BFS 算法。

BreadthFirstSearch.java

import java.io.*; 
import java.util.*; 
//creates an undirected graph
class Graph 
{ 
//stores the number of vertices	
private int vertices;  
//creates a linked list for the adjacency list of the graph 
private LinkedList<Integer> adjlist[]; 
//creating a constructor of the Graph class 
Graph(int count_v) 
{ 
//assigning the number of vertices to the passed parameter
vertices = count_v; 
adjlist = new LinkedList[count_v]; 
//loop for creating the adjacency lists
for (int i=0; i<count_v; ++i)         
adjlist[i] = new LinkedList(); 
} 
//method that adds a new edge to the graph
void addNewEdge(int v, int w) 
{ 
adjlist[v].add(w); 
} 
//traversal starts from the root node 
void traversalBFS(int rnode)   
{ 
//creates an array of boolean type for visited node 
//initially all nodes are unvisited
boolean visitednode[] = new boolean[vertices]; 
//creating another list for storing the visited node
LinkedList<Integer> vnodelist = new LinkedList<Integer>(); 
//if current node (root node) is visited, add it to the vnodelist 
visitednode[rnode]=true; 
//inserts the visited node into vnodelist
vnodelist.add(rnode); 
//the while loop executes until we have visited all the nodes
while (vnodelist.size() != 0)  
{ 
//deque an entry from queue and process it  
//the poll() method retrieves and removes the head (first element) of this list
rnode = vnodelist.poll(); 
System.out.print(rnode+" "); 
//detrmines the negihboring nodes of the current node
//iterates over the list 
Iterator<Integer> i = adjlist[rnode].listIterator(); 
while (i.hasNext())
{ 
//returns the next element in the iteration and store that element in the variable n	
int n = i.next(); 
//checks the next node is visited or not
if (!visitednode[n]) 
{ 
//if the above if-statement returns true, visits the node 
visitednode[n] = true; 
//adds the visited node in the vnodelist
vnodelist.add(n); 
} 
} 
} 
} 
}
//implementing driver code
public class BreadthFirstSearch 
{ 
public static void main(String args[]) 
{ 
//creates a graph having 10 vertices
Graph graph = new Graph(10); 
//add edges to the graph  
graph.addNewEdge(2, 5); 
graph.addNewEdge(3, 5); 
graph.addNewEdge(1, 2); 
graph.addNewEdge(2, 4); 
graph.addNewEdge(4, 1); 
graph.addNewEdge(6, 2); 
graph.addNewEdge(5, 6); 
graph.addNewEdge(1, 6); 
graph.addNewEdge(6, 3); 
graph.addNewEdge(3, 1); 
graph.addNewEdge(7, 3); 
graph.addNewEdge(3, 7); 
graph.addNewEdge(7, 5); 
//print sequence in which BFS traversal execute
System.out.println("Breadth-first traversal sequence is: "); 
//root node
graph.traversalBFS(2); 
} 
}

输出

下一个主题Java-program-to-find-the-mean-of-array-using-recursion

Java Graph

Graph

图术语

图的类型

Java 图实现

有向图实现

带权图实现

图遍历

深度优先搜索 (DFS)

广度优先搜索 (BFS)

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java Graph

Graph

图术语

图的类型

Java 图实现

有向图实现

带权图实现

图遍历

深度优先搜索 (DFS)

广度优先搜索 (BFS)

相关帖子

Pangram Checking in Java

创建 Java 临时文件

Icon interface Java

GST emSigner Java Download

Java 中包的优点

Java 中显示整数数组的所有子集

Example of Static Import in Java

查找 Java 中数组元素的索引

RuleBasedCollator getCollationElementIterator(String) method in Java

Java 中读取 PDF 文件

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器