图(Graph)是一种非线性数据结构,由节点(或顶点,Vertex)和边(Edge)组成。边可能带有权重,表示两个节点之间的某种关系或距离。图结构广泛应用于计算机科学中,如网络路由、社交网络分析、数据结构优化等。
基本概念
- 节点(Vertex):图中的基本元素,通常表示为一个点或对象。
- 边(Edge):连接两个节点的线段或弧线,表示两个节点之间的关系。
- 无向图(Undirected Graph):边没有方向的图。
- 有向图(Directed Graph):边有方向的图,通常表示为箭头。
- 权重(Weight):边可能带有的数值,表示两个节点之间的某种度量或距离。
- 邻接节点(Adjacent Vertex):通过一个边与给定节点相连的所有节点。
- 度(Degree):无向图中一个节点的邻接节点的数量;有向图中分为入度(指向该节点的边的数量)和出度(从该节点出发的边的数量)。
特点
- 非线性:节点之间的关系不是线性的,可以任意连接。
- 灵活性:可以表示复杂的关系网络。
- 多样性:包括无向图、有向图、加权图等多种类型。
代码实现
下面是一个使用Java实现的简单无向图,包括准备数据、创建图、清空图、显示图和遍历图(深度优先搜索DFS和广度优先搜索BFS)的基本操作。
首先,我们定义一个Vertex
类来表示图的顶点,以及一个Graph
类来表示图本身:
下面是一个使用Java实现的简单无向图,包括准备数据、创建图、清空图、显示图和遍历图(深度优先搜索DFS和广度优先搜索BFS)的基本操作。
首先,我们定义一个Vertex
类来表示图的顶点,以及一个Graph
类来表示图本身:
import java.util.*; | |
class Vertex { | |
String label; | |
Vertex(String label) { | |
this.label = label; | |
} | |
@Override | |
public String toString() { | |
return label; | |
} | |
} | |
class Graph { | |
private Map<Vertex, List<Vertex>> adjList; | |
Graph() { | |
adjList = new HashMap<>(); | |
} | |
void addVertex(Vertex v) { | |
adjList.put(v, new ArrayList<>()); | |
} | |
void addEdge(Vertex v1, Vertex v2) { | |
adjList.get(v1).add(v2); | |
adjList.get(v2).add(v1); // 无向图,所以两个方向都要添加 | |
} | |
void removeVertex(Vertex v) { | |
for (List<Vertex> neighbors : adjList.values()) { | |
neighbors.remove(v); | |
} | |
adjList.remove(v); | |
} | |
void clearGraph() { | |
adjList.clear(); | |
} | |
void displayGraph() { | |
for (Map.Entry<Vertex, List<Vertex>> entry : adjList.entrySet()) { | |
System.out.println(entry.getKey() + " -> " + entry.getValue()); | |
} | |
} | |
// 深度优先搜索 | |
void dfs(Vertex v, boolean[] visited) { | |
visited[v.hashCode()] = true; | |
System.out.print(v + " "); | |
for (Vertex neighbor : adjList.get(v)) { | |
if (!visited[neighbor.hashCode()]) { | |
dfs(neighbor, visited); | |
} | |
} | |
} | |
void dfs(Vertex startVertex) { | |
boolean[] visited = new boolean[100]; // 假设图的大小不会超过100个顶点 | |
Arrays.fill(visited, false); | |
dfs(startVertex, visited); | |
} | |
// 广度优先搜索 | |
void bfs(Vertex startVertex) { | |
Queue<Vertex> queue = new LinkedList<>(); | |
Set<Vertex> visited = new HashSet<>(); | |
queue.add(startVertex); | |
visited.add(startVertex); | |
while (!queue.isEmpty()) { | |
Vertex v = queue.poll(); | |
System.out.print(v + " "); | |
for (Vertex neighbor : adjList.get(v)) { | |
if (!visited.contains(neighbor)) { | |
queue.add(neighbor); | |
visited.add(neighbor); | |
} | |
} | |
} | |
} | |
public static void main(String[] args) { | |
Graph g = new Graph(); | |
// 准备数据 | |
Vertex A = new Vertex("A"); | |
Vertex B = new Vertex("B"); | |
Vertex C = new Vertex("C"); | |
Vertex D = new Vertex("D"); | |
Vertex E = new Vertex("E"); | |
Vertex F = new Vertex("F"); | |
// 创建图 | |
g.addVertex(A); | |
g.addVertex(B); | |
g.addVertex(C); | |
g.addVertex(D); | |
g.addVertex(E); | |
g.addVertex(F); | |
g.addEdge(A, B); | |
g.addEdge(A, C); | |
g.addEdge(B, D); | |
g.addEdge(C, D); | |
g.addEdge(D, E); | |
g.addEdge(E, F); | |
// 显示图 | |
System.out.println("Graph:"); | |
g.displayGraph(); | |
// 遍历图(深度优先搜索) | |
System.out.println("\nDFS from A:"); | |
g.dfs(A); | |
// 遍历图(广度优先搜索) | |
System.out.println("\nBFS from A:"); | |
g.bfs(A); | |
// 清空图 | |
g.clearGraph(); | |
// 显示图(应为空) | |
System.out.println("\nGraph after clearing:"); | |
g.displayGraph(); | |
} | |
} |
注意,在上面的示例中,我们使用了hashCode()
方法和数组来跟踪顶点是否已经被访问过,这可能在某些情况下(例如,当多个不同对象具有相同的哈希码时)导致问题。为了避免这种情况,我们可以使用一个HashSet
来跟踪访问过的顶点,因为HashSet
直接依赖于对象的equals()
和hashCode()
方法,但它在添加元素时会检查元素是否已存在。
然而,在DFS的实现中,如果我们使用HashSet
来跟踪访问过的顶点,我们就不需要为整个图预先分配一个布尔数组。
另外,如果图可能非常大,我们不能预先假设一个固定大小的布尔数组来跟踪访问过的顶点。下面是一个改进的DFS实现,它使用HashSet
来跟踪访问过的顶点:
// ... 省略其他部分 ... | |
// 深度优先搜索 | |
void dfs(Vertex startVertex) { | |
Set<Vertex> visited = new HashSet<>(); | |
Stack<Vertex> stack = new Stack<>(); | |
stack.push(startVertex); | |
while (!stack.isEmpty()) { | |
Vertex v = stack.pop(); | |
if (!visited.contains(v)) { | |
visited.add(v); | |
System.out.print(v + " "); | |
for (Vertex neighbor : adjList.get(v)) { | |
if (!visited.contains(neighbor)) { | |
stack.push(neighbor); | |
} | |
} | |
} | |
} | |
} | |
// ... 省略其他部分 ... |
在这个改进的实现中,我们使用了一个Stack
来模拟深度优先搜索的递归过程,同时用一个HashSet
来跟踪访问过的顶点。当遍历到新的邻居时,如果它还没有被访问过,我们就将其添加到栈中以便后续处理。
这个实现更加健壮,因为它不依赖于图的顶点数量,并且不依赖于顶点的hashCode()
方法的实现。它可以处理任意大小的图和具有任意hashCode()
方法的顶点。