图（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());
}
}
}
