第六章图图的定义和术语有向图：在图G中，边是顶点的有序对，每条边都用箭头指明了方向，若<Vi,Vj>是有向图中的一条边，则称Vi是尾或始点(初始顶点)；Vj是头或终点(终端顶点)，且用从尾到头的箭头表示，<Vi,Vj>和<Vj,Vi>不同。无向图：边是顶点的无序对，<Vi,Vj>和<Vj,Vi>表示同一条边。无向完全图：如果在无向图中，任何两个顶点都有一条边相连接，则称此图为无向完全图。含有n个顶点，每一个顶点都与其它n-1个顶点有边，因此，共有n*(n-1)/2条边。有向完全图：在有向图G中，任何两个顶点都有方向相反的两条弧线连接，若图G中含有个n顶点，则共有n*(n-1)条弧。子图:假设有两个图G=(V,E)和图G’=(V’,E’)，如果V’V，且E’E,则称G’为G的子图。弧：在有向图中，一条有向边称为弧。若<Vi,Vj>是有向图中的一条边，则称Vi是弧尾，Vj是弧头。度：顶点V的度是和V相关联的边或弧的数目，记为TD(V)。入度：如果顶点V是有向图的一个顶点，则称以V为头的弧的数目为V的入度，记为ID(V)。出度：如果顶点V是有向图的一个顶点，则称以V为尾的弧的数目为V的出度，记为OD(V)。有向图顶点的度：顶点V的度TD(V)=ID(V)+OD(V)。推论：如果顶点Vi的度为TD(Vi)，那么有n个顶点，e条边或弧的图，满足如下关系路径：图中从顶点V到顶点V’的路径是顶点的序列（V=Vi,0,Vi,1,…,Vi,m=V’），其中（Vi,j-1,Vi,j)E，1jm。路径的长度：路径上所含边的数目。回路：第一个顶点和最后一个顶点相同的路径称为回路。简单路径：序列中顶点不重复出现的路径称为简单路径。简单回路：除第一个和最后一个顶点之外，其它顶点不重复出现的回路，称为简单回路或环。连通：在无向图G中，若从顶点V到顶点V’有路径，则称V和V’是连通的。连通图：若对于无向图中任意两个顶点Vi，VjV都是连通的，则称为连通图。连通分量：指无向图中极大连通子图。强连通图：在有向图中，如果对每一对Vi,VjV，ViVj，从Vi到Vj和从Vj到Vi都存在路径，则称G是强连通图。强连通分量：有向图G的极大强连通子图称为强连通分量。极小连通子图：一个连通图的生成树是该图一个含有图中所有n个顶点和n-1条边的极小连通子图。网：如果图G(V,E)中每条边都赋于反映这条边的某种特性的数据，则称此图G是一个网。其中与边相关的数据称为该边的权。权所反映的特性，由具体问题决定，例如两点之间的距离，时间，代价。图的基本操作图的存储结构图的邻接矩阵总结1、对于个n顶点的有向图，需要n2个存储单元。2、无向图的邻接矩阵是一个对称矩阵，只需要存上三角或下三角部分就可以了，需要个存储单元。图的邻接矩阵表示了一个图，可借助其实现顶点度的运算：无向图顶点Vi的度是矩阵中第i行或第i列元素之和网的邻接矩阵Wi,j，若（Vi,Vj)或<Vi,Vj>VRA[i，j]=0,(i=j)，反之0570480950650310无向图的邻接矩阵的C语言表示：intMAX=20;//最大顶点个数typedefstructgadjmat//图的邻接矩阵{charvertex[MAX];//字符型顶点向量intedge[MAX][MAX];//邻接矩阵};createadjmat(g)//创建无向图g的邻接矩阵structgadjmatg;{inti,j,k,n,e;scanf(“%d,%d”,&n,&e);//图的当前顶点数n和边数efor(i=0;i<n;i++)//读入n个顶点信息scanf(“%c”,&g.vertex[i]);for(i=0;i<n;i++)//邻接矩阵初始化为0for(j=0;j<n;j++)g.edge[i][j]=0;for(k=1;k<=e;k++)//读入e条边{scanf(“%d,%d”,&i,&j);g.edge[i][j]=1;g.edge[j][i]=1;}}邻接链表无向图的邻接链表存储方式用C语言描述如下：typedefstructglinklistnode//链表结点的结构{intadjvex;//该边所指向的顶点的位置charinfo;//该边相关的信息，如权值structglinklistnode*nextarc;//指向下一条边的指针};typedefstructgheadnode//顺序表结点的结构{charvexinfo;//顶点信息structglinklistnode*firstarc;//指向第一条依附该顶点的边的指针};intcreate