文档介绍：叶核亚
数据结构(Java版) (第2版)
数据结构(Java版)(第2版)
第0章 Java程序设计基础
第1章绪论
第2章线性表
第3章栈与队列
第4章串
第5章数组和广义表
第6章树和二叉树
第7章图
第8章查找
第9章排序
第10章综合应用设计
第11章 Java开发运行环境
第7章图
图及其抽象数据类型
图的表示和实现
图的遍历
最小生成树
最短路径
目的:理解图结构。
要求:掌握图的存储结构和操作实现。
重点:图的两种存储结构,遍历算法,最小生成树,最短路径。
难点:图的存储和操作实现,最小生成树,最短路径。
《数据结构(Java版)(第2版)》
图及其抽象数据类型 图的基本概念
图的定义和术语 G=(V, E)
V={A | A∈某个数据元素集合}
E={(A, B) | A, B∈V}
无向图
有向图
《数据结构(Java版)(第2版)》
完全图
带权图
邻接顶点
《数据结构(Java版)(第2版)》
deg(A)=indeg(A)+outdeg(A)
《数据结构(Java版)(第2版)》
《数据结构(Java版)(第2版)》
图抽象数据类型
public interface GGraph<E> { //图接口
int vertexCount(); //返回顶点数
E get(int i); //返回顶点vi元素
boolean insertVertex(E vertex); //插入顶点
boolean insertEdge(int i, int j, int weight); //插入边
boolean removeVertex(int v); //删除顶点
boolean removeEdge(int i, int j); //删除边
int getFirstNeighbor(int v); //返回邻接顶点序号
int getNextNeighbor(int v, int w); //返回下一个邻接顶点
}
《数据结构(Java版)(第2版)》
图的表示和实现
图的邻接矩阵表示
图的邻接表表示
《数据结构(Java版)(第2版)》
图的邻接矩阵表示
邻接矩阵
不带权图的邻接矩阵
带权图的邻接矩阵
《数据结构(Java版)(第2版)》