第七章 图

本章内容 定义和术语 存储结构：邻接矩阵、邻接表，十字链表，邻接多重表 两种遍历策略：深度优先搜索和广度优先搜索 连通性和最小生成树 拓扑排序和关键路径 两类求最短路径问题的解法

本章要点 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系； 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索的两种形式(递归和非递归)和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异； 应用图的遍历算法求解各种简单路径问题。

7.1 图的定义和术语 图G 由两个集合V(G)和E(G)组成，记作G=(V,E) 2 3 4

图的基本术语 顶点(vertex) 弧(arc) 弧头(又称终端点) 弧尾(又称初始点) 边(Edge) 数据元素所构成的结点通常称为顶点。 若两个顶点间有关系<x,y>∈E ，则称<x,y>为一条弧。 弧头(又称终端点) 若<x,y>为一条弧，则顶点 y 称为弧头。 弧尾(又称初始点) 若<x,y>为一条弧，则顶点 x 称为弧尾。 边(Edge) 无向图中两条弧<x,y>和<y,x>可用一条边(x,y)来表示 。

图的基本术语(续) 顶点的度（degree） 顶点的入度（indegree） 顶点的出度（outdegree） 路径（path） 与顶点相关联的边数称为该顶点的度，又分为入度和出度 。 顶点的入度（indegree） 以顶点为头的弧数称为该顶点的入度 。 顶点的出度（outdegree） 以顶点为尾的弧数称为该顶点的出度 。 路径（path） 由顶点vi经过一系列边和顶点到达顶点vj所得到的顶点序列。 回路（loop--又称环 cycle） 起点和终点为同一顶点的路径称为回路。 A B C E F D

图的基本术语(续) 简单路径 简单回路(简单环) 稀疏图 稠密图 权(weight) 网 A B C E F D (路径的顶点)序列中顶点不重复出现的路径。 简单回路(简单环) 除路径起点和终点相同外，其余顶点均不相同的回路。 稀疏图 边数很少的图 (如e<nlogn)。 稠密图 边数很多的图。 权(weight) 有些图的边或弧具有一定的大小，称之为权。 网 带权值的图又称为网或网络。 A B C E F D

图的基本术语(续) 子图 生成子图 邻接点 依附 相关联 由图的部分顶点和边组成的新图称为原图的子图。 由图的全部顶点和部分边组成的子图称为原图的生成子图。 邻接点 若边(vi,vj)∈E，则 vi与vj互为邻接点。 依附 若边(vi,vj)∈E ，则称边(vi,vj)依附于顶点vi和vj。 相关联 若边(vi,vj)∈E ，又称边(vi,vj)与顶点vi和vj相关联。

图的基本术语(续) 有向图 无向图 完全图 有向完全图 若<x,y>∈E ，并不总有<y,x>∈E，则称此图为有向图。 无向图 若<x,y>∈E ，总有<y,x>∈E，则称此图为无向图。 完全图 具有 n*(n-1)/2条边的无向图称为完全图。 有向完全图 具有 n*(n-1)条弧的有向图称为有向完全图。

图的基本术语(续) 连通 连通图 连通分量 强连通图 强连通分量 无向图中顶点vi到vj间有路径存在，则称vi和vj是连通的。 无向图中任意两顶点间均存在路径，则称该图为连通图。 连通分量 无向图中的极大连通子图称为原图的连通分量。 强连通图 有向图中任意两顶点间均存在路径，则称该图为强连通图。 强连通分量 有向图中的极大强连通子图称为原图的强连通分量。

图的基本术语(续) 生成树 有向树 生成森林 最小代价生成树 连通图的极小连通生成子图称为原图的生成树。 恰有一个顶点入度为0 ，其余顶点入度均为1的有向图。 生成森林 由多棵有向树构成的有向图的生成子图称为生成森林。 最小代价生成树 连通网中由最小权值的边构成的生成树。

图的基本操作 图的生成操作 CreatGraph(&G,V,VR) 顶点定位函数 LocateVex(G,v) 取顶点数据函数 GetVex(G,v) 求第一个邻接顶点函数 FirstAdjVex(G,v) 求下一个邻接顶点函数 NextAdjVex(G,v,w) 插入顶点操作 InsertVex(&G,v) 删除顶点操作 DeleteVex(&G,v) 插入边/弧的操作 InsertArc(&G,u,v) 删除边/弧的操作 DeleteArc(&G,u,v) 图的遍历 Traverse(G)

