图及其应用实验报告数据结构

实验目的

1. 理解图的基本概念及其常见表示方法。
2. 掌握图的遍历方法，如深度优先遍历(DFS)与广度优先遍历(BFS)。
3. 理解图的常见应用，如最短路径问题、拓扑排序等。

实验内容

1. 图的基本概念

图是一种由节点（或称为顶点）和边组成的非线性数据结构。图可以表示许多实际问题，如社交网络中的关系、地图中的路线等。

• 无向图：图中的边没有方向，表示两个节点之间的双向关系。
• 有向图：图中的边有方向，表示一个节点到另一个节点的单向关系。
• 加权图：图中的每条边都有一个权重，表示从一个节点到另一个节点的代价或距离。
• 无权图：图中的边没有权重，表示节点之间的关系是等价的。

2. 图的存储方式

图的常见存储方式有两种：

邻接矩阵

邻接矩阵是一个二维数组，其中matrix[i][j]表示从顶点i到顶点j的边。如果存在边，则值为该边的权重；如果不存在边，则值为无穷大或0（对于无向图）。

优点：适合稠密图。 缺点：空间复杂度高，不适合稀疏图。

邻接表

邻接表是一个数组，每个数组元素存储与该顶点相邻的所有顶点的列表。在加权图中，边的权重也可以存储在该列表中。

优点：空间复杂度较低，适合稀疏图。 缺点：访问某一特定边时，速度较慢。

3. 图的遍历

深度优先遍历（DFS）

深度优先遍历是一种从根节点开始，沿着图的每条分支深入到不可再深入的节点，再回溯并继续访问其他分支的算法。DFS可以通过递归或栈来实现。

DFS算法伪代码： python def DFS(graph, node, visited): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: DFS(graph, neighbor, visited)

广度优先遍历（BFS）

广度优先遍历是一种从根节点开始，访问所有邻居节点，然后依次访问这些邻居的邻居节点，直到所有节点都被访问到。BFS通常使用队列来实现。

BFS算法伪代码： ```python from collections import deque

def BFS(graph, start): visited = set() queue = deque([start]) visited.add(start)

while queue:
    node = queue.popleft()
    print(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

```

4. 图的应用

最短路径问题

图的最短路径问题是计算从源节点到目标节点的最短路径。在加权图中，常用的算法有Dijkstra算法和Bellman-Ford算法。

• Dijkstra算法：适用于没有负权边的加权图，通过贪心策略逐步计算最短路径。
• Bellman-Ford算法：适用于有负权边的图，能够处理负权环。

拓扑排序

拓扑排序是对有向无环图（DAG）的一种线性排序，使得对于图中的每条边(u, v)，顶点u在v之前。拓扑排序广泛应用于任务调度、课程安排等问题。

拓扑排序的实现： 1. 计算每个节点的入度。 2. 将入度为0的节点加入队列。 3. 逐个删除入度为0的节点，并更新相邻节点的入度，直到所有节点都被处理。

网络流问题

图论中的网络流问题涉及在图的节点之间流动物资、信息等。常见的算法有最大流算法和最小割问题。

• Ford-Fulkerson算法：用于求解最大流问题，基于增广路径的思想。
• Edmonds-Karp算法：Ford-Fulkerson算法的实现，使用BFS寻找增广路径。

实验结果与分析

通过本次实验，使用邻接矩阵和邻接表两种方式实现了图的存储，并通过DFS和BFS两种遍历方式对图进行访问。在最短路径问题中，Dijkstra算法能够有效解决没有负权边的图，而Bellman-Ford算法则适用于处理有负权边的情况。

在拓扑排序的实验中，我们使用了入度表来实现了对DAG图的排序，解决了任务调度中的依赖关系问题。

实验总结

图作为一种重要的数据结构，广泛应用于计算机科学的各个领域。通过本次实验，我们深入理解了图的表示方法、遍历算法及其应用。对于实际问题的解决，图提供了一个强大的工具，能够有效地建模和求解各种复杂问题。