有向图的邻接矩阵：不对称特性与度的计算

"本资源主要讨论了有向图的邻接矩阵表示，强调了邻接矩阵可能不对称的特性，并提供了具体的例子进行解释。同时，提到了顶点的入度、出度和度的概念，以及图的存储结构、遍历方法和相关应用。" 在数据结构中，图是一种复杂的数据结构，用于表示对象之间的多对多关系。图由顶点（Vertex）和边（Edge）组成，其中顶点代表数据元素，边则连接这些元素。图可以是有向的，也可以是无向的。本资源重点探讨的是有向图。 有向图的邻接矩阵是一个二维数组，用来表示图中顶点之间的连接关系。对于有向图，邻接矩阵可能不是对称的，因为每个边都有明确的方向，即从一个顶点指向另一个顶点。例如，如果存在一条从顶点v1到顶点v2的边，那么邻接矩阵中的元素A[v1][v2]为1，但A[v2][v1]可能为0，这体现了邻接矩阵的不对称性。 顶点的出度是指从该顶点出发的边的数量，也就是邻接矩阵中对应行的非零元素之和。相反，顶点的入度则是指到达该顶点的边的数量，即邻接矩阵中对应列的非零元素之和。顶点的度是其出度与入度之和，表示与该顶点关联的边的总数。 例如，给定的邻接矩阵表示如下： ``` A = [ [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1], [1, 0, 0, 0] ] ``` 在这个矩阵中，顶点v1的出度是0，入度也是0，因此度为0；顶点v2的出度和入度都是0，度为0；顶点v3的出度是0，入度是1，度为1；顶点v4的出度是1，入度是0，度为1。 图的存储结构除了邻接矩阵，还有邻接表，它使用链表来存储每个顶点的邻接点，对于稀疏图（边数远小于顶点数的平方）更为高效。图的遍历方法主要包括深度优先搜索（DFS）和广度优先搜索（BFS），它们分别按照不同的顺序访问图中的顶点。 教学内容涵盖图的基本概念、图的存储表示（邻接矩阵和邻接表）、图的遍历（DFS和BFS）以及特定的图算法，如最短路径问题的Dijkstra算法、最小生成树的构造（如Prim和Kruskal算法）以及拓扑排序等。这些知识在计算机科学中有着广泛的应用，如网络路由、任务调度和社交网络分析等。