图

（数据结构课堂内容复习~）

掌握内容：

　　图的存储结构：邻接矩阵、邻接表、邻接多重表和十字链表

　　基于存储结构上的遍历操作和各种应用：拓扑排序、最小生成树、最短路径和关键路径等

基本定义：

　　图：图G由顶点集V和边集E组成，用|V|表示图G中顶点的个数，也称图G的阶，|E|表示图G中边的条数。

　　有向图：若E是有向边的有限集合时，则图G为有向图。弧是顶点的有序对，记为<v,w>，其中v、w是顶点。

　　无向图：若E是无向边的有限集合时，则图G为无向图。边是顶点的无序对，记为(v,w)或(w,v)

　　简单图：一个图G如果满足：1.不存在重复边 2.不存在顶点到自身的边；则称图G为简单图。（此处的数据结构中仅讨论简单图）

　　多重图：若图G中某两个结点的边数多于一条，又允许顶点通过同一条边与自己关联，则G为多重图。（定义与简单图相对）

　　完全图：在无向图中，若任意两个顶点之间都存在边，则称该图为无向完全图。含有n个顶点的无向完全图有n(n-1)/2条边。在有向图中，若任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。含有n个顶点的有向完全图有n(n-1)条有向边。

　　子图：设有两个图G=(V,E)和G^，=(V^，，E^，)，若V^，和E^，分别是V和E的子集，则称G^，是G的子图。若满足V(G^,)=V(G)的子图G^，，则称其为G的生成子图。

　　连通、连通图、连通分量：在无向图中，若从顶点v到w有路径存在，则称v和w是连通的。若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。若一个图有n个顶点，并且边数小于n-1，则此图必是非连通图。

　　强连通图、强连通分量：在有向图中，若从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量。

注意：强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

　　生成树、生成深林：连通图的生成树是包含图中全部顶点的一个极小连通子图。顶点数为n则它有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边，则会变成一条回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。

　　顶点的度、入度和出度：以该顶点为一个端点的边的数目称为顶点的度。对于无向图，顶点V的度是指依附于该顶点边的条数，记为TD(v)。无向图的全部顶点的度的和等于边数的2倍，因为每条边都和两个顶点相关联。对于有向图，顶点度分为入度和出度，且顶点的度等于其入度和出度之和。

　　边的权和网：在一个图中，每条边都可以标上具有某种含义的数值，称为权值。这种图称为带权图，也称网。

　　稠密图、稀疏图：边数很少的图称为稀疏图，反之为稠密图。一般G满足|E|<|V|log|V|时，可以将G视为稀疏图。

　　路径、路径长度和回路：顶点u到顶点v的路径是指其抵达的顶点序列，路径上的点数称为路径长度。第一个顶点和最后一个顶点相同的路径称为回路或环。若一个图有n个点，大于n-1条边，则此图一定有环。

　　简单路径、简单回路：在路径序列中，顶点不重复出现的路径称为简单路径。除第一个顶点和最后一个顶点外，其余顶点不重复出现的称为简单回路。

　　距离：从顶点u出发到顶点v的最短路径的路径长度称为从u到v的距离。若从u到v根本不存在路径则该距离为无穷(∞)

　　有向树：一个顶点入度为0、其余顶点入度均为1的有向图，称为有向树。

图的存储及基本操作：

　　1.邻接矩阵法

　　用一个一维矩阵存储图中顶点信息，用一个二维数组存储图中边的信息。定义如下：

1 #define MaxVertexNum 100  //顶点数目的最大值
2 typedef char VertexType;  //顶点的数据类型
3 typedef int EdgeType;     //带权图中边上权值和数据类型
4 typedef struct
5 {
6     VertexType Vex[MaxVertexNum]; //顶点表
7     EdgeType Edge[MaxVertexNum][MaxVertexNum];//邻接矩阵，边表
8     int vexnum,arcnum;            //图的当前顶点数和弧数
9 }MGraph;

邻接矩阵

　　无向图的邻接矩阵一定是一个对称矩阵。

　　用邻接矩阵存图，很容易确定图中任意两个顶点之间是否有边相连。但是图中有多少条边必须按行、按列对每个元素进行检测，所花费的时间代价很大。这是邻接矩阵的局限性。

　　适用于稠密图

　　2.邻接表法

　　对图G中的每个顶点建立一个单链表，每个单链表中的结点表示依附于该顶点的边，这个单链表就称为顶点的边表。边表的头指针和数据信息采用顺序存储，所以在邻接表中存在两种结点：顶点表结点和边表结点。

　　顶点表结点由顶点域和指向第一条邻接边的指针构成，边表结点由邻接点域和指向下一条邻接边的指针域构成。定义如下：

 1 #define MaxVertexNum 100   //图中顶点数目的最大值
 2 typedef struct ArcNode     //边表结点
 3 {
 4     int adjvex;            //该弧所指向的顶点的位置
 5     struct ArcNode *next;  //指向下一条弧的指针
 6     //InfoType info;       //网的边权值
 7 }ArcNode;
 8 typedef struct VNode       //顶点表结点
 9 {
10     VertexType data;       //顶点信息
11     ArcNode *first;        //指向第一条依附该顶点的弧的指针
12 }VNode,AdjList[MaxVertexNum];
13 typedef struct
14 {
15     AdjList vertices;      //邻接表
16     int vexnum,arcnum;     //图的顶点数和弧数
17 }ALGraph;                  //ALGraph是以邻接表存储的图类型

邻接表

　　对于稀疏图，采用邻接表表示极大地节省存储空间。

　　在邻接表中，给定一顶点，能很容易找出它的邻边，但是若要确定两个顶点间是否存在边，则在邻接矩阵中可以直接查到，而邻接表中则需要在相应结点对应的边表中查找另一结点，效率低。

　　3.十字链表

　　十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图的每条图弧有一个结点，对应于每个顶点也有一个结点。

　　弧结点中有5个域：尾域和头域分别指示弧尾和弧头这两个顶点在图中的位置；链域hlink指向弧头相同的一下条弧；链域tlink指向弧尾相同的下一条弧；info域指向该弧的相关信息。这样。弧头相同的弧就在同一个链表上，弧尾相同的弧也在同一链表上。

　　顶点结点中有3个域：data域存放顶点相关信息，如顶点名称；firstin和firstout两个域分别指向以该顶点为弧头或者弧尾的第一个弧结点。定义如下：

 1 #define MaxVertexNum 100   //图中顶点数目的最大值
 2 typedef struct ArcNode     //边表结点
 3 {
 4     int tailvex,headvex;   //该弧的头尾结点
 5     struct ArcNode *hlink,*tlink; //分别指向弧头相同和弧尾相同的结点
 6     //InfoType info;       //相关信息指针
 7 }ArcNode;
 8 typedef struct VNode       //顶点表结点
 9 {
10     VertexType data;       //顶点信息
11     ArcNode *firstin,*firstout; //指向第一条入弧和出弧
12 }VNode;
13 typedef struct 
14 {
15     VNode xlist[MaxVertexNum];  //邻接表
16     int vexnum,arcnum;      //图的顶点数和弧数
17 }GLGraph;                   //GLGraph是以十字邻接存储的图类型

十字链表

　　邻接多重表

　　邻接多重表是无向图的另一种链式存储结构。

　　在邻接表中求两个