文档介绍：:图可用二元组表示:Graph=(V,E),其中V表示元素(顶点)的非空有限集合;E表示元素之间关系(边)的有限集集合,边是顶点偶对。可以看出图的每个结点有任意多个前驱和后继结点。:在一个有n个顶点的无向图中,若每个顶点到其它(n-1)顶点都有一条边,则图中有n个顶点且有(n*(n-1)/2)条边的图称为无向完全图邻接点:对无向图G=(V,E),若有(V1,V2)〈E,则称V1和V2互为邻接点相关边:两个相邻接的点连成的边叫做这两个结点的相关边度:与每个顶点相连的边的数叫该点的度入度:对有向图中某结点的孤头数(边的终点):对有向图中某结点的孤尾数(边的终点)称为该结点的出度路径:在一图中若从某个顶点VP出发,沿着一些边经过顶点V1,V2,…,Vm到达Vg则称顶点序列(VP,V1,V2,…,Vm,Vg)为从Vp到Vg的路径回路:从一顶点出发又回到该顶点,则所经过的路径称为回路连通:在无向图中,若从顶点Vi到顶点Vj之间有路径则称这两个顶点是连通的权:有些图对应每条边有一相应的数值,这个数值称为该边的权网::设G=(V,E)是具有n个顶点的图,则G的邻接矩阵是一个n*n的方阵,其中矩阵每一行分别对应图的各个顶点;矩阵的每一列分别对应图的各个顶点邻接矩阵的性质:,图的邻接矩阵是唯一确定的;;(或第i列)的非0元素的个数即为第i个顶点的度;,第i列非0元素个数为第i个顶点的入度,第i个顶点的度为第i行与第i列非0元素个数之和;,,用一个顺序存储区来存储图中各顶点的数据,并对图中每上顶点vi建立一个单链表(此单链表称之为的vi邻接表),把顶点vi的所有相邻顶点,即其后继顶点的序号链接起来邻接表与邻接矩阵的关系:;;;:一个非零元素表示与该行顶点相邻接的另一个顶点;:非零元素则表示该行顶点为起点的一条边的终点。:,它与表结点的链入次序有关;;,有向图的逆邻接表中第i个入边表的结点个数即为第i个结点的入度;,有向图的弧数等于邻接表(逆邻接表)中出边表结点(入边表结点)的数目。,这个矩阵称之为关联矩阵定义如下:图G=(V,E)的关联矩阵是一个矩阵,,且使得每一顶点仅被访问一次,这一过程称之为图的遍历假定给定图G的初态是所有顶点均未曾访问过,在G中任选一顶点v为初始出发点,则深度优先搜索可定义如下:从指定的起点v出发(先访问v,并将其标记为已访问过),访问它的任意相邻接的顶点w1,再访问w1