有向图和无向图有何不同？

有向图和无向图是图论中的两种基本类型，它们在结构、表示和应用上都有显著的不同。

定义

• 无向图：在无向图中，每条边没有方向，意味着如果顶点A和顶点B之间有一条边，那么这条边既可以表示从A到B，也可以表示从B到A。无向图用数学符号表示为 (G = (V, E))，其中V是顶点的集合，E是边的集合。
• 有向图：在有向图中，每条边有明确的方向，意味着如果顶点A和顶点B之间有一条边，这条边只能表示从A到B，而不能表示从B到A。有向图同样用数学符号表示为 (D = (V, E))，其中V是顶点的集合，E是边的集合，但这里的每条边都有方向。

结构特点

• 无向图：无向图的边是没有方向的，因此在无向图中，顶点之间的连接是相互的。例如，在无向图中，顶点A和顶点B之间的边表示它们之间可以直接通信或相互到达。
• 有向图：有向图的边是有方向的，因此在有向图中，顶点之间的连接不是相互的。例如，在有向图中，从顶点A到顶点B的边表示顶点A可以到达顶点B，但顶点B不一定可以到达顶点A。

应用领域

• 无向图：无向图通常用于表示没有特定方向的连接关系，如社交网络中的好友关系、无向的公路网络等。
• 有向图：有向图通常用于表示有明确方向的关系，如网页的链接结构（在搜索引擎中用于页面排名）、交通网络中的路线图等。

算法处理

• 无向图：在无向图中，算法通常关注的是顶点之间的连通性，如寻找无向图中的连通分量、最小生成树等。
• 有向图：在有向图中，算法通常关注的是顶点之间的可达性，如拓扑排序、强连通分量等。

示例

• 无向图示例：在一个无向图中，如果顶点A、B和C之间都有边相连，那么这三个顶点形成一个完全连接的子图，即每两个顶点之间都有边。
• 有向图示例：在一个有向图中，如果从顶点A到顶点B有一条边，但从顶点B到顶点A没有边，那么顶点A可以到达顶点B，但顶点B不能到达顶点A。