《软件技术基础_图课件》由会员分享，可在线阅读，更多相关《软件技术基础_图课件（30页珍藏版）》请在金锄头文库上搜索。
1、1.3.3 图,一、图的定义和术语 1、定义： 由非空的顶点有穷集和边的有穷集组成。 记为G（V，E） V：顶点集，非空 E：边集，可以是空集 (此时，只有顶点没有边),图中数据元素之间的关系可以是任意的！,2、术语： 有向图与无向图 有向图：图中每条边都有方向有向边以表示又称为弧，弧尾： Vi 弧头： Vj,无向图： 由无向边组成 以(Vi ，Vj )表示,有向图,无向图,邻接：若(Vi，Vj)E，则Vi与Vj互为邻接； 若为有向边，则Vj是Vi的邻接点。 顶点的度D(Vi)： 有向图： 出度：以该顶点为弧尾的弧的数目 入度：以该顶点为弧头的弧的数目 顶点的度 = 出度+入度 无向图：以该顶
2、点为一个端点的边的条数。,路径：从一个顶点到另一个顶点的顶点序列,如图中V1到V4的路径有： V1V2 V3 V4 V1 V3 V4 V1 V5 V4,第一个顶点与最后一个顶点相同的的路径称为环，如： V1 V2 V3 V1,连通与连通图： 在图中若两个顶点之间有路径，则称这两个顶点是连通的。任意两个顶点都连通的图称为连通图。 强连通图：有向图的每一对顶点之间相互都存在路径。,权与网： 图中边或弧所具有的相关数称为权，表明从一个顶点到另一个顶点的距离或耗费。 带权的图称为网（或网络）。,二、图的存储 1.邻接矩阵法(数组实现)： 给顶点编号 建立关系矩阵： aij的值表示j号顶点是否为i号顶点
3、邻接点。,顶点的出度为该行的元素之和 顶点的入度为该列的元素之和,无向图的邻接矩阵是对称矩阵， 顶点Vi的度是i行（或列）的元素之和。,权值图的邻接矩阵： aij的值表示边或弧aij的权。,图的邻接矩阵C语言描述： #define MAXNUM 20 typedef struct elemtype nodeMAXNUM; int arcsMAXNUMMAXNUM; graph;,MAXNUM：图中顶点的最大数目,node ：表示顶点集,arcs ：表示邻接矩阵,邻接矩阵的优点： 增减边的操作简单，修改arcsij的值就行了； 邻接矩阵的缺点： 增减顶点的操作需搬移大量元素； 存储空间的浪费：
4、若边 顶点2 ，则邻接矩阵为稀疏矩阵,2.邻接表法（链式存储）：,每个顶点建立一个单链表： 单链表中的结点是该顶点的所有邻接顶点,邻接表中包含两种结点：,邻接表的优点： 节省空间、操作较简便,邻接结点的类型定义： typedef struct node int nodeindex; struct node *nextadj; adjnode;,指向下一个与头结点相邻接的顶点,邻接表的类型定义：,typedef struct headnode nodelist MAXNUM; int nodenum; graphlist;,头结点的类型定义： typedef struct int nodeind
5、ex; elemtype data; adjnode *nextadj; headnode;,指向与头结点相邻接的顶点,用一维数组存储头结点,有向图的邻接表,三、图的遍历 定义： 从某个顶点出发，对图中所有顶点作且只作一次访问。,问题： 1）对于任一个图，从一个顶点出发沿着所有的路径是否可以将所有的顶点遍历到？ 2）图中有回路，遍历算法可能产生死循环，如何避免？,为了避免重复访问同一顶点，设一辅助数组记住每个顶点的状态： visited顶点号=,只有连通图才能从一个顶点出发访问到图中所有顶点 图的遍历是其他操作的基础 图的遍历有两种方法：深度优先遍历与广度优先遍历,1、深度优先遍历（depth
6、-first search，dfs）,从一个未访问过的顶点开始，先访问此顶点，再选取该顶点的一个未访问的邻接点。 然后访问该邻接点，再选取该邻接点的未访问的邻接点； 若某顶点的所有邻接点都已访问过，则回溯到之前的一个顶点，选取它的另一个未访问的邻接点 步骤、是递归的,深度优先遍历序列：,V1,V2,V3,V4,V5,1）设立一维数组记录顶点的访问状态：,2）实现回溯：用递归或栈,3）图以邻接表的方式存储,算法实现分析：,void maindfs(graphlist *graph, int v)initialize visited ;dfs(graph,v);,void dfs(graphlis
7、t *graph, int v)visitedv=true;p=graph-nodelistv -nextadj ;while(p!=NULL) w = p -nodeindex;if (visitedw=false)dfs( graph, w );p=p-nextadj;,/*递归深度优先遍历*/,void dfs（g ，v） visited v = 1; p = g v -nextadj while(p != NULL) w = p-nodeindex; if(visited w = 0) dfs( g, w ); p = p-nextadj; ,void dfs（g ，2） visite
8、d 2 = 1; p = g 2 -nextadj while(p != NULL) w = p-nodeindex; if(visited 3 = 0) dfs( g, 3 ); p = p-nextadj; ,void dfs（g ，3） visited 3 = 1; p = g 3 -nextadj while(p != NULL) w = p-nodeindex; if(visited 4 = 0) dfs( g , 4 ); p = p-nextadj; ,void dfs（g ，4） visited 4 = 1; p = g 4 -nextadj while(p != NULL)
9、w = p-nodeindex; if(visited w = 0) dfs( g , w ); p = p-nextadj; ,void dfs（g ，5） visited 5 = 1; p = g 5 -nextadj while(p != NULL) w = p-nodeindex; if(visited w = 0) dfs( g , w ); p = p-nextadj; ,void dfs（g ，1） visited 1 = 1; p = g 1 -nextadj while(p != NULL) w = p-nodeindex; if(visited 2 = 0) dfs( g,
10、 2 ); p = p-nextadj; ,if(visited 5 = 0),dfs( g , 5 );,2、广度优先遍历（breadth-first search，bfs),访问顶点v后，依次访问v的所有邻接点，再依次访问这些邻接点的邻接点，直至所有的顶点都被访问过。 例：,广度优先遍历序列：,V1,V2,V5,V3,V1的邻接点,V2的邻接点,V4,用队列辅助操作：,v1,v2,v4,v5,v3,1）需设立一维数组记录顶点的访问状态,2）利用队列辅助操作： 访问顶点v时v入队列；当队列不为空时，对头元素出队列（顶点v），此时依次访问v的所有邻接点，并将这些邻接顶点入队列；不断将顶点出队、
11、入队，直到队列为空时结束。,3）图以邻接表的方式存储,算法实现分析：,void bfs(graphlist * graph, int v) initialize visited ;setnull (Q);visit v;visitedv=true;enqueue(Q,v); while(!empty(Q) v = dequeue(Q); p = ,/*连通图的bfs*/,/*v进入队列Q*/,/*从顶点v开始访问*/,/*置已访问标记*/,/*出队*/,while(adjp!=NULL)if (visitedadjp-nodeindex=false)v=adjp-nodeindex;visit
12、 v;visitedv=true;enqueue(Q,v);adjp=adjp-nextadj; /*end of while(!empty(Q)*/ ,/*访问v的所有邻接点*/,四、生成树与最短路径,生成树定义： 树的结点与图的顶点一一对应，树的分支全部由图的边构成，称这棵树为这幅图的生成树。,最小费用生成树： 所有生成树中，边的权值总和最小。,求最小费用生成树： 两种方法：Prim（普里姆算法）Kruskal（克鲁斯卡尔算法）Prim算法：从一个顶点开始，不断增加顶点到树中。,Kruskal算法： 先选取所有顶点，然后不断选取权值最小的边来连接位于两个不同的连通分量内的顶点。,最短路径： 图中两个顶点之间有多条路径，最短路径是所有路径中边或弧的权值总和最小的路径。,计算机网络中常使用最短路径算法计算最佳路径（无向图）,交通网络中使用最短路径算法计算最短旅途（有向图）,Dijkstra算法,Floyd算法,两种算法：,作业：,P.75页 18, 19, 20, 21, 23 题； P.75页 22 题；将此二叉树转换成森林； 已知二叉树的先序序列为：ABDECFGHI，中序序列为：DBEAFHGIC，画出此二叉树。 已知一个图的邻接矩阵或邻接表，如何判断此图是有向图还是无向图？ P.76页 24 题；,
