会计学7.1图的概念(gàiniàn)V(G1)={1,2,3,4}顶点(dǐngdiǎn)集合;E(G1)={<1,2>,<1,3>,<3,4>,<4,1>}边的集合（顶点(dǐngdiǎn)关系）V(G2)={1,2,3,4,5}顶点(dǐngdiǎn)集合;E(G2)={(1,2),(1,4),(2,3),(2,5),(3,4),(3,5)}边的集合7.1.2图的基本术语1、完全图：在一个有N个顶点的图中，若每个顶点到其它（N-1）顶点都有一条边，则图中有N个顶点且有（N*（N-1）/2）条边的图称为完全图。2、邻接点：对无向图G=（V，E），若有（V1，V2）属于(shǔyú)E则称V1和V2互为邻接点。3、相关边：两个相邻接的点连成的边叫做这两个结点的相关边。4、度：与每个顶点(dǐngdiǎn)相连的边的数叫该点的度。5、入度：对有向图中某结点的弧头数（边的终点）称为该结点的入度。6、出度：对有向图中某结点的弧尾数（边的终点）称为该结点的出度。7、路径：在一图中若从某个顶点(dǐngdiǎn)VP出发，沿着一些边经过顶点(dǐngdiǎn)V1，V2，…,VM到达VG则称顶点(dǐngdiǎn)8、回路：从一顶点(dǐngdiǎn)出发又回到该顶点(dǐngdiǎn)，则所经过的路径称为回路。9、子图若G和G'是两个图，且存在着V(G')≤V(G)和E（G’）≤E（G）的关系，则称G’是G的子图10、有关连通的概念连通：在无向图中，若从顶点VI到顶点VJ之间有路径则称此二顶点是连通的。连通图：如果图中任意一对顶点之间都是连通的，则称此图为连通图。强连通：对于(duìyú)有向图，若从顶点VI到顶点VJ到顶点VI之间都有路径，则称这两点是强连通的。强连通图：图中任何一对顶点都是强连通的，则此图叫强连通图。连通分量：非连通图中的每一个连通部分叫连通分量。强连通分量：有向图中极大强连通子图称为有向图的强连通分量。11、生成树一个连通的生成树，它含有图中全部顶点(dǐngdiǎn)，但只有足以构成树的N-1条边（N顶点(dǐngdiǎn)个数）如图P15912.权、网权：有些图对应每条边有一相应的数值。这个数值叫该边的权。网：这种带权的图叫网。注：不同网络的权有不同的意义(yìyì)：电网络权可以是阻抗，运输网络中的权可以是路程长度，运费等。7.1.3图的几种基本操作(1)LOC_VERTEX(G,v)顶点定位(dìngwèi)函数顶点函数:确定顶点在图G中的位置.若图中无此顶点，则函数值为零.(2)GET_VERTEX(G,i)取顶点函数取点函数:求图G中第i个顶点.若i>图G中顶点数则函数值为零.(3)FIRST_ADJ(G,v)求第一个邻接点函数求第一个邻接点函数:求图G中顶点V的第一个邻接点.若v没有邻接点或图G中无顶点v,则函数值为零.……P1567.2图的存贮(cúnzhù)结构7.2.2邻接表邻接表是由邻接矩阵改造而来(érlái)的一种链接结构,它只考虑非零元素,因而节省了零元素所占的存贮空间.逆邻接表链表中每个结点表示邻接矩阵中该顶点的列中每个非零元素图的存贮结构(jiégòu)说明几点说明:1.如果图的各边是带权的,也可以用邻接矩阵来表示,只需将矩阵中1元素换成相应(xiāngyīng)边的权值.2.邻接矩阵表示法对于以图的顶点为主的运算比较适用.3.除完全图外,其他图的邻接矩阵有许多零元素,特别是当n值较大,而边数又少是,则此矩阵称为"稀疏矩阵".浪费存储空间.邻接表与邻接矩阵的关系:1.与邻接矩阵的每一行有一个线形链接表.2.链接表的表头对应着邻接矩阵该行的顶点.3.链接表中的每个结点(jiédiǎn)对应着邻接矩阵正中该行的一个非零元素无向图:一个非零元素表示与该行顶点相邻接的另一个顶点有向图:非零元素则表示该行顶点为起点的一条边的终点几点说明:1.在邻接表中的每个线性链接表中各结点的的顺序是任意的.2.邻接表中的各个线性链接表不说明它们顶点(dǐngdiǎn)之间的邻接关系.3.对于无向图:某顶点(dǐngdiǎn)的度数=该顶点(dǐngdiǎn)对应的线性链表的结点数对于有向图:某顶点(dǐngdiǎn)的"出度"数=该顶点(dǐngdiǎn)对应的线性链表的结点数逆邻接(línjiē)表链表中每个结点表示邻接(línjiē)矩阵中该顶点的列中每个非零元素7.3图的遍历(biànlì)图的遍历(biànlì)的两种方法1.深度优先(yōuxiān)搜索dfs例：2.广度优先(yōuxiān)搜索bfs例：7.4图的最小生成(shēnɡchénɡ)树P159G3图7.3(a)邻接(línjiē)表说明：该图中包括三个连通