Java数据结构与算法：有向图和无向图

什么是图？

在计算机科学中，图是一种非常重要且广泛应用的数据结构，用于表示对象之间的关系。图由节点（顶点）和边组成，边表示节点之间的连接关系。

有向图和无向图

图可以分为有向图和无向图两种基本类型。

1. 有向图

有向图中的边有方向，即从一个节点指向另一个节点的关系。有向图表示一种单向的关系，如A指向B。

2. 无向图

无向图中的边没有方向，即连接两个节点的关系是双向的。无向图表示一种双向的关系，如A和B相互连接。

图的应用场景

图的应用非常广泛，例如：

1. 社交网络关系： 用图表示社交网络中用户之间的关系。
2. 路线规划： 用图表示城市之间的道路和交通规划。
3. 网页链接关系： 用图表示网页之间的链接关系，搜索引擎的排名算法中经常使用图。
4. 编译器中的依赖关系： 用图表示源代码文件之间的依赖关系。

Java中的图表示

在Java中，可以使用邻接矩阵或邻接表来表示图。邻接矩阵适用于稠密图，而邻接表适用于稀疏图。

// 以邻接表表示的有向图
public class Graph {
    private int V; // 节点数
    private LinkedList<Integer>[] adjList; // 邻接表

    public Graph(int v) {
        V = v;
        adjList = new LinkedList[v];
        for (int i = 0; i < v; ++i)
            adjList[i] = new LinkedList<>();
    }

    // 添加边
    public void addEdge(int v, int w) {
        adjList[v].add(w);
    }
}

有向图和无向图的区别

在实际应用中，有向图和无向图的选择取决于问题的特性。有向图更适合表示单向关系，而无向图更适合表示双向关系。在设计和解决问题时，选择合适的图类型非常重要。

希望通过这篇文章，大家对有向图和无向图有了初步的了解。在后续的文章中，我们将深入讨论图的遍历、最短路径等算法。