会计学7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)2）邻接、关联(guānlián)无向图中，对于任意两个顶点vi和顶点vj，若存在边(vi，vj)，则称顶点vi和顶点vj互为邻接点，同时称边(vi，vj)关联(guānlián)于顶点vi和顶点vj。有向图中，对于任意两个顶点vi和顶点vj，若存在弧<vi，vj>，则称顶点vi邻接到顶点vj，顶点vj邻接于顶点vi，同时称弧<vi，vj>关联(guānlián)于顶点vi和顶点vj。7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.1图的概念(gàiniàn)7.2图的存储(cúnchǔ)7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.1邻接矩阵表示法7.2.2邻接(línjiē)表表示法例1：无向(wúxiànɡ)图的邻接表分析1:对于n个顶点e条边的无向图，邻接表中除了n个头结点(jiédiǎn)外，只有2e个表结点(jiédiǎn),空间效率为O(n+2e)。若是稀疏图(e<<n2)，则比邻接矩阵表示法O(n2)省空间。7.2.2邻接(línjiē)表表示法7.2.2邻接(línjiē)表表示法voidCREATADJLIST(vexnodega[],intn,inte){inti,j,k;edgenode*s;for(i=0;i<n;i++)/*读入顶点(dǐngdiǎn)信息*/{ga[i].vertex=getchar();ga[i].link=NULL;}7.2图的存储(cúnchǔ)7.3图的遍历(biànlì)7.3.1连通图的深度(shēndù)优先搜索遍历7.3.1连通图的深度优先(yōuxiān)搜索遍历邻接矩阵中图的基本操作——深度优先(yōuxiān)遍历7.3.1连通(liántōng)图的深度优先搜索遍历邻接(línjiē)表中图的基本操作——深度优先遍历7.3.1连通图的深度优先搜索(sōusuǒ)遍历7.3.2连通图的广度优先搜索(sōusuǒ)遍历7.3.2连通图的广度优先搜索(sōusuǒ)遍历邻接矩阵中图的基本操作——广度优先(yōuxiān)遍历7.3.2连通图的广度优先搜索(sōusuǒ)遍历邻接(línjiē)表中图的基本操作——广度优先遍历7.3.2连通图的广度优先(yōuxiān)搜索遍历7.3.3非连通(liántōng)图的遍历intvisited[n];graphg;voidTRAVER(){inti;for(i=0;i<n;i++)visited[i]=0;/*标志数组初始化*/for(i=0;i<n;i++)if(visited[i]==0){DFS(i);/*从顶点(dǐngdiǎn)i出发遍历某一个连通分量*/ptintf(“compend\n”);}}7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树（1）从V中任选一顶点u0，并置T为只含一个顶点的树：即初始状态：U={u0},TE={}；（2）只要U≠V,就找出一条(yītiáo)权值最小的边(u,v),且u∈U,v∈V-U,将该条边(u,v)和不在T中的顶点v加入T中。即：while(U≠V){(u,v)=min{wuv,u∈U,v∈V-U};U=U+{v};TE=TE+{(u,v)}}（3）直到把所有顶点加入T为止。7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树7.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树17.4生成(shēnɡchénɡ)树和最小生成(shēnɡchénɡ)树for(k=0;k<n-1;k++)/*找n-1条边*/{min=max;for(j=k;j<n-1;j++)/*找最短边*/if(T[j].length<min){min=T[j].length;m=j;}e=T[m];T[m]=T[k