数据结构-高职计算机-97484-第六章图幻灯片.pptx

第六章 图;6.1 图的定义和基本术语 6.2 图的存储方式 6.3 图的遍历 6.4 图与最小生成树 6.5 AOV网与拓扑排序 6.6 AOE网与关键路径 6.7 最短路径 6.8 本章实战练习 6.9 小结 ;6.1 图的定义和基本术语 6.2 图的存储方式 6.3 图的遍历 6.4 图与最小生成树 6.5 AOV网与拓扑排序 6.6 AOE网与关键路径 6.7 最短路径 6.8 本章实战练习 6.9 小结 ;6.1 图的定义和基本术语;6.1.1 图的定义;6.1.1 图的定义;6.1.1 图的定义;6.1.1 图的定义;6.1.1 图的定义;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1.2 图的基本术语;6.1 图的定义和基本术语 6.2 图的存储方式 6.3 图的遍历 6.4 图与最小生成树 6.5 AOV网与拓扑排序 6.6 AOE网与关键路径 6.7 最短路径 6.8 本章实战练习 6.9 小结 ;6.2 图的存储方式; ;6.2.1 邻接矩阵;6.2.1 邻接矩阵;6.2.1 邻接矩阵;6.2.1 邻接矩阵;void CreateDN(MGraph G) //算法6.1用数组表示法构造有向网G { scanf(G.vexnum,G.arcnum); for(i=0;i G.vexnum;i++) scanf(G.vexs[i]); //构造顶点表 for(i=0;i G.vexnum;i++) { for(j=0;j G.vexnum;j++) G.arcs[i][j]={-1}; //初始化邻接矩阵权值均为-1，用-1表示邻接矩阵中的∞元素 } for(k=0;k G.vexnum;k++) { Scanf{v1, v2, w}; //接受用户输入与边相连的两个顶点及边的权值 n=LocateVex(G, v1); //确定v1在图中的位置 m=LocateVex(G, v2); G.arcs[n][m]=w; } }//end of CreateDN;6.2.1 邻接矩阵;6.2.2 邻接表;6.2.2 邻接表;//图的邻接表存储表示 #define MaxVerNum 10 //最大顶点数 typedef enum{DG,DN,UDG,UDN} GraphType; //枚举{有向图，有向网，无向图，无向网} typedef struct ArcNode{ int adjvex; //邻接顶点的位置 ArcNode *nextarc; // 标记下一个vi的邻接结点的指针 char data; // 标记和边（或弧）的相关信息 } ArcNode; typedef struct VexNode{ VexInfo vex; //顶点的信息 ArcNode *firstarc; // 标记第一个vi的邻接结点的指针 } VexNode VexList[MaxVerNum]; typedef struct ALGraph{ VexList vexs; int vexnum,arcnum; //顶点数和边数 GraphType type; //图的类型标识 } ALGraph; ;6.2.2 邻接表;(a)无向图G1的邻接表;6.2.3 十字链表;6.2.3 十字链表;//图的十字链表存储表示 #define MaxVerNum 10 //最大顶点数 typedef struct ArcNode{ int tailvex,headvex; ArcNode *hlink,*tlink; char data; // 标记和边（或弧）的相关信息 } ArcNode; typedef struct VexNode{ VexInfo vex; //顶点的信息 ArcNode *firstin,*firstout; // 标记第一个vi的邻接结点的指针 } VexNode VexList[MaxVerNum]; typedef struct OLGraph{ VexList vexs; int vexnum,arcnum; //顶点数和边数 } OLGraph;;//下面算法6.2是建立有向图的十字链表。