数据结构－－图

三种比较

　　线性表：数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继； 
　　树形结构：数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关； 
　　图形结构：结点之间的关系可以是任意的，图中任意两个元素之间都可能相关。

图的基本术语

　　图（Graph）：图G由两个集合V和E组成，记为G=(V,E)，这里，V是顶点的有穷非空集合，E是边（或弧）的集合，而边（或弧）是V中顶点的偶对。 
　　顶点（Vertex）：图中的结点又称为顶点。 
　　边（Edge）：相关顶点的偶对称为边。

　　有向图（Digraph）：若图G中的每条边都是有方向的，则称G为有向图。 
　　弧（Arc）：又称为有向边。在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。 
　　弧尾（Tail）：边的始点。 
　　弧头（Head）：边的终点。 
 

　　无向图（Undigraph）：若图G中的每条边都是没有方向的，则称G为无向图。 
　　无向完全图（Undirected Complete Graph）：恰好有n(n-1)/2的无向图。 
　　有向完全图（Directed Complete Graph）：恰好有n(n-1)条弧的有向图。 
　　邻接点（Adjacent）：若(vi,vj)是一条无向边，则称顶点vi和vj互为邻接点。 
　　度（Degree）：无向图中顶点v的度是关联于该顶点的边的数目，记为TD(v)。 
　　入度（Indegree）：若G为有向图，则把以顶点v为终点的边的数目，称为v的入度，记为ID(v)。 
　　出度（Outdegree）：若G为有向图，则把以顶点v为始点的边的数目，称为v的出度，记为OD(v)。 
　　对于有向图：TD(v)=ID(v)+OD(v) 

 
　　子图（Subgraph）：设G=(V,E)是一个图，若E'是E的子集，V'是V的子集，使得E'中的边仅与V'中顶点相关联，则图G'=(V',E')称为图G的子图。 
　　路径（Path）：无向图G=(V,E)中从顶点v到顶点v'的路径是一个顶点序列(v=vi0,vi1,…,vin=v')，其中(vij-1,vij)∈E，1≤j≤n。有向图G=(V,E)中从顶点v到顶点v'的路径是一个顶点序列(v=vi0,vi1,…,vin=v')，其中〈vij-1,vij〉∈E，1≤j≤n。 
　　简单路径：序列中顶点不重复出现的路径。 
　　环（Cycle）：又称回路，第一个顶点和最后一个顶点相同的路径。 
　　简单回路：又称简单环，除了第一个顶点和最后一个顶点外，其余顶点不重复的回路。 
连通：在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。 

    连通图（Connected Graph）：如果对于图中的任意两个顶点vi、vj∈V，vi和vj都是连通的，则称该图为连通图。 
　　连通分量（Connected Component）：无向图中的极大连通子图。 
　　强连通图：在有向图G中，如果对于每一对vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。 
　　强连通分量：有向图中的极大连通子图。 
　　生成树（Spanning Tree）：含有连通图的全部顶点的一个极小连通子图。 

　　网络（Network）：若将图的每条边都赋上一个权，则称这种带权图为网络。
 
有向图和无向图

　　无向图和有向图对照表