第6章学习小结

一学习小结

图的基本知识

1. 图分为无向图和有向图。若无向图有 n(n-1)/2 条边，则称之为无向完全图，若有向图有 n(n-1) 条弧，则称之为有向完全图

2. 带权图通常称为网

3. 度：顶点v的度指和v相关联的边的数目，记为TD(v) 入度：以v为头的弧的数目出度：以v为尾的弧的数目

4. 路径长度是一条路径上经过的边或弧的数目

5. 强连通图：在有向图G中，对于每一对vi,vj∈V，从vi到vj都存在路径

6. 连通生成树：一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边其中各边代价之和（权）最小的那棵生成树成为最小生成树

图的存储

1. 邻接矩阵

#define MaxInt 32767  //表示极大值，即∞
#define MVNum 100    //最大顶点数
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;        //假设边的权值类型为整型
typedef struct
{
    VerTexType Vexs[MVNum]; //顶点表
    ArcType arcs[MVNum] [MVNum]; //邻接矩阵
    int vexnum,arcnum;           //图的当前点数和边数
}AMGraph;

创建邻接矩阵的时间复杂度为O(n²)

2. 邻接表

#define MvNum 100       //最大顶点数 
typedef struct ArcNode    //边结点
{
    int adjvex;            //该边所指向的顶点的位置 
    struct ArcNode *nextarc;//指向下一条边的指针 
}ArcNode;

typedef struct VNode    //顶点信息
{
    VertexType data;
    ArcNode *firstarc;  //指向第一条依附该顶点的边的指针 
}VNode,AdjList[MvNum];  //AdjList表示邻接表类型

typedef struct
{
    AdjList Vertices;   //一维数组
    int vexnum,arcnum;  //图的当前顶点数和边数 
}Graph;

创建邻接矩阵的时间复杂度为O(n+e) (顶点数+边数)

图的遍历

1. DFS　深度优先搜索

　从某个顶点v出发，遍历v所在的连通分量

2. BFS 广度优先搜索

最小生成树

1. Prim算法普里姆算法 —— 加点法

时间复杂度 O(n²) 适用于稠密图

主要步骤：在所有 u∈ U， v∈V-U 的边（u,v）属于E中找一条权值最少的边（u0,v0），并入集合TE（N上最小生成树中边的集合），同时v0并入U

2. Kruskal算法克鲁斯卡尔算法 ——加边法

时间复杂度 O（e log e）适用于稀疏图

初始状态为只有n个顶点而无边的非连通图 T = { V , { } } 每个顶点自成一个连通分量

主要步骤：在E中选择权值最小的边，若该边依附的顶点落在不同连通分量上（即不形成回路），则将此边并入T，否舍去此边而选择下一条权值最小的边

最短路径：①路径上边的数目 ②路径上边的权值之和

1. Dijkstra算法迪杰斯特拉算法

二关于上次制定的目标和接下来的目标

这周没有合理安排时间大部分时间花在书面上，导致上机实践的时间大大缩水，很惭愧

下一周要先规划分配好时间，尽量保证足够的实操时间

第6章学习小结

推荐阅读