数据结构与算法图1

1、第七图图b 7.1 图的定义和基本术语b 7.2 图的存储结构 7.2.1数组表示法 7.2.2邻接表 7.2.3十字链表 7.2.4邻接多重表b 7.3 图的遍历 7.3.1 深度优先搜索 7.3.2 广度优先搜索b 7.4 图的连通性问题 7.4.1 无向图的连通分量和生成树 7.4.2 最小生成树b 7.5 有向无环图及其应用 7.5.1 拓扑排序 7.5.2 关键路径b 7.6 最短路径 7.6.1 从某个源点到其余各顶点的最短路径 7.6.2 每一对顶点间的最短路径b图图(graph)是较线性表和树更为复杂的结构。b图图中任意数据两个元素之间都可能相关。第七图图 g1 = (v1,

2、a1) v1 = v1,v2,v3,v4 a1 = , g2 = (v2, e2) v2 = v1,v2,v3,v4,v5 e2 = (v1,v2),(v1,v4),(v2,v3),(v2,v5) ,(v3,v4),(v3,v5) 7.1 图的定义和基本术语v1v3v4v2有向图 g1v1v4v5v2无向图 g2v3 顶点 弧 弧尾 弧头顶点边7.1 图的定义和基本术语(续一) 完全图：完全图：n个顶点有n(n-1)/2条边的无向图 有向完全图：有向完全图： n个顶点有n(n-1)条弧的有向图 稀疏图：有稀疏图：有很少条边的图（如边数e nlogn) 稠密图：稠密图：非稀疏图 权：权： 与边或

3、弧相关的数数 网络：网络： 带权的图v1v3v2v1v3v2274 子图：子图： g =(v,e)和g1 = (v1,e1) 若v1属于v, e1属于e 则g1是g的子图7.1 图的定义和基本术语(续二)v1v1v3v4v2v3v1v3v4v1邻接点：无向图中有边相连的两个顶点互为无向图中有边相连的两个顶点互为邻接点 顶点的度：度：无向图中和某顶点相连的邻接点数无向图中和某顶点相连的邻接点数 入度：入度：有向图中指向某顶点的弧的数目有向图中指向某顶点的弧的数目 出度：出度：有向图中从某顶点出发的弧的数目有向图中从某顶点出发的弧的数目7.1 图的定义和基本术语(续三) 路径：路径：两个顶点之间的

4、顶点序列，该序列的每个顶点与其前驱是邻接点，每个顶点与其后继也是邻接点 回路（环）：回路（环）：第一顶点和最后顶点相同的路径 简单路径：简单路径： 顶点不重复的路径 连通：连通： 两个顶点之间有路径 连通图：连通图： 任意任意两个顶点之间有路径 连通分量：连通分量： 无向图中的极大连通子图。 强连通图：任意强连通图：任意两个顶点之间有双向路径 强连通分量：强连通分量：有向图中的极大强连通子图。 连通图的生成树：生成树：极小连通子图。 不唯一，但n个顶点的生成树 有且仅有n-1条边。 生成森林：生成森林： 7.2 图的存储结构 7.2.1 数组表示法#define infinity int_ma

5、x#define max_vertex_num 20typedef enumdg, dn, ag, an graphkind;typedef struct arccell vrtype adj; infotype *info;arccell, adjmatrixmax_vertex_num max_vertex_num typedef struct vetextype vexsmax_vertex_num ; adjmatrix arc; int vexnum, arcnum; graphkind kind;mgraph;数组表示法(邻接矩阵)b无向图、有向图、网均适用易求各顶点的度。b例如有

6、向图g1和无向图g2的邻接矩阵为0 1 1 00 0 0 00 0 0 11 0 0 0g1.arc =0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0g2.arc =n2的存储量无向图的邻接矩阵总是对称的-可以采用压缩存储邻接矩阵v1v3v4v2v5v65489731565(a) 网 5 7 4 8 9 5 6 5 3 1 (b) 邻接矩阵7.2.2 邻接表- - 链式链式存储结构#define max_vertex_num 20typedef struct arcnode int adjvex; struct arcnode *nextarc; i

7、nfotype *info;arcnode;typedef struct adjlist verteces; int vexnum, arcnum; int kind;algraph;typedef struct vnode vetextype data; arcnode *firstarc; vnode, adjlist max_vertex_num ;data firstarc头结点adjvex nextarc info表结点邻接表的链式链式存储结构示意图0123v1v2 v3v40123v1v2v3v401234v1v2v3v4v52 1 3 3 0 0 2 0 3 1 2 0 2 1

8、2 0 4 3 1 4 g1的邻接表g2的邻接表g1的逆邻接表邻接表：邻接表：求出度容易，求入度难邻接表：邻接表：求入度容易，求出度难7.3 图的遍历b图的遍历：从图的某顶点出发，访问所有顶点，且每个顶点仅被访问一次。b两种遍历图的路径：b深度优先搜索和广度优先搜索b它们对无向图和有向图都适用b深度优先搜索类似于树的先根遍历b广度优先搜索类似于树的层次遍历7.3.1 深度优先搜索v1v2v4v5v8v3v6v7v1v2v4v8v5v3v6v71 2 3 4 5 6 7 8visited1 1 0 1 1 0 0 1遍历顺序：非连通的图重复上述过程, 使每个顶点均被访问v1v2stackv4v8

9、v5深度优先搜索算法boolean visitedmax;status (* visitfunc)(int v);void dfstraverse(graph g, status (* visit)(int v) visitfunc = visit; for(v=0; vg.vexnum; +v) visitedv = false; for(v=0; vg.vexnum; +v) if(!visitedv) dfs(g,v);void dfs(graph g, int v) visitedv = true; visitfunc(v); for(w=firstadjvex(g, v); w; w

10、 = nextadjvex(g,v,w) if(!visitedw) dfs(g,w);7.3.2 广度优先搜索v1v2v4v5v8v3v6v7v1v2v3v4v5v6v7v81 2 3 4 5 6 7 8visited1 0 0 0 0 0 0 0v2v3queue遍历顺序：非连通的图重复上述过程, 使每个顶点均被访问void bfstraverse(graph g, status (* visit)(int v) for(v=0; vg.vexnum; +v) visitedv = false; intiqueque(q); for(v=0; vg.vexnum; +v) if(!visi

11、tedv) enqueue(q,v); while(!queueempty(q) dequeue(u); visitedu = true; visit (u); for(w=firstadjvex(g, u); w; w = nextadjvex(g,u,w) if(!visitedw) visitedw=true; visited(w); enqueue(g,w); 广度优先搜索算法7.4 图的连通性问题b7.4.1 无向图的连通分量和生成树v1v2v4v5v8v3v6v7深度优先生成树v1v2v4v5v8v3v6v7广度优先生成树7.4.3 最小生成树-树上各边的代价之和b最小生成树- 一个v1v2v4v5v3v66555662134v1v2v4v5v3v61v1v2v4v5v3v614v1v2v4v5v3v6