1.图的定义

　　图的定义：图G由顶点集V和边集E组成，记为G =（V,E）,其中V(G)表示图G中顶点的有限非空集，E(G)表示图G中顶尖之间的关系（边）集合，|V|表示图中顶点的个数，也称为图的阶，|E|表示图中边的条数。

　　简单图：不存在重复边；不存在顶点到自身的边；

　　完全图：无向图：边数 = n(n-1)/2

　　　　　　有向图：边数 = n(n-1)

　　强连通图：从顶点v到顶点w有路径和从顶点w到顶点v有路径，则顶点v和顶点w是强连通的。若 任意一对结点都是强连通的，则称此图为强连通图。

　　稀疏图：|E| < |V| log |V|

　　简单路径：顶点不重复出现的路径称为简单路径。

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

2.图的实现（包括邻接矩阵和邻接表）和基本操作

　　（1）邻接矩阵：

　　　　所谓邻接矩阵存储，是指用一个一位数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。

　　　　A[i][j] = 1表示从顶点i到顶点j有边。

　　　　特点：

　　　　　　①无线图的邻接矩阵是对称矩阵，因此在存储邻接矩阵时只需存储上（或下）三角矩阵的元素。

　　　　　　②第i行非零元素的个数表示第i个结点的出度；第j列非零元素的个数表示第j个结点的入度。

　　　　　　③稠密图适合用邻接矩阵存储

　　　　　　④设图G的邻接矩阵为A，Aⁿ的元素Aⁿ[i][j]表示从顶点i到顶点j的长度为n的路径的数目。

　　　　　　⑤空间复杂度为O(n²)

　　（2）邻接表法

　　　　特点：

　　　　　　①若G为无向图，则所需的存储空间为O(|V|+2|E|)。

　　　　　　   若G为有向图，则所需的存储空间为O(|V|+|E|)。

　　　　　　②对于稀疏图，采用邻接表法可以极大的节省存储空间。

　　　　　　③对于一个有向图，求一个顶点的出度只需要计算其邻接表中的结点个数；但求其入度则需要遍历全部邻接表。

　　　　　　④图的邻接表表示法不唯一。

3.图的两种遍历

　　（1）深度优先遍历

　　　　借助栈

伪代码如下：

 1 bool visited[MAX_VERTEX_NUM]
 2 void DFSTraverse(Graph G){
 3     for(v=0; v<G.vernum; ++v){    //访问标记数组初始化 
 4         visited[v] = FALSE;
 5     }
 6     for(v=0; v<G.vexnum; ++v){    //从0号开始遍历 
 7         if(!visited[v]){
 8             DFS(G,v);
 9         }
10     }
11 } 
12 void DFS(Graph G, int v){        //从顶点v出发，广度优先遍历图 
13     visit(v);
14     visited[v] = TRUE;
15     for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
16         if(!visited[w]){
17             DFS(G,w);
18         }//if
19     }//for
20 } 

　　空间复杂度：O(|V|)

　　邻接矩阵的时间复杂度：O(|V|²)

　　邻接表的时间复杂度：O(|V|+|E|)

　　（2）广度优先遍历

　　　　借助一个辅助队列

伪代码如下：

 1 bool visited[MAX_VERTEX_NUM]
 2 void BFSTraverse(Graph G){
 3     for(i=0; i<G.vernum; ++i){    //访问标记数组初始化 
 4         visited[i] = FALSE;
 5     }
 6     InitQueue(Q);
 7     for(i=0; i<G.vexnum; ++i){    //从0号开始遍历 
 8         if(!visited[i]){
 9             BFS(G,i);
10         }
11     }
12 } 
13 void BFS(Graph G, int v){        //从顶点v出发，广度优先遍历图 
14     visit(v);
15     visited[v] = TRUE;
16     EnQueue(Q,v);
17     while(!isEmpty(Q)){
18         DeQueue(Q,v);
19         for(w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)){
20             if(!visited[w]){
21                 visit(w);
22                 visited[w] = TRUE;
23                 EnQueue(Q,w);
24             }//if
25         }//for
26     }//while
27 } 

　　　　采用邻接矩阵存储：时间复杂度O(|V|²)，空间复杂度O(|V|)。

　　　　采用邻接表存储：时间复杂度O(|V|+|E|)，空间复杂度O(|V|)。

4.图的基本应用，包括最小支撑树、最短路径、拓扑排序和关键路径。

考试要求

掌握图的定义，包括完全图、连通图、简单路径、有向图、无向图、无环图等，明确理解图和二叉树、树和森林这种结构之间的异同点；

掌握图采用邻接矩阵和邻接表进行存储的差异性；

掌握广度优先遍历和深度优先遍历；

掌握最小支撑树（Prim算法、Kruskal算法）、最短路径（Dijkstra算法、Floyd算法）、拓扑排序以及关键路径的实现过程。