{ 图的存储结构:邻接矩阵 数组表示法 A B C E F D 邻接矩阵(优缺点) Aij = 0 (vi,vj) ∈E #define Infinity INT_MAX typedef enum{DG, DN, AG, AN} GraphKind; typedef struct ArcCell{ VRType adj; InfoType *info; }ArcCell, AdjMatrix[20][20]; typedef struct Gragh{ VertexType vexs[20]; int vtxnum, arcnum; AdjMatrix arcs; GraghKind kind; } Gragh; A B C D E F 0 0 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 A B C D E F

{ 图的存储结构：邻接矩阵 邻接矩阵(边表)arcs  3 2     4  5     2  3 A B C D Aij = {  (vi,vj) ∈E 权值 (vi,vj) ∈E 2 5 4 2 邻接矩阵(边表)arcs  3 2  　    4  5     2 

{ 图的存储结构:关联矩阵 关联矩阵 A B C E F D e1 e2 e3 e4 e5 e6 e7 Bij = 1 vi 是 ej 的弧头 0 vi 与 ej 不相关联 -1 vi 是 ej 的弧尾 e1 e2 e3 e4 e5 e6 e7 1 0 0 0 0 0 -1 -1 -1 0 0 1 0 0 0 1 -1 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 1 -1 1 0 0 0 0 0 0 -1 1 A B C D E F

图的存储结构:邻接表 邻接表(有向图) A B C E F D 按结点出度建立; firstarc data 头结点 adjvex 12 3 邻接表(有向图) 按结点出度建立; A B C E F D 2 5 7 16 firstarc data 头结点 adjvex weight nextarc 弧结点 23 9 typedef struct ArcNode { int adjvex; InfoType weight; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ VertexType data; ArcNode *firstarc; }VNode, Adjlist[20]; typedef struct { AdjList vertices; int vexnum; }AlGraph;

链式存储结构(续) 逆邻接表 按结点入度建立; A B C E F D 2 3 1 4 E 4 B 1 C 2 D 3 F 5 ∧ A firstarc vexdata 头结点 adjvex info nextarc 弧结点 E 4 B 1 C 2 D 3 F 5 ∧ A

链式存储结构(续) 十字链表 A B C E F D D 3 ∧ 4 A 5 B 1 2 E F C 按结点入度和出度建立； tailvex headvex hlink 弧结点 tlink firstout data 头结点 firstin typedef struct ArcBox{ int tailvex,headvex; struct ArcBox *hlink,*tlink; }ArcBox; typedef struct VexNode{ VertexType data; ArcBox *firstin,*firstout; }VexNode; typedef struct { VerNode xlist[20]; int vexnum,arcnum; }OLGraph; D 3 ∧ 4 A 5 B 1 2 E F C

链式存储结构(续) 邻接多重表 是无向图的一种存储结构 存储无向图用十字链表法的问题 data 头结点 firstedge ivex 边结点 ilink jvex jlink #define MAX_VEX_NUM 20 struct EBox{ EdgeType data; int ivex, jvex; struct EBox *ilink, *jlink; }; typedef struct VexBox{ VertexType data; struct EBox *firstedge; }VexBox; typedef struct { VexBox vex[MAX_VEX_NUM]; int nvex, nedge;

7.3 图的遍历 图的遍历 按某种搜索顺序对图中每个结点访问且仅访问一次。 遍历图的两种方式 深度优先搜索 DFS 广度优先搜索 BFS

深度优先搜索 类似树的先根边历 从图中某顶点 v0 出发，访问该顶点 依次从v0未被访问过的邻接点中选取一个顶点作为新的出发点，用同样的方法访问其它所有顶点；直到所有与v0 连通的顶点均被访问到为止 若仍有顶点未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点； 反复此过程，直至图中所有顶点均被访问过一遍为止 A B C E F G D H A B F E H C D G

深度优先搜索算法 void DFS( Graph G, int v ) { Visit( v ); visited[v] = 1; int visited[MAX]; void DFSTraverse (Graph G) { for (v = 0; v < G.vexnum; v++) visited[v] = 0; /* memset(visited, 0, sizeof(visited) */ for (v = 0; v < G.vexnum; v++) if (!visited[v]) DFS(G, v); } void DFS( Graph G, int v ) { Visit( v ); visited[v] = 1; for (w = FirstAdjVex(G,v); w; w = NextAdjVex(G, v, w)) if (!visited[w]) DFS(G, w); }

广度优先搜索 A B C E F G D H A B C F H D G E 类似树的按层次遍历 从某顶点v0出发，访问该顶点 若此时仍有顶点尚未被访问，则从未被访问过的顶点中任意选取一个顶点作为新的出发点； 反复此过程，直至图中所有顶点均被访问过一遍为止。 A B C E F G D H A B C F H D G E

广度优先搜索算法 void BFSTraverse ( Graph G) { memset(visited, 0 , sizeof(visited)); InitQueue(Q); for (v = 0; v < G.vexnum; v++) { if (visited[v]) continue; EnQueue(Q, v); while (!QueueEmpty(Q)) { u = DeQueue(Q); visited[u] = 1; Visit(u); for (w = FirstAdjVex(G,u); w; w=NextAdjVex(G, u, w)) if (!visited[w]) EnQueue(Q, w); }

无向图的连通分量和生成树 无向图的连通分量 生成树 从图中任一顶点出发，一次调用深度或广度优先搜索所得到的顶点集即为连通分量中的顶点集。 连通分量中的节点，连同遍历时走过的边，构成图的生成树 非连通图，多个生成树，形成生成森林

遍历图构成图的生成森林 以孩子-兄弟链表作为生成森林的存储结构 struct CSNode *root; int visited[N]; void DFS_Forest(Graph G) { struct CSNode *last_sibling; root = NULL; memset(visited, 0, sizeof(visted)); for (v = 0; v < G.vexnum; v++) { if (visited(v)) continue; p = malloc(sizeof(CSNode)); *p = { GetVex(G,v), NULL, NULL }; if (root == NULL) root = p; else last_sibling->next_sibling = p; last_sibling = p; DFSTree(G, v, p); }

遍历图构成图的生成森林(续) void DFSTree(Graph G, int v, CSTree T) { struct CSNode *last_sibling = NULL; visited[v] = TRUE; for (w = FirstAdjVex(G,v); w; w = NextAdjVex(G, v, w)) { if (visited(w)) continue; p = malloc(sizeof(CSNode)); *p = { GetVex(G, w), NULL, NULL }; if (last_sibling == NULL) T->child = p; else last_sibling->next_sibling = p; last_sibling = p; DFSTree(G, w, p); }

遍历图构成生成森林算法改写 void DFS_Forest(Graph G) { root = NULL; pp = &root; memset(visted, 0, sizeof(visted)); for (v = 0; v < G.vexnum; v++) { if (visted(v)) continue; *pp = p = malloc(sizeof(CSNode)); *p = { GetVex(G,v), NULL, NULL }; pp = &p->next_sibling; DFSTree(G, v, &p->child); }

遍历图构成生成森林算法改写(续) void DFSTree(Graph G, int v, struct CSNode **t) { visited[v] = TRUE; pp = t; for (w = FirstAdjVex(G,v); w; w = NextAdjVex(G, v, w)) { if (visited(w)) continue; *pp = p = malloc(sizeof(CSNode)); *p = { GetVex(G, w), NULL, NULL }; pp = &p->next_sibling; DFSTree(G, w, &p->child); }

遍历图构成生成森林C++算法(1) void DFS_Forest(Graph G) { struct CSNode *&ptr = root; root = NULL; memset(visted, 0, sizeof(visted)); for (v = 0; v < G.vexnum; v++) { if (visted(v)) continue; ptr = malloc(sizeof(CSNode)); *ptr = { GetVex(G,v), NULL, NULL }; DFSTree(G, v, ptr->child); ptr = ptr->next_sibling; }

遍历图构成生成森林C++算法(2) void DFSTree(Graph G, int v, struct CSNode *&ptr) { visited[v] = TRUE; for (w = FirstAdjVex(G,v); w; w = NextAdjVex(G, v, w)) { if (visited(w)) continue; ptr = malloc(sizeof(CSNode)); *ptr = { GetVex(G, w), NULL, NULL }; DFSTree(G, w, ptr->child); ptr = ptr->next_sibling; }

最小生成树 定义 性质： 构造算法 由一个网络生成的各边的权数总和最小的生成树 记为MST 设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，若(u,v)[uU,vV-U]是一条具有最小权值(代价)的边，则必存在一棵包含边(u,v)的最小生成树 构造算法 Prim算法 Kruskal算法

Prim算法 将图中顶点分为两个集合，其中集合 X 包含图的一个顶点 v0，集合 Y 包含除 v0 外的其它所有顶点； 将跨接这两个集合的权值最小的边加入图中，并将其依附在集合 Y 中的顶点 v1 从 Y 中移入集合 X 中； 反复过程 2，直到集合 Y 为空，所得生成子图即为最小生成树。 教材图7.16,结构数组closedge， 数组每元素两个分量adjvex,lowcost 算法复杂性O(n2) A B C E F D 2 3 1 A B C E F D 2 1 2 1 3

Prim算法描述 void MinSpanTree_PRIM(MGraph, G, VertexType u) { /* cost为NxN矩阵，cost[i][j]存储节点i到节点的边的权值 */ k = LocateVex(G, u); for (j = 0; j < G.vexnum; j++) if (j != k) closedge[j] = {k, cost[k][j] }; closedge[k].lowcost = 0; /* k在已完成的集合中 */ for (i = 1; i< G.vexnum, i++) { k = min(closedge); /* 从lowcost>0节点中挑最小的节点 */ printf(closedge[k].adjvex, k); /* 输出边的两个端点的编号 */ closedge[k].lowcost = 0; /* k号节点并入已完成集合*/ /* 考虑新加入的节点k, 修正closedge */ if (cost[k][j] < closedge[j].lowcost) closedge[j] = { k, cost[k][j] }; }

Kruskal 算法 将图中所有边按权值从小到大排序； 取权值最小的边，加入图中，判断是否形成了回路，若无，则保留此边，否则去掉该边，重取权值较小的边； 反复过程 2，直到全部顶点均连通为止。 算法复杂性O(e*loge) A B C E F D 2 3 1 1 A F C D 2 B E 3 A B C E F D 2 1 2 1 3 2

其它算法 破圈法 去边法 A B C E F D 2 3 1 A B C E F D 2 1 3 2 1 2 1 1 3 2 3 1 2 3 在图中找到一个回路； 去掉该回路中权值最大的边； 反复此过程，直到图中不存在回路为止。 去边法 将图中所有边按权值从大到小排序； 去掉权值最大的边，若图不再连通则保留此边，再选取下一权值较大的边去掉； 反复此过程，直到图中只剩下 n-1 条边为止。 A B C E F D 2 3 1 A B C E F D 2 1 3 2 1 2 1 1 3 2 3 1 2 3 2

7.5 有向无环图及其应用 有向无环图 一个无环的有向图，简称DAG （Directed Acycline Graph） 是描述含有公共子式的表达式的有效工具； 实现对公共子式的共享，节省存储,节约时间； 是描述一项工程或系统的进行过程的有效工具。 所有的工程都可分为若干个称为活动的子工程，子工程之间受一定条件的约束； 评估工程能否顺利进行－－拓扑排序； 估算整个工程完成所必须的最短时间－－关键路径；

拓扑排序 拓扑排序 AOV 网(Activity On Vertex) 由某集合上的偏序得到该集合上的一个全序的过程 有向边表示两个活动间的次序关系 顶点表示活动 这类图又称为顶点活动图，简称 AOV 图。 如用顶点表示课程，用弧表示某些课程是其它课程的先修课，则拓扑排序就是求在同时只能学习一门课程时的学习次序。

拓扑排序的步骤 C1C2C3C4C5C6C7C8C9C10 C2C1C3C4C5C6C7C8C9C10 扫描图中每个顶点，将入度为零的顶点入队列； 从队列中取出一个顶点输出，并将其所有邻接点的入度减 1 ，若入度减为零，则将该邻接点入队列； 反复执行步骤 2，直至所有顶点的入度均为零。 若该有向图不是无环图，则不存在拓扑排序，就不可能输出全部顶点。此特点可用来判断一个有向图是否存在回路。 C1 C2 C3 C6 C4 C5 C7 C8 C9 C10 拓扑排序结果： C1C2C3C4C5C6C7C8C9C10 C2C1C3C4C5C6C7C8C9C10 C1C2C4C3C5C6C7C8C9C10 C2C1C4C3C5C6C7C8C9C10 C1C2C5C4C3C6C7C8C10C9

拓扑排序算法描述 Status TopologicalSort(ALGraph G) { FindInDegree(G, indegree); InitStack(S); for (i = 0; i< G.vexnum; i++) if (indgree[i]==0) push(S,i); count = 0; while (!StackEmpty()) { i = pop(S); print_vex(i); count ++; for (p = G.vex[i].firstarc; p; p = p->nextarc) { k = p->adjvex; if (--indegree[k] == 0) push(S,k); } return count < G.vexnum ? ERROR : ok;

关键路径 源点 汇点 关键活动 关键路径 AOE图 (Activity On Edge) AOE网的性质 入度为0的顶点，即工程的开始点； 出度为0的顶点，即工程的完成点； 关键活动 关键路径上的活动，关键活动的加快可以缩短工期； 关键路径 影响整个工程进度的那些活动所组成的路径 减少这些活动所需时间，整个工程就可能提前完成。 AOE图 (Activity On Edge) 顶点一般用来表示事件(状态) 弧用来表示活动 弧的权值表示活动所需时间 此类有向无环图称AOE图 AOE网的性质 进入Vi的活动都结束， Vi所代表的事件才能发生 顶点Vi所代表的事件发生，从Vi出发的活动才能开始

关键路径的提出 V1 V2 V3 66 V4 V5 V7 V8 V9 V10 a1=4 a2=3 a3=2 a4=3 a5=3 a6=5 如左图所示工程，其最后完工时间为21天。 能否加快某些活动进度，使整个工期缩短呢？ 确定关键路径的变量 e(i):活动ai的最早开始时间，活动ai的弧尾事件的最早发生时间。 l(i):活动ai的最迟开始时间，在不影响总工期的前提下，活动ai最迟必须开始进行的时间。 ve(i):事件vi的最早发生时间，从V1到事件Vi的最长路径长度。 vl(i):事件vi的最迟发生时间，从Vi到事件Vn的最长路径。 关键活动：l(i)=e(i)的活动；

关键路径的确定 1.公式：设活动 ai = 弧<Vj,Vk>的权定义为活动的持续时间dut(<j,k>)，则有下式成立：e(i) = ve(j)，l(i) = vl(k)-dut(<j,k>)。若e(i) = l(i) ，则活动 ai就是关键路径上的关键活动。 2.求ve(i): 用拓扑排序求各事件的最早发生时间，有： ve(j) = Max{ve(i)+dut(<i,j>)} , <i,j>∈T， 2≤j≤n， T为所有以 j 为头的弧的集合，初始条件 ve(1) = 0。 i 3.求vl(i):用逆拓扑排序求各事件的最晚发生时间，有： vl(i) = Min{vl(j)-dut(<i,j>)} ， <i,j>∈S， 1≤i≤n-1， S为所有以 i 为尾的弧的集合，初始条件vl(n) = ve(n)。 j

ve： vl： e： l： V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 a1=4 a2=3 a3=2 a4=3 a5=3 a6=5 a9=5 a12=5 a7=4 a8=6 a10=2 a11=1 a13=8 a14=5 V1 V2 V3 V4 V5 V6 V7 V8 V9 V10 (a1a2a3) (a4) (a5a6) (a7) (a8) (a9a10) (a11a13) (a12) (a14) ve： 4 3 2 7 8 13 10 15 21 vl： 4 3 4 7 8 13 11 16 21 e： (0 0 0) (4) (3 3) (2) (7) (8 8) (13 13) (10) (15) 21 l： (0 0 2) (4) (4 3) (4) (7) (8 9) (15 13) (11) (16) 21 关键活动： a1、a2、a4、a6 、a8 、a9 、a13； 关键路径： V1V2V5V7V10 和 V1V3V6V7V10 。

求关键路径的算法 Status TopologicalOder(ALGraph G, Stack &T) { FindInDegree(G, indegree); InitStack(S); count = 0; InitStack(T); memset(ve, 0, sizeof(ve)); for (i = 0; i< G.vexnum; i++) if (indgree[i]==0) push(S,i); while (!StackEmpty(S)) { i = pop(S); count ++; push(T,i) for (p = G.vex[i].firstarc; p; p = p->nextarc) { k = p->adjvex; if (--indegree[k] == 0) push(S, k); if (ve[k] < ve[i] + p->dut) ve[k] = ve[i] + p->dut; } return count < G.vexnum ? ERROR : OK;

求关键路径的算法(续) Status CriticalPath(ALGraph G) { if (!TopologicalOrder(G, T) return ERROR: memcpy(vl, ve, sizeof(ve)); /* vl = ve; */ while (!StackEmpty(T)) { i = pop(T); for (p = G.vex[i].firstarc; p; p = p->nextarc) { k = p->adjvex; if (vl[i] > vl[k] – p->dut) vl[i] = vl[k] – p->dut; } for (i = 0; i < G.vexnum; i++) e = ve[i]; l = ve[k] –p->dut; if (e == l) print_edge(i, k);

单源最短路径 ---迪杰斯特拉(Dijkstra)算法 每一对顶点间的最短路径 ---弗洛伊德(Floyd)算法 7.6 最短路径 单源最短路径 ---迪杰斯特拉(Dijkstra)算法 每一对顶点间的最短路径 ---弗洛伊德(Floyd)算法

从某点到其余顶点的最短路径 Dijkstra算法（最小路径生成树） （按路径长度递增的次序产生最短路径） 从源点的所有邻接点中找出距源点最近的邻接点； 以该邻接点为中间点，比较其它各顶点与源点的路径通过中间点后是否更短；若是： 用新路径代替老路径，再从中找出其它各点距源点最近的顶点作为新的中间点，这也是该点的最短路径； 反复此过程，直至全部顶点距源点的最短路径均找到

例:求图中 v1到各点的最短路径 V1 V2 V3 V4 V5 6 ∞ ∞ 2 V1 V1 V1 V1 5 3 5 V5 V5 V5 4 5 6 ∞ ∞ 2 V1 V1 V1 V1 5 3 5 V5 V5 V5 4 5 V3 V5 5 V5 V1 到各点的最短距离为： 4 、3 、5 和 2； V1 到各点的最短路径为： V1V5V3V2 、 V1V5V3 、 V1V5V4和V1V5 。该方法的时间复杂度为 O(n2)。

最短路径：Dijkstra算法 void ShortestPath_DIJ(int v0) { for (v = 0; v < vexnum; v++) { vex[v].visted = 0; vex[v].distance = arcs[v0][v]; vex[v].plink = arcs[v0][v] < INFINITY ? &vex[v0] : NULL; } vex[v0].distance = 0; vex[v0]. visted = 1; vex[v0].plink = NULL; for (;;) { /* 在未访问节点集合中挑选一个离源点最近的节点v*/ min = INFINITY; for (w = 0; w < vexnum; w++) if (!vex[w].visted && vex[w].distance < min) { v = w; min = vex[w].distance; } if (min == INFINITY) break; vex[v].visted = TRUE; /*考虑新加入节点V之后，其他节点到源点的可能最短路径 */ if (!vex[w].visit && (min + arcs[v][w] < vex[w].distance)) { vex.distance = min + arcs[v][w]; vex[w].plink = &vex[v]; 结果：单向链表vex[i].plink链为节点i最短路径的逆序， vex[i].distance为路径长度

作业(1) 设一个无向图含n个节点e条边，分析邻接矩阵和邻接表存储该图的空间复杂度。 给出下面无向图的邻接矩阵和邻接表，分别计算两种方法所占用的存储空间(假定所有指针、整数和数据均占4字节)。 什么是图的最小代价生成树？分别按Prim算法和Kruscal算法求下图的最小代价生成树。 写出从顶点a出发DFS和BFS遍历所得到的顶点序列。 a b c e f d 2 3 1 4 g h

作业(2) 含有5个节点{A,B,C,D,E}的有向图的邻接矩阵： 0 100 30  10  0     60 0 20  0 100 30  10 　  0     60 0 20   10  0     50 0 画出逻辑图，画出图的十字链表存储结构。 设以邻接矩阵作为一个有向图的存储结构，编写算法判断该图中是否含有环路？

作业(3) AOV网络和AOE网络中，节点和边分别表示什么？列出下列AOE网络中各个事件的最早发生时间和最迟发生时间，找出关键路径并指出完成该工程所需要的最短时间。 V1 V2 V3 V6 V4 V5 V7 V8 V9 V10 a1=4 a2=3 a3=2 a4=3 a5=3 a6=5 a9=5 a12=5 a7=4 a8=6 a10=2 a11=1 a13=8 a14=5

作业(3) 利用Dijkstra算法求出下图从顶点V1到其他各个顶点的最短路径和路径长度，写出执行算法过程中各步的状态。 含有N个节点的无向图G用邻接矩阵A存储。对于G中的某节点v，如果从G中删除顶点v以及与顶点v相关联的边之后，G变成由两个或者两个以上的非空连同分量所组成的图，则称v是图G的关节节点。例如右图中只有节点4和6是关节节点，而其他节点都不是。设计在图G中寻找所有关节节点的算法，并且分析所设计算法的时间复杂度，然后，用C语言编写实现这一算法的程序。 V1 V2 V3 V4 V5 3 2 1 6

作业(4) 自选存储结构，编写一算法判断无向图中任意给定的两个顶点间是否存在一条长度等于k的简单路径(即不含回路的路径)。 2/5/6/9/10

上机作业(选作) 设计邻接表结构存储有向图 增加和删除带权的边 DFS遍历图 最小生成森林及费用 给定两顶点，求最短路径长度及途中的节点名