1、数据结构（数据结构（C版）版）清华大学出版社清华大学出版社第七章第七章 图图本章的主要内容是本章的主要内容是:图的逻辑结构图的逻辑结构图的存储结构及实现图的存储结构及实现图的遍历图的遍历图的连通性与最小生成树图的连通性与最小生成树拓扑排序拓扑排序关键路径关键路径 最短路径最短路径数据结构（数据结构（C版）版）清华大学出版社清华大学出版社欧拉欧拉17071707年出生在瑞士的巴塞尔城，年出生在瑞士的巴塞尔城，1919岁开始发岁开始发表论文，直到表论文，直到7676岁。几乎每一个数学领域都可以岁。几乎每一个数学领域都可以看到欧拉的名字，从初等几何的欧拉线，多面体看到欧拉的名字，从初等几何的欧拉线，
2、多面体的欧拉定理，立体解析几何的欧拉变换公式，四的欧拉定理，立体解析几何的欧拉变换公式，四次方程的欧拉解法到数论中的欧拉函数，微分方次方程的欧拉解法到数论中的欧拉函数，微分方程的欧拉方程，级数论的欧拉常数，变分学的欧程的欧拉方程，级数论的欧拉常数，变分学的欧拉方程，复变函数的欧拉公式等等。据统计他那拉方程，复变函数的欧拉公式等等。据统计他那不倦的一生，共写下了不倦的一生，共写下了886886本书籍和论文，其中本书籍和论文，其中分析、代数、数论占分析、代数、数论占40%40%，几何占，几何占18%18%，物理和，物理和力学占力学占28%28%，天文学占，天文学占11%11%，弹道学、航海学、，弹
3、道学、航海学、建筑学等占建筑学等占3%3%。1733 1733年，年仅年，年仅2626岁的欧拉担任岁的欧拉担任了彼得堡科学院数学教授。了彼得堡科学院数学教授。17411741年到柏林担任科年到柏林担任科学院物理数学所所长，直到学院物理数学所所长，直到17661766年，重回彼得堡，年，重回彼得堡，没有多久，完全失明。欧拉在数学上的建树很多，没有多久，完全失明。欧拉在数学上的建树很多，对著名的哥尼斯堡七桥问题的解答开创了图论的对著名的哥尼斯堡七桥问题的解答开创了图论的研究。研究。图论图论欧拉欧拉数据结构（数据结构（C版）版）清华大学出版社清华大学出版社能否从某个地方出发，穿过所有的桥仅一次能否从
4、某个地方出发，穿过所有的桥仅一次后再回到出发点？后再回到出发点？哥尼斯堡七桥问题哥尼斯堡七桥问题 数据结构（数据结构（C版）版）清华大学出版社清华大学出版社CADB七桥问题的图模型七桥问题的图模型哥尼斯堡七桥问题哥尼斯堡七桥问题 欧拉回路的判定规则：欧拉回路的判定规则：1.如果通奇数桥的地方多于如果通奇数桥的地方多于两个，则不存在欧拉回路；两个，则不存在欧拉回路；2.如果只有两个地方通奇数如果只有两个地方通奇数桥，可以从这两个地方之一桥，可以从这两个地方之一出发，找到欧拉回路；出发，找到欧拉回路；3.如果没有一个地方是通奇如果没有一个地方是通奇数桥的，则无论从哪里出发，数桥的，则无论从哪里出发
5、，都能找到欧拉回路。都能找到欧拉回路。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的定义图的定义7.1 图的逻辑结构图的逻辑结构图是一种数据结构。由图是一种数据结构。由顶点顶点的的有穷非空有穷非空集合和顶点集合和顶点之间之间关系关系的集合组成，通常表示为：的集合组成，通常表示为：G=(V，E)其中：其中：G表示一个图，表示一个图，V是具有相同特性的数据元是具有相同特性的数据元素的集合，称为顶点集；素的集合，称为顶点集；E是图是图G中顶点之间关系中顶点之间关系的集合，成为边集或弧集。的集合，成为边集或弧集。E|v,wV 且且 P(v,w)或或(v,w)|v,wV 且且 P(v,w
6、)表示从表示从 v 到到 w 的一条弧，称的一条弧，称 v 为弧头，为弧头，w 为弧尾。为弧尾。(v,w)表示表示v与与w之间的一条边。之间的一条边。谓词谓词 P(v,w)定义了弧定义了弧 或边或边(v,w)的意义或信息。的意义或信息。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.1 图的逻辑结构图的逻辑结构如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是无向边，则称该图为无向边，则称该图为无向图无向图。若顶点若顶点vi和和vj之间的边没有方向，则之间的边没有方向，则称这条边为称这条边为无向边无向边，表示为，表示为(vi,vj)。若从顶点若从顶点vi到到vj的边
7、有方向，则称这的边有方向，则称这条边为条边为有向边有向边，表示为，表示为。如果图的任意两个顶点之间的边都如果图的任意两个顶点之间的边都是是有向边，则称该图为有向边，则称该图为有向图有向图。V1V2V3V4V5V1V2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 简单图：简单图：在图中，若不存在顶点到其自身的边，且同在图中，若不存在顶点到其自身的边，且同一条边不重复出现一条边不重复出现。V3V4V5V1V2V3V4V5V1V2非简单图非简单图 非简单图非简单图 简单图简单图V1V2V3V4V5v 数据结构中讨论的都是简
8、单图。数据结构中讨论的都是简单图。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 邻接、依附邻接、依附无向图无向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在边若存在边(vi，vj)，则称顶点，则称顶点vi和顶点和顶点vj互为互为邻接点邻接点，同时称边，同时称边(vi，vj)依附依附于顶点于顶点vi和顶点和顶点vj。V1V2V3V4V5V1的邻接点：的邻接点：V2、V4V2的邻接点：的邻接点：V1、V3、V5数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.1 图的逻辑结构图的逻辑结构图的基
9、本术语图的基本术语 邻接、依附邻接、依附有向图有向图中，对于任意两个顶点中，对于任意两个顶点vi和顶点和顶点vj，若存在弧若存在弧，则称顶点则称顶点vi邻接到顶点邻接到顶点vj，顶点顶点vj邻接自顶邻接自顶点点vi，同时称弧同时称弧依附于顶点依附于顶点vi和顶点和顶点vj。V1V2V3V4V1的邻接点：的邻接点：V2、V3V3的邻接点：的邻接点：V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在线性结构中，数据元素之间仅具有线性关系；在线性结构中，数据元素之间仅具有线性关系；在树结构中，结点之间具有层次关系；在树结构中，结点之间具有层次关系；在图结构中，任意两个顶点之间都可能有关
10、系。在图结构中，任意两个顶点之间都可能有关系。FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比数据结构（数据结构（C版）版）清华大学出版社清华大学出版社在线性结构中，元素之间的关系为在线性结构中，元素之间的关系为前驱前驱和和后继后继；在树结构中，结点之间的关系为在树结构中，结点之间的关系为双亲双亲和和孩子孩子；在图结构中，顶点之间的关系为在图结构中，顶点之间的关系为邻接邻接。FECBAD线性结构线性结构ABCDEF树结构树结构V1V2V3V4V5图结构图结构不同结构中逻辑关系的对比不同结构中逻辑关系的对比数据结
11、构（数据结构（C版）版）清华大学出版社清华大学出版社无向完全图无向完全图：在无向图中，如果任意两个顶点之间：在无向图中，如果任意两个顶点之间都存在边，都存在边，则称该图为无向完全图。则称该图为无向完全图。有向完全图有向完全图：在有向图中，如果任意两个顶点之间：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，都存在方向相反的两条弧，则称该图为有向完全图则称该图为有向完全图。图的基本术语图的基本术语 V1V2V3V1V2V3V47.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社含有含有n个顶点的无向完全图有个顶点的无向完全图有多少多少条边？条边？含有
12、含有n个顶点的有向完全图有个顶点的有向完全图有多少多少条弧？条弧？7.1 图的逻辑结构图的逻辑结构含有含有n个顶点的无向完全图有个顶点的无向完全图有n(n-1)/2条边。条边。含有含有n个顶点的有向完全图有个顶点的有向完全图有n(n-1)条边。条边。V1V2V3V1V2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社稀疏图：稀疏图：称边数很少的图为稀疏图（称边数很少的图为稀疏图（enlogn）；）；稠密图：稠密图：称边数很多的图为稠密图（称边数很多的图为稠密图（enlogn）。顶点的度：顶点的度：在无向图中，顶点在无向图中，顶点v的的度度是指依附于该顶是指依附于该顶点的边数，
13、通常记为点的边数，通常记为TD(v)。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 顶点的入度：顶点的入度：在有向图中，顶点在有向图中，顶点v的的入度入度是指以该顶是指以该顶点为弧头的弧的数目，点为弧头的弧的数目，记为记为ID(v)；顶点顶点的的出度：出度：在有向图中，顶点在有向图中，顶点v的的出度出度是指以该顶是指以该顶点为弧尾的弧的数目，记为点为弧尾的弧的数目，记为OD(v)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社V1V2V3V4V57.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 在具有在具有n个顶点、个顶点、e条边的无向图条边的无向图G中，各顶点
14、中，各顶点的度之和与边数之和的关系？的度之和与边数之和的关系？=niievTD12)(数据结构（数据结构（C版）版）清华大学出版社清华大学出版社V1V2V3V47.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 在具有在具有n个顶点、个顶点、e条边的有向图条边的有向图G中，各顶点中，各顶点的入度之和与各顶点的出度之和的关系？与边的入度之和与各顶点的出度之和的关系？与边数之和的关系？数之和的关系？evODvIDiiii=11)()(nn数据结构（数据结构（C版）版）清华大学出版社清华大学出版社权：权：是指对边赋予的有意义的数值量。是指对边赋予的有意义的数值量。网：网：边上带权的图，也称网图
15、。边上带权的图，也称网图。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V42785数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径：路径：在无向图在无向图G=(V,E)中，从顶点中，从顶点vp到顶点到顶点vq之间的之间的路径路径是一个顶点序列是一个顶点序列(vp=vi0,vi1,vi2,vim=vq)，其中，其中，(vij-1,vij)E（1jm）。）。若若G是有向图，则路径也是有是有向图，则路径也是有方向的，顶点序列满足方向的，顶点序列满足E。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4V5v一般情况下，图中的路径不惟一。
16、一般情况下，图中的路径不惟一。V1 到到V4的路径：的路径：V1 V4 V1 V2 V3 V4 V1 V2 V5V3 V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径长度：路径长度：7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1V2V3V4V5V1 V4：长度为：长度为1V1 V2 V3 V4：长度为：长度为3V1 V2 V5V3 V4：长度为：长度为4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社路径长度：路径长度：7.1 图的逻辑结构图的逻辑结构图的基本
17、术语图的基本术语 非带权图非带权图路径路径上边的上边的个数个数带权图带权图路径上路径上各边的各边的权之和权之和V1 V4：长度为：长度为8V1 V2 V3 V4：长度为：长度为7V1 V2 V5V3 V4：长度为：长度为15V1V2V3V4V5256328数据结构（数据结构（C版）版）清华大学出版社清华大学出版社回路（环）回路（环）：第一个顶点和最后一个顶点相同的路径。：第一个顶点和最后一个顶点相同的路径。简单路径：简单路径：序列中顶点不重复出现的路径。序列中顶点不重复出现的路径。简单回路（简单环）：简单回路（简单环）：除了第一个顶点和最后一个顶点除了第一个顶点和最后一个顶点外，其余顶点不重复
18、出现的回路。外，其余顶点不重复出现的回路。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4V5V1V2V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社子图：子图：若图若图G=（V，E），），G=（V，E），），如果如果V V 且且E E，则称图则称图G是是G的子图。的子图。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4V5V1V2V3V4V5V1V3V4数据结构（数据结构（C版）版）清华大学出版社清华大学出版社连通图：连通图：在无向图中，如果从一个顶点在无向图中，如果从一个顶点vi到另一个顶到另一个顶点点vj(ij)有路径
19、，则称顶点有路径，则称顶点vi和和vj是连通的。如果图中是连通的。如果图中任意两个顶点都是连通的，则称该图是连通任意两个顶点都是连通的，则称该图是连通图。图。连通分量：连通分量：非连通图的极大连通子图称为连通分量。非连通图的极大连通子图称为连通分量。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 如何求得一个非连通图的连通分量如何求得一个非连通图的连通分量?1.含有极大含有极大顶点顶点数；数；2.依附于这些顶点的所有依附于这些顶点的所有边边。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社连通分量连通分量1 7.1 图的逻辑结构图的逻辑结构V1V2V3V4V5V6V7V1V
20、2V4V5V3V6V7连通分量连通分量2图的基本术语图的基本术语 v连通分量是对无向图的一种划分。连通分量是对无向图的一种划分。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社强连通图：强连通图：在有向图中，对图中任意一对顶点在有向图中，对图中任意一对顶点vi和和vj(ij)，若从顶点若从顶点vi到顶点到顶点vj和从顶点和从顶点vj到顶点到顶点vi均有路径均有路径，则称该有向图是强连通图。，则称该有向图是强连通图。强连通分量：强连通分量：非强连通图非强连通图的极大强连通子图。的极大强连通子图。7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 如何求得一个非连通图的连通分量如何
21、求得一个非连通图的连通分量?数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 V1V2V3V4强连通分量强连通分量1 强连通分量强连通分量2V1V3V4V2数据结构（数据结构（C版）版）清华大学出版社清华大学出版社生成树：生成树：n个顶点的连通图个顶点的连通图G的生成树是包含的生成树是包含G中中全全部顶点部顶点的一个极小连通的一个极小连通子图。（子图。（n n个顶点的数至少有个顶点的数至少有n-1n-1条边）条边）生成森林：生成森林：在非连通图中，由每个连通分量都可以得在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分
22、到一棵生成树，这些连通分量的生成树就组成了一个量的生成树就组成了一个非连通图的非连通图的生成森林生成森林。如何理解极小连通子图如何理解极小连通子图?7.1 图的逻辑结构图的逻辑结构图的基本术语图的基本术语 多了多了构成回路构成回路少了少了不连通不连通含有含有n-1条边条边数据结构（数据结构（C版）版）清华大学出版社清华大学出版社V1V2V3V4V5V6V7V1V2V3V4V5V6V7V1V2V3V4V5V1V2V3V4V5生成树生成树生成森林生成森林7.1 图的逻辑结构图的逻辑结构数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的抽象数据类型定义图的抽象数据类型定义 7.1 图的逻
23、辑结构图的逻辑结构ADT GraphADT Graph数据对象数据对象V V；V V是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R:R=ER:R=E（弧集或边集）（弧集或边集）基本操作基本操作P P：构造、销毁、顶点操作、弧操作、遍历等：构造、销毁、顶点操作、弧操作、遍历等CreatGraph(&GCreatGraph(&G,V,E)/,V,E)/按定义按定义(V,E)(V,E)构造图构造图DestroyGraph(&GDestroyGraph(&G)/)/销毁图销毁图LocateVex(GLocateVex(G,u)/,u)/若若G G中存在顶点中存在顶点
24、u u，则返回该顶点在，则返回该顶点在图中图中“位置位置”；否则返回其它信息。；否则返回其它信息。GetVex(GGetVex(G,v)/,v)/返回返回 v v 的值。的值。PutVex(&GPutVex(&G,v,value)/,v,value)/对对 v v 赋值赋值valuevalue。FirstAdjVex(GFirstAdjVex(G,v)/,v)/返回返回 v v 的的“第一个邻接点第一个邻接点”。若。若该顶点在该顶点在 G G 中没有邻接点，则返回中没有邻接点，则返回“空空”。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社图的抽象数据类型定义图的抽象数据类型定义 7
25、.1 图的逻辑结构图的逻辑结构NextAdjVex(G,v,w);/返回返回 v 的的(相对于相对于 w 的的)“下一个邻接下一个邻接 /点点”。若若 w 是是 v 的最后一个邻接点，则返回的最后一个邻接点，则返回“空空”。InsertVex(&G,v);/在图在图 G中增添新顶点中增添新顶点v。DeleteVex(&G,v);/删除删除G中顶点中顶点v及其相关的弧。及其相关的弧。InsertArc(&G,v,w);/在在G中增添弧中增添弧，若，若G是无向的，是无向的，/则还增添对称弧则还增添对称弧。DeleteArc(&G,v,w);/在在G中删除弧中删除弧，若，若G是无向的，是无向的，/则
26、还删除对称弧则还删除对称弧。DFSTraverse(G,v,Visit();/从顶点从顶点v起起深度优先深度优先遍历图遍历图G，并，并 /对每个顶点调用函数对每个顶点调用函数Visit一次且仅一次。一次且仅一次。BFSTraverse(G,v,Visit();/从顶点从顶点v起起广度优先广度优先遍历图遍历图G，并，并 /对每个顶点调用函数对每个顶点调用函数Visit一次且仅一次。一次且仅一次。ADT Graph数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现是否可以采用顺序存储结构存储图是否可以采用顺序存储结构存储图?图的特点：顶点之间的关
27、系是图的特点：顶点之间的关系是m:n，即，即任何两任何两个顶点之间都可能存在关系（边或弧），无法个顶点之间都可能存在关系（边或弧），无法通过存储位置表示这种任意的逻辑关系，所以，通过存储位置表示这种任意的逻辑关系，所以，图无法采用顺序存储结构。图无法采用顺序存储结构。如何存储图如何存储图?考虑图的定义，图是由顶点和边组成的，分别考虑图的定义，图是由顶点和边组成的，分别考虑如何存储顶点、如何存储边。考虑如何存储顶点、如何存储边。线性表、二叉树都可以两种不同的存储结构线性表、二叉树都可以两种不同的存储结构-顺序和链式存储结构来存储。顺序和链式存储结构来存储。数据结构（数据结构（C版）版）清华大学出
28、版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现如何设计图的顶点结构和边结构呢？如何设计图的顶点结构和边结构呢？如果按照度数最大的结点设计结点存储结构，浪如果按照度数最大的结点设计结点存储结构，浪费；若按照各自的度数设计又会造成操作的不便。费；若按照各自的度数设计又会造成操作的不便。下面我们介绍的四种存储表示法将分别对图中的下面我们介绍的四种存储表示法将分别对图中的顶点结构和弧（边）结构分别进行设计。顶点结构和弧（边）结构分别进行设计。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社一、邻接矩阵（数组表示法）一、邻接矩阵（数组表示法）基本思想：用一个一维数组存储图中基本
29、思想：用一个一维数组存储图中顶点顶点的信息，的信息，用一个二维数组（用一个二维数组（称为邻接矩阵称为邻接矩阵）存储图中各顶点）存储图中各顶点之间的之间的邻接邻接关系。关系。7.2 图的存储结构及实现图的存储结构及实现假设图假设图G(V，E)有有n个顶点，则邻接矩阵是一个个顶点，则邻接矩阵是一个nn的方阵，定义为：的方阵，定义为：arcij1 若若(vi,vj)E（或（或E）0 其它其它数据结构（数据结构（C版）版）清华大学出版社清华大学出版社无向图的邻接矩阵的特点？无向图的邻接矩阵的特点？无向图的邻接矩阵无向图的邻接矩阵7.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V
30、3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4主对角线为主对角线为 0 且一定是对称矩阵。且一定是对称矩阵。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何求顶点如何求顶点i的度？的度？无向图的邻接矩阵无向图的邻接矩阵7.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4邻接矩阵的第邻接矩阵的第i行（或第行（或第i列）非零元素的个数。列）非零元素
31、的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断顶点如何判断顶点 i 和和 j 之间是否存在边？之间是否存在边？无向图的邻接矩阵无向图的邻接矩阵7.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？无向图的邻接矩阵无向图的邻接矩
32、阵7.2 图的存储结构及实现图的存储结构及实现V1V3V4V2V1 V2 V3 V4vertex=0 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 arc=V1 V2 V3 V4V1V2V3V4将数组中第将数组中第 i 行元素扫描一遍，若行元素扫描一遍，若arcij为为1，则，则顶点顶点 j 为顶点为顶点 i 的邻接点。的邻接点。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 ar
33、c=V1 V2 V3 V4V1V2V3V4有向图的邻接矩阵一定不对称吗？有向图的邻接矩阵一定不对称吗？不一定，例如有向完全图。不一定，例如有向完全图。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的出度？的出度？邻接矩阵的第邻接矩阵的第 i 行元素之和。行元素之和。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社
34、7.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V2 V3 V4V1V2V3V4如何求顶点如何求顶点 i 的入度？的入度？邻接矩阵的第邻接矩阵的第 i 列元素之和。列元素之和。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现有向图的邻接矩阵有向图的邻接矩阵V1V2V3V4V1 V2 V3 V4vertex=0 1 1 0 0 0 0 0 0 0 0 1 1 0 0 0 arc=V1 V
35、2 V3 V4V1V2V3V4如何判断从顶点如何判断从顶点 i 到顶点到顶点 j 是否存在弧？是否存在弧？测试邻接矩阵中相应位置的元素测试邻接矩阵中相应位置的元素arcij是否为是否为1。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社网图的邻接矩阵网图的邻接矩阵7.2 图的存储结构及实现图的存储结构及实现网图的邻接矩阵可定义为：网图的邻接矩阵可定义为：arcij wij 若若(vi,vj)E（或（或E）0 若若i=j 其他其他V1V2V3V42785 0 2 5 0 0 8 7 0 arc=数据结构（数据结构（C版）版）清华大学出版社清华大学出版社typedef struct Ar
36、cCell /弧的定义弧的定义 VRType adj;/VRType是顶点关系类型。是顶点关系类型。/对无权图，用对无权图，用1或或0表示相邻否；表示相邻否；/对带权图，则为权值类型。对带权图，则为权值类型。Info *info；/该弧相关信息的指针该弧相关信息的指针 AdjMatrixN N;/这里假设这里假设N为最大顶点个数为最大顶点个数7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 Status CreateGraph(MGraph&G)/算法算法7.1 /采用数组采用数组(邻接矩阵邻接矩阵)表示法，构造图表示法，构造图G。scan
37、f(&G.kind);/自定义输入函数，读入一个随机值自定义输入函数，读入一个随机值 switch(G.kind)case DG:return CreateDG(G);/构造有向图构造有向图G case DN:return CreateDN(G);/构造有向网构造有向网G case UDG:return CreateUDG(G);/构造无向图构造无向图G case UDN:return CreateUDN(G);/构造无向网构造无向网G，算法，算法7.2 default:return ERROR;/CreateGraph7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）
38、清华大学出版社清华大学出版社邻接矩阵中图的基本操作邻接矩阵中图的基本操作构造函数构造函数 1.确定图的顶点个数和边的个数；确定图的顶点个数和边的个数；2.输入顶点信息，构造顶点向量输入顶点信息，构造顶点向量vertexvexnum；3.初始化邻接矩阵；初始化邻接矩阵；4.依次输入每条边存储在邻接矩阵依次输入每条边存储在邻接矩阵arc中；中；4.1 确定确定边依附的两个顶点的序号边依附的两个顶点的序号i,j；4.2 将邻接矩阵的第将邻接矩阵的第i行第行第j列置为列置为边的权值边的权值w；4.3 将邻接矩阵的第将邻接矩阵的第j行第行第i列置为边的权值列置为边的权值w；7.2 图的存储结构及实现图的
39、存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Status CreateUDN(MGraph&G)/算法算法7.2 /采用数组（邻接矩阵）表示法，构造无向网采用数组（邻接矩阵）表示法，构造无向网G。int i,j,k,w;VertexType v1,v2;printf(G.vexnum:);scanf(%d,&G.vexnum);/输入顶点个数输入顶点个数 printf(“G.arcnum:”);scanf(“%d”,&G.arcnum);/输入弧的个数输入弧的个数 for(i=0;iG.vexnum;+i)printf(G.vertex%d:,i);scanf(%c
40、,&G.vertexi);/构造顶点向量构造顶点向量 for(i=0;iG.vexnum;+i)/初始化邻接矩阵初始化邻接矩阵 for(j=0;jG.vexnum;+j)G.arcsij.adj=INFINITY;/adj,info G.arcsij.info=NULL;7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社 for(k=0;kG.arcnum;+k)/构造邻接矩阵构造邻接矩阵 printf(v1(char):);scanf(%c,&v1);getchar();printf(v2(char):);scanf(%c,&v2);get
41、char();printf(w(int):);scanf(%d,&w);getchar();/输入一条边依附的顶点及权值输入一条边依附的顶点及权值 i=LocateVex(G,v1);j=LocateVex(G,v2);/确定确定v1和和v2在在G中位置中位置 G.arcsij.adj=w;/弧弧的权值的权值 /if(IncInfo)scanf(G.arcsij.info);/输入弧含有相输入弧含有相关信息关信息 G.arcsji.adj=G.arcsij.adj;/置置的对称的对称弧弧 return OK;/CreateUDN7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C
42、版）版）清华大学出版社清华大学出版社二、邻接表二、邻接表邻接表存储的基本思想：对于图的每个顶点邻接表存储的基本思想：对于图的每个顶点vi，将所将所有邻接于有邻接于vi的顶点链成一个单链表，称为顶点的顶点链成一个单链表，称为顶点vi的的边边表表（对于有向图则称为出边表），所有边表的头指（对于有向图则称为出边表），所有边表的头指针和存储顶点信息的一维针和存储顶点信息的一维数组构成了数组构成了顶点表顶点表。7.2 图的存储结构及实现图的存储结构及实现图的邻接矩阵存储结构的空间复杂度？图的邻接矩阵存储结构的空间复杂度？如果为稀疏图则会出现什么现象？如果为稀疏图则会出现什么现象？假设图假设图G有有n个顶
43、点个顶点e条边，则存储该图需要条边，则存储该图需要O(n2)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻接表有两种结点结构：顶点表结点和边表结点邻接表有两种结点结构：顶点表结点和边表结点。datafirstarc adjvex nextarc头头(顶点顶点)结点结点 表表(边边)结点结点 vertex：数据域，存放顶点信息。数据域，存放顶点信息。firstedge：指针域，指向边表中第一个结点。指针域，指向边表中第一个结点。adjvex：邻接点域，边的终点在顶点表中的下标。邻接点域，边的终点在顶点表中的下标。next：指针域，指向边表中的下一个结点。指针域，指向边表中的下一个
44、结点。7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社Typedef struct ArcNode int adjvex;ArcNode*nextarc;ArcNode;Typedef struct VNode Vertextype data;ArcNode*firstarc;VNode，AdjListN；/N为图的最大顶点数为图的最大顶点数定义邻接表的结点定义邻接表的结点 7.2 图的存储结构及实现图的存储结构及实现data firstarc adjvex nextarc表（边）结点表（边）结点头（顶点）结点头（顶点）结点数据结构（数据结
45、构（C版）版）清华大学出版社清华大学出版社typedef struct AdjList vertices;int vexnum,arcnum;int kind;/图的种类标志 ALGraph;图的结构定义图的结构定义7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社10323101 V1 V2 V3 V40123Data firstarc7.2 图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表无向图的邻接表表（边）结点表示什么？表（边）结点表示什么？每个表（边）结点对应图中的一条边，每个表（边）结点对应图中的一条边，邻接表的
46、空间复杂度为邻接表的空间复杂度为O(n+e)。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社10323101 V1 V2 V3 V40123Data firstarc7.2 图的存储结构及实现图的存储结构及实现V1V3V4V2无向图的邻接表无向图的邻接表如何求顶点如何求顶点 i 的度？的度？顶点顶点i的边链表中结点的个数。的边链表中结点的个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社如何判断顶点如何判断顶点 i 和顶点和顶点 j之间是否存在边之间是否存在边?测试顶点测试顶点 i 的边链表中是否的边链表中是否存在终点为存在终点为 j 的结点。的结点。7.2 图的存储
47、结构及实现图的存储结构及实现10323101 V1 V2 V3 V40123Data firstarcV1V3V4V2无向图的邻接表无向图的邻接表数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123data firstarc如何求顶点如何求顶点 i 的出度？的出度？顶点顶点 i 的出边链表中结点的个数的出边链表中结点的个数数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3
48、V41230 V1 V2 V3 V40123data firstarc如何求顶点如何求顶点 i 的入度？的入度？各顶点的出边链表中以顶点各顶点的出边链表中以顶点 i 为终点的结点个数。为终点的结点个数。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现有向图的逆向邻接表有向图的逆向邻接表V1V2V3V4如何求顶点如何求顶点 i 的入度？的入度？顶点顶点i的入边链表中的结点个数的入边链表中的结点个数3002 V1 V2 V3 V40123data firstarc数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实
49、现图的存储结构及实现有向图的邻接表有向图的邻接表V1V2V3V41230 V1 V2 V3 V40123Data firstarc如何求顶点如何求顶点 i 的所有邻接点？的所有邻接点？遍历顶点遍历顶点 i 的边链表，该边链表中的边链表，该边链表中的所有终点都是顶点的所有终点都是顶点 i 的邻接点。的邻接点。数据结构（数据结构（C版）版）清华大学出版社清华大学出版社7.2 图的存储结构及实现图的存储结构及实现网图的邻接表网图的邻接表V1V2V3V427852 1 V1 V2 V3 V40123Data firstarc5 28 37 0数据结构（数据结构（C版）版）清华大学出版社清华大学出版社邻
50、接表中图的基本操作邻接表中图的基本操作构造函数构造函数 1.确定图的顶点个数和边的个数；确定图的顶点个数和边的个数；2.输入顶点信息，初始化该顶点的边表；输入顶点信息，初始化该顶点的边表；3.依次输入边的信息并存储在边表中；依次输入边的信息并存储在边表中；3.1 输入边所依附的两个顶点的序号输入边所依附的两个顶点的序号i和和j；3.2 生成邻接点序号为生成邻接点序号为j的边表结点的边表结点s；3.3 将结点将结点s插入到第插入到第i个边表的头部；个边表的头部；7.2 图的存储结构及实现图的存储结构及实现数据结构（数据结构（C版）版）清华大学出版社清华大学出版社优点：优点：在边稀疏的情况下，用邻
