图
一些重要的概念：
（1）无向完全图：对于无向图，若具有 n *（n-1）/ 2条边，则称为无向完全图；
有向完全图：对于有向图，若具有n *（n-1）条弧，则称为有向完全图；
（2）连通分量：无向图中的极大连通子图
Q1. 对于连通图，其连通分量是什么？ 它本身
Q2. 如果从无向图的任一顶点出发进行一次广度优先搜索可访问所有顶点，则该图一定是？ 连通图
（3）强连通图和强连通分量：在有向图G中，如果对于每一对vi，vj 属于 V，vi 不等于 vj, 从 vi 到 vj 和从 vj 到 vi 都存在路径，则称 G 是强连通图。（路径不等于通路！看下面的例题）
Q1. 写出算法，判别以邻接表方式存储的有向图G中是否存在由顶点vi到顶点vj的边（i!=j）。
bool has_edge(ALGraph G, VerTexType x, VerTexType y) { int i = LocateVex(G, x); int k = LocateVex(G, y); ArcNode p; for(p=G.vertices[i].firstarc; p!=NULL; p=p->next) { if(p->adjvex==j) //p指向的邻接点就是j return true; } return false; }
Q2. 写出算法，判别以邻接表方式存储的有向图G中是否存在由顶点vi到顶点vj的路径（i!=j)。
#define MVNum 100 int visited[MVNum] ; // = {0}，访问标志数组 int level = 1 ; //递归的次数 int PathDFS ( ALGraph G, int i, int j ) // i, j 表示图G中的两个顶点 { // 如果顶点 i 和 j 之间连通，则返回1；否则返回0 if ( i == j ) return 1 ; // 如果 i 和 j 相等，相等于环，结束递归 else { visited[ i ] = 1 ; for ( p = G.vertices[ i ].firstarc ; p ; p = p->nextarc, level-- ) // level-- 保证循环结束后的 level 的值不会比真实的递归次数多1 { level++ ; // 递归次数加1 k = p->adjvex ; // k 表示 p 的邻接边的点，如果 k 和 j 之间连通，那么 i 和 j 之间也能连通 if ( visited[ k ] == 0 && PathDFS ( G, k, j ) ) return 1 ; } } if ( level == 1 ) return 0 ; // 如果没有发生递归，i 和 j 也并不相等，那就说明两个顶点 i 和 j 之间是不连通的 }
从Q1、Q2得知，连通和路径是不一样的。连通就必须这两个点之间有边相连，但路径可以是其中一个点的临接点与两个点中的另外一个点连通。路径的意思就是 “能到就行” ，不一定要两个点之间直接连通。
（4）一棵有 n 个顶点的生成树有且仅有 n-1 条边。如果一个图有 n 个顶点和小于 n-1 条边，则是非连通图。如果它多于 n-1 条边，则一定有环。但是，有 n-1 条边的图不一定是生成树。
图的存储结构（邻接矩阵表示法、邻接表）
临接矩阵表示法
当G是网时，A[ i ][ j ] = 权值 或 无穷，无穷表示计算机允许的、大于所有边上权值的数
用临接矩阵表示法表示图时，除了一个用于存储临接矩阵的二维数组外，还需要用一个一维数组来存储顶点信息：
#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 ;
采用邻接矩阵创建无向网
void CreateUDN(AMGraph &G) { cin >> G.vexnum >> G.arcnum ; //依次输入总顶点数、总边数 for(int i=0 ; i<G.vexnum ; ++i) { cin >> G.vexs[ i ] ; } for(int i=0 ; i<G.vexnum ; ++i) {//初始化邻接矩阵，边的权值均置为极大值MaxInt for(int j=0 ; j<G.vexnum ; j++) { G.arcs[ i ][ j ] = MaxInt ; } } for(int k=0 ; k<G.arcnum ; ++k) { cin >> v1 >> v2 >> w ; //输入一条边依附的顶点及权值 i = LocateVex(G, v1) ; j = LocateVex(G, v2) ; //确定v1和v2在G中的位置，即顶点数组的下标 G.arcs[ i ][ j ] = w ; G.arcs[ j ][ i ] = G.arcs[ i ][ j ] ; } }
该算法的时间复杂度为O（n*n），若要建立无向图，则1、在初始化邻接矩阵时将边的权值均初始化为0；2、构造邻接矩阵时将权值w改为常量值1即可
邻接矩阵表示的优点：1、便于判断两个顶点之间是否有边（G[ i ][ j ] = 1或0）；2、便于计算各个顶点的度（对于无向图，邻接矩阵第 i 行元素之和就是顶点 i 的度；对于有向图，第 i 行元素之和就是顶点 i 的出度，第 i 列元素之和就是顶点 i 的入度）；
邻接矩阵表示的缺点：1、不便于增加、删除顶点；2、不便于统计边的数目，需要扫描邻接矩阵所有元素才能统计完毕，时间复杂度为O（n*n）；3、空间复杂度为O（n*n），对于稀疏图而言尤其浪费空间（所以邻接矩阵更适用于稠密图）。
邻接表表示法
邻接表由两部分组成：表头节点表（数据域+链域）、边表（邻接点域+数据域+链域）
#define MVNum 100 typedef struct ArcNode //边表 { int adjvex ; //该边所指向的顶点的位置 struct ArcNode *nextarc ; //指向下一条边的指针 Other info ; //和边相关的信息 }ArcNode ; typedef struct VNode //表头结点表 { VerTexType data ; ArcNode *firstarc ; //指向第一条依附该顶点的边的指针 }VNode, AdjList[MVNum] ; typedef struct { AdjList vertices ; int vexnum, arcnum ; //图的当前顶点数和边数 }ALGraph ;
采用邻接表创建无向图
void CreateUDG(ALGraph &G) { cin >> G.vexnum >> G.arcnum ; //输入总顶点数，总边数 for(int i=0 ; i<G.vexnum ; ++i) { cin >> G.vertices[ i ].data ; //输入顶点值 G.vertices[ i ].firstarc = NULL ; //初始化表头结点的指针域为NULL } for(int k=0 ; k<G.arcnum ; ++k) { cin >> v1 >> v2 ; //输入一条边依附的两个顶点 i = Locate(G, v1) ; j = Locate(G, v2) ; p1 = new ArcNode ; //生成一个新的边结点*p1 p1->adjvex = j ; //邻接点序号为 j p1->nextarc = G.vertices[ i ].firstarc ; G.vertices[ i ].firstarc = p1 ; //将新结点*p1插入顶点 vi 的边表头部 p2 = new ArcNode ; p2->adjvex = i ; p2->nextarc = G.vertices[ j ].firstarc ; G.vertices[ i ].firstarc = p2 ; } }
该算法的时间复杂度是O(n + e)
建立有向图的邻接表，更加简单，每读入一个顶点对序号 i， j，仅需生成一个邻接点序号为 j 的边表结点，并将其插入到 vi 的边链表头部即可；
若要创建网的邻接表，可以将边的权值存储在info域中。
一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一。这是因为邻接表表示时，个边表的链接次序取决于建立邻接表的算法，以及边的输入顺序。
邻接表的优点：1、便于增加和删除顶点；2、便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目，时间复杂度为O（n + e）；3、空间效率高（适合表示稀疏图）
邻接表的缺点：1、不便于判断顶点之间是否有边，要判定 vi 和 vj 之间是否有边，就需扫描第 i 个边表，最坏情况下要耗费O（n）房间；2、不便于计算有向图各个顶点的度（对于无向图，在邻接表表示中顶点 vi 的度是第 i 个边表中的结点个数；在有向图的邻接表中，第 i 个边表上的结点个数是顶点 vi 的出度，但求 vi 的入度比较困难，需遍历各顶点的边表）
图的遍历（课本p161页图6.17（b）（c））
深度优先搜索（DFS, 遍历类似于树的先序遍历）“不撞南墙不回头”
注意复习6月2日个人小测最后一题！！
1、DFS遍历连通图
bool visited[MVNum] ; //访问标志数组，其初值为“false” void DFS(Graph G, int v) {//从第v个顶点出发递归地深度优先遍历图G cout << v ; visited[ v ] = true ; for(int w = FirstAdjVex(G, v) ; w >= 0 ; w = NextAdjVex(G, v, w) ; //依次检查v的所有邻接点w， FirstAdjVex(G, v)表示v的第一个邻接点 //NextAdjVex(G, v, w)表示v相对于w的下一个邻接点，w >= 0 表示存在邻接点 if( !visited[ w ]) DFS(G, w) ; //对v的尚未访问的邻接顶点w递归调用DFS }
2、DFS遍历非连通图
void DFSTraverse(Graph G) { for(int v=0 ; v < G.vexnum ; ++v) { visited[ v ] = false ; //访问标志数组初始化 } for(innt v=0 ; v < G.vexnum ; ++v) { if( !visited[ v ]) DFS(G, v) ; //循环调用DFS遍历连通图时的程序 } }
3、采用邻接矩阵表示图的DFS
void DFS_AM(AMGraph G, int v) { cout << v ; visited[ v ] = true ; for(int w=0 ; w<G.vexnum ; ++w) { if((G.arcs[ v ][ w ] != 0) && ( !visited[ w ] )) //G.arcs[ v ][ w ] != 0 表示w是v的邻接点，如果w未访问，则递归调用DFS_AM DFS_AM(G, w) ; } }
4、采用邻接表表示图的DFS
void DFS_AL(ALGraph G, int v) { cout << v ; visited[ v ] = true ; p = G.vertices[ v ].firstarc ; //p指向v的边链表的第一个边结点 while(p != NULL) //边结点非空 { w = p->adjvex ; //表示w是v的邻接点 if( !visited[ w ] ) DFS_AL(G, w) ; //如果w未访问，则递归调用DFS_AL p = p->nextarc ; } }
当用邻接矩阵表示图时，查找每个顶点的邻接点的时间复杂度为O(n*n），其中 n 为图中顶点数
当以邻接表做图的存储结构时，查找邻接点的时间复杂度为O(e），其中 e 为图中边数
所以，当以邻接表做存储结构时，DFS遍历图的时间复杂度为O(n + e）
广度优先搜索（BFS, 遍历类似于树的层次遍历）
广度优先搜索遍历连通图
void BFS(Graph G, int v) { cout << v ; visited[ v ] = true ; InitQueue(Q) ; //辅助数列初始化，置空 EnQueue(Q, v) ; //v进队 while( !QueueEmpty(Q) ) //队列非空 { DeQueue(Q, u) ; //队头元素出队并置为u for(int w=FirstAdjVex(G, u) ; w >= 0 ; w = NextAdjVex(G, u, w) ) if( !visited[ w ] ) { cout << w ; visited[ w ] = true ; EnQueue(Q, w) ; } } }
BFS、DFS遍历图的时间复杂度相同，即当用邻接矩阵存储时，时间复杂度为O(n * n）；用邻接表存储时，时间复杂度为O(n + e）。两种遍历方法仅仅在于对顶点访问的顺序不同
最小生成树
最小生成树不是唯一的（指画图求解时）。因为：每次都选择最小边时，可能存在多条同样权值的边可选，此时任选其一即可。
Prim算法（“加点法”）
Kruskal算法
这两种算法是理解的重点，通过SPOC视频+PPT复习
有权图的单源最短路——Dijkstra算法
注意复习6月8日个人作业第1题！！
这也是理解的重点，需要掌握画过程的图，通过SPOC视频复习。
原文：https://www.cnblogs.com/cq20/p/13124392.html