3.3.2 图

2025-07-30 22:58:27 更新

阅读(486)
收藏
赞(0)

图是比树结构更复杂的一种数据结构，被用于描述各种复杂的数据对象。

图结构中，任意两个结点之间都可能有直接关系。

（一）图的概念

在图中，数据元素用顶点表示，数据元素之间的关系用边表示。

	概念	描述
1	有向图	图中每条边都有方向。有向边也称为弧，起点为弧尾，终点为弧头。
2	无向图	图中每条边都没有方向。
3	完全图（无向完全图）	具有n个顶点的无向图，每个顶点与其他n-1个顶点之间都有边。
4	度	度是关联于顶点的边的数目（含入度和出度）
5	入度	以顶点为终点的有向边数目。
6	出度	以顶点为起点的有向边数目。
7	路径	在无向图中，路径长度是路径上边或孤的数目。
8	回路（环）	第一个顶点和最后一个顶点相同的路径。
9	简单路径	除了起顶点和终顶点可以相同外，其余顶点均不相同的路径。
10	子图	图A的顶点和边构成的集合都是图B对应顶点和边的子集。
11	连通图	无向图中任意两个顶点都是连通的。
12	强连通图	有向图中，每一对顶点之间都存在路径。
13	网	边（或孤）具有权值的图。

（二）图的存储结构

存储结构

描述

1

邻接矩阵

利用一个矩阵来表示图中顶点之间的关系。

结论：无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。

2

邻接表

为图的每个顶点建立一个单链表。