图(Graph)是计算机科学中一种重要的非线性数据结构,广泛应用于社交网络、地图导航、任务调度等领域。本文将使用 Java 语言深入讲解图论中的两个基本概念:有向图和无向图。
什么是图?
图由两个基本元素组成:
- 顶点(Vertex/Node):图中的节点,代表对象
- 边(Edge):连接两个顶点,代表对象之间的关系
数学表示:G = (V, E),其中 V 是顶点集合,E 是边集合。
无向图(Undirected Graph)
概念与特点
无向图中的边没有方向,表示对称的双向关系。如果顶点 A 和顶点 B 之间存在一条边,那么可以从 A 到达 B,也可以从 B 到达 A。
实际应用
- 社交网络:微信好友关系(互为好友)
- 交通网络:城市间的双向道路
- 协作关系:项目团队成员之间的合作关系
- 网络拓扑:局域网中设备的连接关系
Java 实现:邻接表方式
import java.util.*;
/**
* 无向图的实现(使用邻接表)
*/
public class UndirectedGraph {
// 使用 HashMap 存储图,key 为顶点,value 为邻接顶点列表
private Map<String, List<String>> adjList;
public UndirectedGraph() {
this.adjList = new HashMap<>();
}
/**
* 添加顶点
*/
public void addVertex(String vertex) {
adjList.putIfAbsent(vertex, new ArrayList<>());
}
/**
* 添加边(无向边,需要双向添加)
*/
public void addEdge(String v1, String v2) {
// 确保两个顶点都存在
addVertex(v1);
addVertex(v2);
// 添加双向边
adjList.get(v1).add(v2);
adjList.get(v2).add(v1);
}
/**
* 移除边
*/
{
List<String> v1Neighbors = adjList.get(v1);
List<String> v2Neighbors = adjList.get(v2);
(v1Neighbors != ) {
v1Neighbors.remove(v2);
}
(v2Neighbors != ) {
v2Neighbors.remove(v1);
}
}
{
List<String> neighbors = adjList.get(vertex);
(neighbors != ) {
(String neighbor : <>(neighbors)) {
removeEdge(vertex, neighbor);
}
}
adjList.remove(vertex);
}
{
List<String> neighbors = adjList.get(vertex);
neighbors != ? neighbors.size() : ;
}
List<String> {
adjList.getOrDefault(vertex, <>());
}
{
Set<String> visited = <>();
dfsHelper(start, visited);
}
{
visited.add(vertex);
System.out.print(vertex + );
(String neighbor : getNeighbors(vertex)) {
(!visited.contains(neighbor)) {
dfsHelper(neighbor, visited);
}
}
}
{
Set<String> visited = <>();
Queue<String> queue = <>();
visited.add(start);
queue.offer(start);
(!queue.isEmpty()) {
queue.poll();
System.out.print(vertex + );
(String neighbor : getNeighbors(vertex)) {
(!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
{
System.out.println();
(Map.Entry<String, List<String>> entry : adjList.entrySet()) {
System.out.println(entry.getKey() + + entry.getValue());
}
}
}

