图的相关概念

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为G(V,E)，其中，G表示一个图， V是图G中顶点的集合，E是图G中边的集合
顶点图中数据元素。在图结构中，不允许没有顶点，即在定义中强调顶集合V有穷非空。
边在图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的。
无向边和无向图:若顶点v1到v2之间的边没有方向，则称这条边为无向边，用无序偶对(v1,v2)表示。如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
有向边和有向图若从顶点V1到v2的边有方向，则称这条边为有向边，也称为弧，用有序偶<v1,v2>来表示，v1称为弧尾，v2称为弧头。如果图中任意两个顶点之间的边都是有向边，则称该图诶有向图

图1

• 图的顶点与边间关系

1. 对于无向图G=(V,{E}),如果边(v,v)**属于E，则称顶点V和V互为邻接点(Adjacent)，即v和v相邻接。边**(v,v)依附于顶点v和v或者说**(v,v)与顶点v和v`相关联。顶点v的度(Degree)是和v相关联的边的数目，记为TD(v)。边数就是各顶点度数和的一半**
2. 对于有向图G=(V,{E}),如果弧(v,v)**属于E，则称顶点v·邻接自顶点v(Adjacent)。弧**(v,v)和顶点v和v`相关联。以顶点v为头的弧的数目称为v的入度，记做ID(v)。以顶点v为尾的弧的数目称为v的出度，记做OD(v)。顶点v的度(Degree)为TD(v)=ID(v)+OD(v)。
3. 树中根结点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却不是唯一的。
4. 第一个顶点到最后一个顶点相同的路径称为回路或环(Cycle)。序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路或简单环。

• 连通图相关术语
  在无向图G中，如果从顶点v到顶点v有路径，则称v和v是连通的。如果对图中任意两个顶点vi,vj属于E，vi和vj都是连通的，则称G 是连通图。
  无向图中的极大连通子图称为连通分量。即

1. 要是子图
2. 子图要是连通的
3. 连通子图含有极大顶点数
4. 具有极大顶点数的连通子图包含依附于这些顶点的所有边
   在有向图G中，如果对于每一对vi，vj属于v,vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。
   连通图的生成树:是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
   有向树如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一颗有向树。入度为0就相当于树中的根结点，其余顶点入度为1就是说树的非根结点的双亲只有一个。一个有向图的生成森林由若干颗有向树组成，含有图中全部顶点，但只有足以构成若干颗不想交的有向树的弧。

• 总结

1. 图按照有无方向无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧尾和弧头之分。
2. 图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点到自身的边叫简单图。
3. 图中顶点之间有邻接点、依附的概念，无向图顶点的边数叫做度，有向图顶点分为入度、出度。
4. 图中顶点间存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向的则称为强连通分量
5. 无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0，其余顶点入度为1的叫有向树。一个有向图由若干颗有向树构成生成森林。

图的存储结构

• 邻接矩阵

1. 图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。

   
   
   image.png
2. 矩阵的主对角线全为0，表示不存在顶点到自身的边。arc[0][1]=1是因为v0到v1的边存在。以无向图的边数组是一个对称矩阵。
3. 某个顶点的度，就是这个顶点vi在邻接矩阵中第i行(或第i列)的元素之和。比如顶点v1的度为2.

4. 求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点。

   
   
   有向图
   
   

   顶点v1的入度为1，正好是第v1列各数之和。顶点v1的出度为2，即第v1行的各数之和。
   5)下图G是网图，n个顶点，则邻接矩阵是一个n*n的方阵

   
   
   image.png
   
   
   image.png

• 邻接表
  适用于边数相对顶点较少的图。考虑对边或弧使用链式存储的方式避免空间浪费的问题。数组与链表相结合的存储方法称为邻接表。
  邻接表的处理方法:

1. 图中顶点用一个一维数组存储。每个数据元素还需存储指向第一个邻接点的指针，以便查找该顶点的边信息。
2. 图中每个顶点vi的所有邻接点构成一个线性表，单链表存储。
   
   image.png
   
   顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息，firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成，adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针。
   通过查找某顶点的边表中结点的个数就可以知道该顶点的度
   通过测试顶点vi的边表中adjvex是否存在结点vj的下标j就可以判断顶点vi到vj是否存在边。
   
   带权值的网图

• 十字链表
  十字链表弥补邻接表的缺陷，
  其重新定义的顶点表结点结构中firstin表示入边表头指针，指向该顶点的入边表中第一个结点，firstout表示出边表头指针，指向该顶点的出边表中的第一个结点。
  
  结点结构
  
  重新定义的边表结点结构:tailvex指弧起点在顶点表的下标，headvex指弧终点在顶点表中的下标，headlink指入边表指针域，指向终点相同的下一条边，taillink是指边表指针域，指向起点相同的下一条边。如果是网，再加一个weight域来存储权值。
  
  image.png

• 邻接多重表

  
  
  image.png

• 边集数组
  由两个一维数组构成，一个存储顶点的信息，一个存储边的信息，这个边数组每个数据元素由一条边的起点下标、终点下标和权组成。

  
  
  image.png

图的遍历

从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这个过程就叫做图的遍历。

• 深度优先遍历(Depth_First_Search)
  对于连通图:就像一棵树的前序遍历，从图中某个顶点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
  对于非连通图：对其连通分量分别进行深度优先遍历，即在先前一个顶点进行一次深度优先遍历后，若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

• 广度优先遍历(Breadth_First_Search)
  类似于树的层序遍历。

  
  
  image.png
  
  

  深度优先更适合目标比较明确，以找到目标为主要目的的情况，而广度优先更适合在不断扩大遍历范围时找到相对最优解的情况。

最小生成树

构造连通网的最小代价生成树
有普里姆算法和克鲁斯卡尔算法找连通网的最小生成树。

• 普里姆(Prim)算法
  以某顶点为起点，逐步找各顶点上最小权值的边来构建最小生成树。
  
  image.png
• 克鲁斯卡尔(Kruskal)算法
  主要针对边展开，边数少时效率高。
  
  image.png

最短路径

• 迪杰斯特拉(Dijkstra)算法
  按路径长度递增的次序产生最短路径的算法。即一步步求出它们之间顶点的最短路径，过程中都是基于已经求出的最短路径的基础上，求得更远顶点的最短路径。
  解决从某个源点到其余各顶点的最短路径问题。
• 费洛伊德(Floyd)算法
  求所有顶点至所有顶点的最短路径问题。