软件技术基础_图课件.ppt

《软件技术基础_图课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.3.3图一、图的定义和术语1、定义：由非空的顶点有穷集和边的有穷集组成。记为G（V，E）V：顶点集，非空E：边集，可以是空集(此时，只有顶点没有边)V1V2V3V4V5★图中数据元素之间的关系可以是任意的！2、术语：●有向图与无向图有向图：图中每条边都有方向有向边以表示又称为弧，弧尾：Vi弧头：VjV2V3V4V1V5V2V3V4V1V5无向图：由无向边组成以(Vi，Vj)表示ViVjViVj有向图无向图●邻接：若(Vi，Vj)∈E，则Vi与Vj互为邻接；若为有向边，则Vj是Vi的邻接点。●顶点的度D(V

2、i)：有向图：出度：以该顶点为弧尾的弧的数目入度：以该顶点为弧头的弧的数目顶点的度=出度+入度无向图：以该顶点为一个端点的边的条数。总边数＝21∑D(Vi)i=1n●路径：从一个顶点到另一个顶点的顶点序列如图中V1到V4的路径有：V1——V2——V3——V4V1——V3——V4V1——V5——V4第一个顶点与最后一个顶点相同的的路径称为环，如：V1——V2——V3——V1V1V2V3V4V5●连通与连通图：在图中若两个顶点之间有路径，则称这两个顶点是连通的。任意两个顶点都连通的图称为连通图。强连通图：有向图的每一对顶点之间相互都存在路径

3、。V2V3V4V1V5V2V3V4V1V5连通图非连通图●权与网：图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网（或网络）。V2V3V4V1V5342895二、图的存储1.邻接矩阵法(数组实现)：①给顶点编号②建立关系矩阵：aij的值表示j号顶点是否为i号顶点邻接点。V2V3V4V1V5010010010000001101000000012345A=有向图的邻接矩阵顶点的出度为该行的元素之和顶点的入度为该列的元素之和V2V3V4V1V5010111010001011101001010012345A

4、=无向图的邻接矩阵无向图的邻接矩阵是对称矩阵，顶点Vi的度是i行（或列）的元素之和。权值图的邻接矩阵：aij的值表示边或弧aij的权。∞3∞∞2∞∞4∞∞∞∞∞∞98∞5∞∞∞∞∞∞∞12345A=V2V3V4V1V5342895★图的邻接矩阵C语言描述：#defineMAXNUM20typedefstruct{elemtypenode[MAXNUM];intarcs[MAXNUM][MAXNUM];}graph;MAXNUM：图中顶点的最大数目node[]：表示顶点集arcs[][]：表示邻接矩阵★邻接矩阵的优点：增减边的操作简单，修

5、改arcs[i][j]的值就行了；★邻接矩阵的缺点：增减顶点的操作需搬移大量元素；存储空间的浪费：若边<<顶点2，则邻接矩阵为稀疏矩阵2.邻接表法（链式存储）：每个顶点建立一个单链表：单链表中的结点是该顶点的所有邻接顶点V2V3V4V1V5data124^5data21^3data324^5data41^3data51^3用一维数组存储头结点邻接表中包含两种结点：datai头结点：每个顶点对应一个头结点邻接结点：j与头结点邻接的顶点★邻接表的优点：节省空间、操作较简便★邻接结点的类型定义：typedefstructnode{intnod

6、eindex;structnode*nextadj;}adjnode;顶点号指向下一个与头结点相邻接的顶点★邻接表的类型定义：typedefstruct{headnodenodelist[MAXNUM];intnodenum;}graphlist;★头结点的类型定义：typedefstruct{intnodeindex;elemtypedata;adjnode*nextadj;}headnode;顶点号元素值指向与头结点相邻接的顶点用一维数组存储头结点21431data2data3data4data134134权值图的邻接表1data2

7、data3data4data233211354102331顶点号边权值有向图的邻接表124332511103三、图的遍历定义：从某个顶点出发，对图中所有顶点作且只作一次访问。问题：1）对于任一个图，从一个顶点出发沿着所有的路径是否可以将所有的顶点遍历到？2）图中有回路，遍历算法可能产生死循环，如何避免？V2V3V4V1V5为了避免重复访问同一顶点，设一辅助数组记住每个顶点的状态：visited[顶点号]=true顶点被访问过false顶点没有被访问过只有连通图才能从一个顶点出发访问到图中所有顶点图的遍历是其他操作的基础图的遍历有两种方法

8、：深度优先遍历与广度优先遍历1、深度优先遍历（depth-firstsearch，dfs）①从一个未访问过的顶点开始，先访问此顶点，再选取该顶点的一个未访问的邻接点。②然后访问该邻接点，再选取该邻接点的未访