数据结构知识点总结

第七章 图 7.1 图的基本概念

无向图，有向图，边，顶点，子图，路径，路径长度，强连通，弱连通，极大连通子图，连通分量，回路，度，出度，入度。

n个顶点的完全无向图有n(n-1)/2条边，完全有向图有n(n-1)条边。

连通的无回路的无向图为一棵树。

7.2 图的存贮结构 7.2.1邻接矩阵

方针，有边记1，无边记0。

无向图邻接矩阵为对称的，所以只需存入上（下）三角元素即可，空间只需要 n ( n + 1 ) / 2 n(n+1)/2 n(n+1)/2.

7.2.2邻接表

会画，n个链表组成，头指针按顺序存贮，构成顺序表，第i个链表的结点由与顶点i相邻接的顶点组成。

第i个链表结点个数即为顶点i的出度。

n个顶点，e条边的图，邻接表，确定边的个数需要 O ( n + e ) O(n+e) O(n+e)

7.2.3 带权邻接矩阵。

有边记为 w i j w_{ij} wij​,无边为0，

或者有边记为 w i j w_{ij} wij​,自己对自己记为0，无边记为无穷大。

7.3 图的遍历与求图的连通分量 7.3.1 深搜DFS void create_adjust(L_NODE *head[],int n,E_NODE e[],int m){ int i,u,v; L_NODE *p; for(i=1;i int i; for(i=1;i//顶点不为空 if(visit[t->ver]==0)//未被访问过 dfs(t->ver);//递归访问 t=t->link;//下一个 }}

无向图G有n个顶点和m条边，邻接表共有2m个结点，执行时间为O(m);邻接矩阵与某个顶点v邻接的所有顶点O(n)，有n个，所以全部时间为O(n*n)

7.3.2 广搜BFS

程序不考，时间复杂度也为n*n.

首先访问顶点v，然后访问与顶点v邻接的全部顶点，再依次访问以访问的顶点相邻接的全部顶点……

7.4 生成树和最小（代价）生成树

G是连通无向图，G的生成树则是包含G中所有顶点的一个无回路的连通子图。具有n个顶点的连通无向图至少有n-1条边，而其生成树也有n-1条边。

生成树不唯一，最小代价生成树也不唯一。

（1） p r i m prim prim算法——从顶点1开始，让一棵小树长大。

f ( x ) = { 0 x=0 1 x  ≠  0 f(x)= egin{cases} 0& ext{x=0}\ 1& ext{x $ eq$ 0} end{cases} f(x)={01​x=0x ​= 0​

c o s t ( i , j ) = { w i j ( i , j ) ∈ E , i ≠ j , w i j 为 （ i , j ) 上 的 权 0 i = j ∞ 否 则 cost(i,j)=left{ egin{aligned} w_{ij} & & (i,j)in E,i eq j,w_{ij}为（i,j)上的权 \0 & & i=j \ infty & & 否则 end{aligned} ight. cost(i,j)=⎩⎪⎨⎪⎧​wij​0∞​​(i,j)∈E,i​=j,wij​为（i,j)上的权i=j否则​

（2） k r u s k a l kruskal kruskal算法——将森林合并成树

按权递增排序

从最小开始，选取n-1条边，每次添加不能构成回路

7.5 最短路径

路径的开始顶点为源点，最后顶点为终点。路径的长度为该路径各边权之和。

（1）求某个顶点到其他路径的最短路径

void shortsetpath(MAT cost,int n,int v,int dist[],int pre[]){ int s[MAXN],i,j,k,min; for(i=1;i min=MAXINT; k=0; for(j=1;j//dist小于当前最小值且不为0 min=dist[j]; k=j; } } if(k==0) break;//没有与出发相连的顶点 s[k]=1; for(j=1;j int i,j,k; for(i=1;i if(a[i][k]+a[k][j] int k; k=path[i][j]; if(k==0) return; print_path(i,k); printf("%d--->",k); print_path(k,j);} 7.6 拓扑排序

任何没有有向回路的有向图，其顶点可以排成一个拓扑序列。

对AOV网络进行拓扑排序的方法：

1.在网络中选取一个没有前驱的顶点，把它输出。

2.从网络中删除该结点和以它为尾的所有有向边。

重复上述步骤，直到所有顶点都被输出，或者遗留在网络上的顶点都有前驱顶点。