《数据结构》课程教学资源(PPT课件)第七章 图(7.3 邻接矩阵图类 7.4 图的遍历)

7.3邻接矩阵图类·邻接矩阵图类AdjMWGraph的设计class AdjMWGraph[const int maxWeight = 10000:/存储结点的顺序表private SeqList vertices;/存储边的二维数组private int[,J edge;/边的个数private int numOfEdges;
7.3 邻接矩阵图类 • 邻接矩阵图类AdjMWGraph的设计 class AdjMWGraph{ const int maxWeight = 10000; private SeqList vertices; //存储结点的顺序表 private int[,] edge; //存储边的二维数组 private int numOfEdges; //边的个数

publicAdjMWGraph(intmaxV)i//构造函数,maxV为结点个数vertices = new SeqList(maxV);edge = new int[maxV, maxV];for (inti = 0; i< maxV; i++)for (int j = O; j< maxV; j++)(0888880if (i == j)88888088888edge[i, j] = O;088888else0808888088888edge[i, jl = maxWeight;7numOfEdges=0;7
public AdjMWGraph(int maxV){ //构造函数,maxV为结点个数 vertices = new SeqList(maxV); edge = new int[maxV, maxV]; for (int i = 0; i < maxV; i++){ for (int j = 0; j < maxV; j++){ if (i == j) edge[i, j] = 0; else edge[i, j] = maxWeight; } } numOfEdges = 0; } 0 ∞∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞ ∞ ∞ ∞ ∞ ∞ 0

/返回结点个数public int getNumOfVerticesOreturn vertices.getSizeO:/返回边的个数public int getNumOfEdgesOreturn numOfEdges;public Object getValue(int v)//返回序号为v的结点的数据元素return vertices.getData(v);
public int getNumOfVertices(){ //返回结点个数 return vertices.getSize(); } public int getNumOfEdges(){ //返回边的个数 return numOfEdges; } public Object getValue(int v){ //返回序号为v的结点的数据元素 return vertices.getData(v); }

public int getWeight(int vl, int v2) //返回边的权值if (v1 = vertices.getSize0 II v2 :vertices.getSizeO)thrownewException("参数v1或v2越界出错!");return edge[vl, v2];public void insertVertex(Object vertex) //插入结点vertices.insert(vertices.getSizeO, vertex);^
public int getWeight(int v1, int v2){ //返回边的权值 if (v1 = vertices.getSize() || v2 = vertices.getSize()) throw new Exception("参数v1或v2越界出错!"); return edge[v1, v2]; } public void insertVertex(Object vertex){ //插入结点 vertices.insert(vertices.getSize(), vertex); }

public void insertEdge(int vl, int v2, int weight)/插入边,权值为weightif (v1 = vertices.getSize0 Il v2 :vertices.getSizeO)thrownewException("参数v1或v2越界出错!")://置边的权值edge[v1, v2] = weight;/边的个数加1numOfEdges++;
public void insertEdge(int v1, int v2, int weight) { //插入边,权值为weight if (v1 = vertices.getSize() || v2 = vertices.getSize()) throw new Exception("参数v1或v2越界出错!"); edge[v1, v2] = weight; //置边的权值 numOfEdges++; //边的个数加1 }

public void deleteEdge(int vl, int v2) //删除边if (v1 = vertices.getSize0 Il v2 :vertices.getSizeO)thrownewException("参数vl或v2越界出错!");if (edge[vl, v2] == maxWeight Il v1 == v2)throw newException("该边不存在!");edge[vl,v2]=maxWeight;//置边的权值为无穷大/边的个数减1numOfEdges--;
public void deleteEdge(int v1, int v2) { //删除边 if (v1 = vertices.getSize() || v2 = vertices.getSize()) throw new Exception("参数v1或v2越界出错!"); if (edge[v1, v2] == maxWeight || v1 == v2) throw new Exception("该边不存在!"); edge[v1, v2] = maxWeight; //置边的权值为无穷大 numOfEdges-; //边的个数减1 }

public int getFirstNeighbor(int v){//取结点v的第一个邻接结点。若存在返回该结点的下标序号,否则返回-1if (v = vertices.getSize0)thrownewException("参数v越界出错!");for (int col = O; col 0 && edge[v, col] < maxWeight)return col;return -1;
public int getFirstNeighbor(int v) { //取结点v的第一个邻接结点。若存在返回该结点的下标序 号,否则返回-1 if (v = vertices.getSize()) throw new Exception("参数v越界出错!"); for (int col = 0; col 0 && edge[v, col] < maxWeight) return col; return -1; }

public int getNextNeighbor(int vl, int v2)//取结点v1的邻接结点v2后的邻接结点/若存在返回该结点的下标序号,否则返回-1if (v1 = vertices.getSize0 II v2 vertices.getSizeO)thrownewException("参数v1或v2越界出错!");for (int col = v2 + 1; col 0 && edge[vl, col] < maxWeight)return col;return -1;
public int getNextNeighbor(int v1, int v2) { //取结点v1的邻接结点v2后的邻接结点 //若存在返回该结点的下标序号,否则返回-1 if (v1 = vertices.getSize() || v2 = vertices.getSize()) throw new Exception("参数v1或v2越界出错!"); for (int col = v2 + 1; col 0 && edge[v1, col] < maxWeight) return col; return -1; }

0A1B00A=0V=00(D00E00(a)(b)
B A D C E = E D C B A V = 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 1 1 1 A (b) (a)

可以把创建图所需的数据和方法设计为类RowColWeightclassRowColWeightint row;int col;int weight;public RowColWeight(int r, int c, int w) row =r;col = c;weight =w;1
可以把创建图所需的数据和方法设计为类RowColWeight class RowColWeight{ int row; int col; int weight; public RowColWeight(int r, int c, int w) { row = r; col = c; weight = w; }
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 《数据结构》课程教学资源(PPT课件)第七章 图(7.1 概述 7.2 图的存储结构).ppt
- 《数据结构》课程教学资源(PPT课件)第一章 绪论(华北理工大学:赵爽).ppt
- 《数据结构》课程授课教案(讲稿)第九章 查找 第三节 动态查找.doc
- 《数据结构》课程授课教案(讲稿)第九章 查找 第一节 查找的基本概念 第二节 静态查找.doc
- 《数据结构》课程授课教案(讲稿)第八章 排序 第一节 排序的基本概念 第二节 插入排序 第三节 交换排序.doc
- 《数据结构》课程授课教案(讲稿)第七章 图 第三节 邻接矩阵图类 第四节 图的遍历.doc
- 《数据结构》课程授课教案(讲稿)第七章 图 第一节 概述 第二节 图的存储结构.doc
- 《数据结构》课程授课教案(讲稿)第六章 树和二叉树 第三节 以结点类为基础的二叉树设计.doc
- 《数据结构》课程授课教案(讲稿)第六章 树和二叉树 第一节 树 第二节 二叉树.doc
- 《数据结构》课程授课教案(讲稿)第五章 递归算法.doc
- 《数据结构》课程授课教案(讲稿)第四章 数组、集合和矩阵 第四节 矩阵类 第五节 特殊矩阵 第六节 稀疏矩阵.doc
- 《数据结构》课程授课教案(讲稿)第四章 数组、集合和矩阵 第一节 数组 第二节 向量类 第三节 集合.doc
- 《数据结构》课程授课教案(讲稿)第三章 堆栈和队列 第二节 队列.doc
- 《数据结构》课程授课教案(讲稿)第三章 堆栈和队列 第一节 堆栈.doc
- 《数据结构》课程授课教案(讲稿)第二章 线性表 第四节 循环单链表 第五节 双向链表 第六节 仿真链表.doc
- 《数据结构》课程授课教案(讲稿)第二章 线性表 第三节 单链表.doc
- 《数据结构》课程授课教案(讲稿)第二章 线性表 第一节 线性表 第二节 顺序表.doc
- 《数据结构》课程授课教案(讲稿)第一章 绪论.doc
- 《电子商务概论》课程教学资源(教案讲义)第一章 电子商务概述.pdf
- 《电子商务概论》课程教学资源(教案讲义)第二章 电子商务交易模式.pdf
- 《数据结构》课程教学资源(PPT课件)第三章 堆栈和队列(3.1 堆栈 3.2 堆栈的应用).ppt
- 《数据结构》课程教学资源(PPT课件)第三章 堆栈和队列(3.3 队列 3.4 优先级队列).ppt
- 《数据结构》课程教学资源(PPT课件)第九章 查找.ppt
- 《数据结构》课程教学资源(PPT课件)第二章 线性表(2.1 线性表 2.2 顺序表).ppt
- 《数据结构》课程教学资源(PPT课件)第二章 线性表(2.3 单链表).ppt
- 《数据结构》课程教学资源(PPT课件)第二章 线性表(2.4 循环单链表 2.5 双向链表 2.6 仿真链表).ppt
- 《数据结构》课程教学资源(PPT课件)第五章 递归算法.ppt
- 《数据结构》课程教学资源(PPT课件)第八章 排序.ppt
- 《数据结构》课程教学资源(PPT课件)第六章 树和二叉树(6.1 树 6.2 二叉树).ppt
- 《数据结构》课程教学资源(PPT课件)第六章 树和二叉树(6.3 以结点类为基础的二叉树设计 6.4 二叉树类 6.5 线索二叉树 6.6 哈夫曼树).ppt
- 《数据结构》课程教学资源(PPT课件)第六章 树和二叉树(6.7 树与二叉树的转换 6.8 树的遍历).ppt
- 《数据结构》课程教学资源(PPT课件)第四章 数组、集合和矩阵.ppt