【数据结构与算法】图1

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

2、1 = 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 图的定义和基本术语,顶点 弧 弧尾 弧头,顶点 边,7.1 图的定义和基本术语(续一),完全图：n个顶点有n(n-1)/2条边的无向图 有向完全图： n个顶点有n(n-1)条弧的有向图 稀疏图：有很少条边的图（如边数e nlogn) 稠密图：非稀疏图 权： 与边或弧相关的数 网络： 带权的图,2,7,4,子图： G =(V,E)和G1 = (V1,E1) 若V1属于V

3、, E1属于E 则G1是G的子图,7.1 图的定义和基本术语(续二),邻接点：无向图中有边相连的两个顶点互为邻接点 顶点的度：无向图中和某顶点相连的邻接点数 入度：有向图中指向某顶点的弧的数目 出度：有向图中从某顶点出发的弧的数目,7.1 图的定义和基本术语(续三),路径：两个顶点之间的顶点序列，该序列的每个顶点与其前驱是邻接点，每个顶点与其后继也是邻接点 回路（环）：第一顶点和最后顶点相同的路径 简单路径： 顶点不重复的路径 连通： 两个顶点之间有路径 连通图： 任意两个顶点之间有路径 连通分量： 无向图中的极大连通子图。 强连通图：任意两个顶点之间有双向路径 强连通分量：有向图中的极大强连

4、通子图。 连通图的生成树：极小连通子图。 不唯一，但n个顶点的生成树 有且仅有n-1条边。 生成森林：,7.2 图的存储结构 7.2.1 数组表示法,#define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 typedef enumDG, DN, AG, AN GraphKind; typedef struct ArcCell VRType adj; InfoType *info; ArcCell, AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM typedef struct VetexType vexsMAX_VERT

5、EX_NUM ; AdjMatrix arc; int vexnum, arcnum; GraphKind kind; MGraph;,数组表示法(邻接矩阵),无向图、有向图、网均适用易求各顶点的度。 例如有向图G1和无向图G2的邻接矩阵为,n2的存储量 无向图的邻接矩阵总是对称的-可以采用压缩存储,网及其邻接矩阵,7.2.2 邻接表- 链式存储结构,#define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex; struct ArcNode *nextarc; InfoType *info; ArcNode;,typedef stru

6、ct AdjList verteces; int vexnum, arcnum; int kind; ALGraph;,typedef struct VNode VetexType data; ArcNode *firstarc; Vnode, AdjList MAX_VERTEX_NUM ;,邻接表的链式存储结构示意图,G1的邻接表,G2的邻接表,G1的逆邻接表,邻接表： 求出度容易，求入度难,邻接表： 求入度容易，求出度难,7.3 图的遍历,图的遍历：从图的某顶点出发，访问所有顶点，且每个顶点仅被访问一次。 两种遍历图的路径： 深度优先搜索和广度优先搜索 它们对无向图和有向图都适用 深度优

7、先搜索类似于树的先根遍历 广度优先搜索类似于树的层次遍历,7.3.1 深度优先搜索,V1,遍历顺序：,非连通的图重复上述过程, 使每个顶点均被访问,V1,V2,stack,V4,V8,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

8、) DFS(G,v); void DFS(Graph G, int v) visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w; w = NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); ,7.3.2 广度优先搜索,1 2 3 4 5 6 7 8,遍历顺序：,非连通的图重复上述过程, 使每个顶点均被访问,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(!visitedv) 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 图的连通性问题,7.4.1 无向图的连通分量和生成树,7.4.3 最小生成树,连通网的生成树 一棵生成树的