《数据结构》课程授课教案（讲稿）第七章 图 第三节 邻接矩阵图类 第四节 图的遍历

课程名称：数据结构第13周，第13讲次摘要第七章图授课题目（章、节）第三节邻接矩阵图类第四节图的遍历【目的要求】通过本讲课程的学习，了解邻接矩阵图类的设计和实现方法，掌握图的遍历算法，包括图的深度优先遍历和图的广度优先遍历算法以及如何处理非连通图的遍历。【重点】掌握图的遍历算法。【难点】理解图的深度遍历算法；可以根据图的邻接矩阵或邻接表得出图的遍历序列。内容【本讲课程的引入】图的存储方法有两种，分别是邻接矩阵和邻接表，其中邻接矩阵对于图的操作非常方便，通常只要图不是一个稀疏图，我们一般都可以采用邻接矩阵存储图，这一讲我们首先来讨论一下邻接矩阵图类的设计和实现方法。【本讲课程的内容】7.3邻接矩阵图类1邻接矩阵图类AdjMWGraph的设计public class AdjMWGraphfstatic finalintmaxWeight=10000;//存储结点的顺序表private SeqList vertices:private int edge;//存储边的二维数组privateintnumOfEdges；//边的个数publicAdjMWGraph(intmaxV)(//构造函数，maxV为结点个数vertices = new SeqList(maxV) ;edge = new int[maxV][maxV];for(int i=O;i<maxV:i++)(for(intj=o:j<maxV:j++)(if(i == )edge[i][j] = 0;elseedge[i]l[j] = maxWeight;11numOfEdges=O;1public int getNumOfVertices(//返回结点个数return vertices.size;导public intgetNumOfEdgesO(//返回边的个数return numOfEdges;1public ObjectgetValue(intv)throws Exception(//返回结点v的数据元素return vertices.getData(v);1

课程名称：数据结构 第 13 周，第 13 讲次 摘 要 授课题目（章、节） 第七章 图 第三节 邻接矩阵图类 第四节 图的遍历 【目的要求】通过本讲课程的学习，了解邻接矩阵图类的设计和实现方法，掌握图的遍历算法，包括图的深 度优先遍历和图的广度优先遍历算法以及如何处理非连通图的遍历。 【重 点】掌握图的遍历算法。 【难 点】理解图的深度遍历算法；可以根据图的邻接矩阵或邻接表得出图的遍历序列。 内 容 【本讲课程的引入】图的存储方法有两种，分别是邻接矩阵和邻接表，其中邻接矩阵对于 图的操作非常方便，通常只要图不是一个稀疏图，我们一般都可以采用邻接矩阵存储图， 这一讲我们首先来讨论一下邻接矩阵图类的设计和实现方法。 【本讲课程的内容】 7.3 邻接矩阵图类 1 邻接矩阵图类 AdjMWGraph 的设计 public class AdjMWGraph{ static final int maxWeight = 10000; private SeqList vertices; //存储结点的顺序表 private int[][] edge; //存储边的二维数组 private int numOfEdges; //边的个数 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; } public int getNumOfVertices(){ //返回结点个数 return vertices.size; } public int getNumOfEdges(){ //返回边的个数 return numOfEdges; } public Object getValue(int v) throws Exception{ //返回结点 v 的数据元素 return vertices.getData(v); }

public int getWeight(int vl,int v2)throws Exceptionf//返回边的权值if(vl=vertices.sizellv2=vertices.size)thrownewException("参数vl或v2越界出错！")；returnedge[v1][v2]:1public void insertVertex(Object vertex)throws Exceptionf//插入结点vertices.insert(vertices.size, vertex);//public void insertEdge(int vl,int v2,int weight)throws Exceptionf插入边，权值为weightif(vl=vertices.size I v2=vertices.size)thrownewException（"参数vl或v2越界出错！"）；edge[v1][v2] = weight;//置边的权值//边的个数加1numOfEdges ++:1public void deleteEdge(int vl, int v2) throws Exceptionf/ /删除边if(vl=vertices.size1l v2=vertices.size)thrownewException（"参数vl或v2越界出错！"）：if(edge[vi][v2] ==maxWeight I vl ==v2)thrownewException（"该边不存在！"）；edge[v1][v2]=maxWeight；//置边的权值为无穷大numOfEdges --://边的个数减11/ /取结点v的第public int getFirstNeighbor(int v)throwsExceptionf个邻接结点。若存在返回该结点的下标序号，否则返回-1if(v=vertices.size)thrownewException("参数v越界出错！")；for(int col = O; col 0&&edge[v][col]= vertices.sizeIl v2=vertices.size)thrownewException（"参数vl或v2越界出错！）；for(int col = v2 + l: col 0&&edge[vl][col]<maxWeight)return col;return - l:

public int getWeight(int v1, int v2) throws Exception{ //返回边的权值 if(v1 = vertices.size || v2 = vertices.size) throw new Exception("参数 v1 或 v2 越界出错！"); return edge[v1][v2]; } public void insertVertex(Object vertex) throws Exception{ //插入结点 vertices.insert(vertices.size, vertex); } public void insertEdge(int v1, int v2, int weight) throws Exception{ // 插入边，权值为 weight if(v1 = vertices.size || v2 = vertices.size) throw new Exception("参数 v1 或 v2 越界出错！"); edge[v1][v2] = weight; //置边的权值 numOfEdges ++; //边的个数加 1 } public void deleteEdge(int v1, int v2) throws Exception{ //删除边 if(v1 = vertices.size || v2 = vertices.size) 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) throws Exception{ //取结点 v 的第 一个邻接结点。若存在返回该结点的下标序号，否则返回-1 if(v = vertices.size) throw new Exception("参数 v 越界出错！"); for(int col = 0; col 0 && edge[v][col] = vertices.size || v2 = vertices.size) throw new Exception("参数 v1 或 v2 越界出错！"); for(int col = v2 + 1; col 0 && edge[v1][col] < maxWeight) return col; return - 1; }

7.4图的遍历1.遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。2.遍历实质：找每个顶点的邻接点的过程。3.图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。4.解决思路：可设置一个辅助数组visited[n]，用来标记每个被访问过的顶点。它的初始状态为O，在图的遍历过程中，一旦某一个顶点i被访问，就立即改visited[］为1，防止它被多次访问。图常用的遍历：一、深度优先遍历二、广度优先遍历1.深度优先遍历（DFS）基本思想：一一仿树的前序遍历过程。起点连通图的深度优先遍历递归算法为：（1）访问结点v并标记结点v为已访问；（2）查找结点v的第一个邻接结点W：（3）若结点v的邻接结点W存在，则继续执行，否则算法结束：（4）若结点W尚未被访问则深度优先搜索递归访问结点W；（5）查找结点v的W邻接结点的下一个邻接结点W，转到步骤（3）。深度优先遍历成员函数设计private void depthFirstSearch(int v, boolean[I visited, Visit vs) throws Exceptiont1/访问该结点vs.print(getValue(v));1/置已访问标记visited[v] = true,intw=getFirstNeighbor(v)；/取第一个邻接结点while(w|=-1)(//当邻接结点存在时循环if(! visited[w])1如果没有访问过depthFirstSearch(w，visited，vs);//以w为初始结点递归遍历W=getNextNeighbor(vw);//取下一个邻接结点12.广度优先遍历（BFS）基本思想：一一仿树的层次遍历过程

7.4 图的遍历 1.遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使 每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。 2.遍历实质：找每个顶点的邻接点的过程。 3.图的特点：图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个 顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 4.解决思路：可设置一个辅助数组 visited [n ]，用来标记每个被访问过的顶点。它的初 始状态为 0，在图的遍历过程中，一旦某一个顶点 i 被访问，就立即改 visited [i]为 1， 防止它被多次访问。 图常用的遍历：一、深度优先遍历二、广度优先遍历 1.深度优先遍历( DFS ) 基本思想：——仿树的前序遍历过程。 连通图的深度优先遍历递归算法为： （1）访问结点 v 并标记结点 v 为已访问； （2）查找结点 v 的第一个邻接结点 w； （3）若结点 v 的邻接结点 w 存在，则继续执行，否则算法结束； （4）若结点 w 尚未被访问则深度优先搜索递归访问结点 w； （5）查找结点 v 的 w 邻接结点的下一个邻接结点 w，转到步骤（3）。 深度优先遍历成员函数设计 private void depthFirstSearch(int v, boolean[] visited, Visit vs) throws Exception{ vs.print(getValue(v)); //访问该结点 visited[v] = true; //置已访问标记 int w = getFirstNeighbor(v); //取第一个邻接结点 while(w != -1){ //当邻接结点存在时循环 if(! visited[w]) //如果没有访问过 depthFirstSearch(w, visited, vs); //以 w 为初始结点递归遍历 w = getNextNeighbor(v, w); //取下一个邻接结点 } } 2.广度优先遍历( BFS ) 基本思想：——仿树的层次遍历过程

起点连通图的广度优先遍历算法为：（1）访问初始结点v并标记结点v为已访问：（2）结点v入队列；（3）当队列非空时则继续执行，否则算法结束：（4）出队列取得队头结点u：（5）查找结点u的第一个邻接结点W：（6）若结点u的邻接结点w不存在，则转到步骤（3），否则循环执行，（6.1）若结点w尚未被访问，则访问结点W，并标记结点w为已访问；（6.2）结点w入队列：（6.3）查找结点u的w邻接结点后的下一个邻接结点W，转到步骤（6）。广度优先遍历成员函数设计privatevoid broadFirstSearch(int v, boolean[visited, Visit vs) throws Exceptionint u, w,SeqQueuequeue=newSeqQueue();//创建顺序队列queue1/访问结点vvs.print(getValue(v),1/置已访问标记visited[v] = true,/结点v入队列queue.append(new Integer(v);while(! queue.isEmptyO)(//队列非空时循环u=((Integer)queue.deleteO).intValue()//出队列W=getFirstNeighbor(u)；/取结点u的第一个邻接结点/当邻接结点存在时循环while(w |=- 1)(1若该结点没有访问过if(! visited[w])vs.print(getValue(w)；//访问结点w//置已访问标记visited[w] = true;queue.append(newInteger(w);w=getNextNeighbor(u, w);I113非连通图的遍历对于连通图，从图的任意一个结点开始深度或广度优先遍历，一定可以访问图中的所有结点。但对于非连通图，从图的任意一个结点开始深度或广度优先遍历，并不能访问图中的所有结点。对于非连通图，从图的任意一个结点开始深度或广度优先遍历只能访问和初始结点连通的所有结点。但是，当把每一个结点都作为一次初始结点进行深度或广度优先遍历，并根据结点的访问标记来判断是否需要访问该结点，就一定可以访问非连通图（当然包括连通图）中的所

连通图的广度优先遍历算法为： （1）访问初始结点 v 并标记结点 v 为已访问； （2）结点 v 入队列； （3）当队列非空时则继续执行，否则算法结束； （4）出队列取得队头结点 u； （5）查找结点 u 的第一个邻接结点 w； （6）若结点 u 的邻接结点 w 不存在，则转到步骤（3），否则循环执行， （6.1）若结点 w 尚未被访问，则访问结点 w，并标记结点 w 为已访问； （6.2）结点 w 入队列； （6.3）查找结点 u 的 w 邻接结点后的下一个邻接结点 w，转到步骤（6）。 广度优先遍历成员函数设计 private void broadFirstSearch(int v, boolean[] visited, Visit vs) throws Exception{ int u, w; SeqQueue queue = new SeqQueue();//创建顺序队列 queue vs.print(getValue(v)); //访问结点 v visited[v] = true; //置已访问标记 queue.append(new Integer(v)); //结点 v 入队列 while(! queue.isEmpty()){ //队列非空时循环 u = ((Integer)queue.delete()).intValue();//出队列 w = getFirstNeighbor(u); //取结点 u 的第一个邻接结点 while(w != - 1){ //当邻接结点存在时循环 if(! visited[w]){ //若该结点没有访问过 vs.print(getValue(w)); //访问结点 w visited[w] = true; //置已访问标记 queue.append(new Integer(w)); } w = getNextNeighbor(u, w); } } } 3 非连通图的遍历 对于连通图，从图的任意一个结点开始深度或广度优先遍历，一定可以访问图中的所 有结点。但对于非连通图，从图的任意一个结点开始深度或广度优先遍历，并不能访问图 中的所有结点。对于非连通图，从图的任意一个结点开始深度或广度优先遍历只能访问和 初始结点连通的所有结点。 但是，当把每一个结点都作为一次初始结点进行深度或广度优先遍历，并根据结点的访 问标记来判断是否需要访问该结点，就一定可以访问非连通图（当然包括连通图）中的所

有结点。public voiddepthFirstSearch(Visitvs)throws Exception1/非连通图的深度优先遍历boolean[]visited=newboolean[getNumOfVertices()]for(inti=0;i<getNumOfVerticesO);i++)visited[]=false；//置所有结点均未访问过for(inti=0;i<getNumOfVertices();i++)/对每个结点循环1/如果该结点未访问if(! visited[i])depthFirstSearch(i，visited,vs);//以结点i为初始结点深度优先遍历1public void broadFirstSearch(Visit vs) throws Exception//非连通图的广度优先遍历boolean[] visited = new boolean[getNumOfVertices()];for(inti=0, i<getNumOfVertices(); i++)visited[i]=false;//置所有结点均未访问过for(inti=O;i<getNumOfVertices(,i++)//对每个结点循环if(!visited[i])//如果该结点未访问过broadFirstSearch(i，visited,vs);//以结点i为初始结点广度优先遍历14测试程序public class Exam8_20public static void main(String[ args)final intmaxVertices =100;Visit vs= new VisitO);AdjMWGraphg=newAdjMWGraph(maxVertices);Characterla=(newCharacter(A),newCharacter(B),new Character(C),newCharacter(D'),newCharacter(E));RowCo/Weight[) rcw = (new RowColWeight(0,1,10),new RowColWeight(0,4,20),newRowCo/Weight(1,3,30),newRowColWeight(2,1,40),newRowCo/Weight(3,2,50));int n =5,e=5;trytRowColWeight.createGraph(g,a.n,rcw,e);System.out.print("深度优先搜索序列为：");g.depthFirstSearch(vs);System.out.printlnO;System.out.print("广度优先搜索序列为：")g.broadFirstSearch(vs);System.out.printlnO);1

有结点。 public void depthFirstSearch(Visit vs) throws Exception{ //非连通图的深度优先遍历 boolean[] visited = new boolean[getNumOfVertices()]; for(int i = 0; i < getNumOfVertices(); i ++) visited[i] = false; //置所有结点均未访问过 for(int i = 0; i < getNumOfVertices(); i ++)//对每个结点循环 if(! visited[i]) //如果该结点未访问 depthFirstSearch(i, visited, vs);//以结点 i 为初始结点深度优先遍历 } public void broadFirstSearch(Visit vs) throws Exception{ //非连通图的广度优先遍历 boolean[] visited = new boolean[getNumOfVertices()]; for(int i = 0; i < getNumOfVertices(); i ++) visited[i] = false; //置所有结点均未访问过 for(int i = 0; i < getNumOfVertices(); i ++)//对每个结点循环 if(! visited[i]) //如果该结点未访问过 broadFirstSearch(i, visited, vs);//以结点 i 为初始结点广度优先遍历 } } 4 测试程序 public class Exam8_2{ public static void main(String[] args){ final int maxVertices = 100; Visit vs = new Visit(); AdjMWGraph g = new AdjMWGraph(maxVertices); Character[] a = {new Character('A'),new Character('B'),new Character('C'),new Character('D'),new Character('E')}; RowColWeight[] rcw = {new RowColWeight(0,1,10),new RowColWeight(0,4,20),new RowColWeight(1,3,30),new RowColWeight(2,1,40),new RowColWeight(3,2,50)}; int n = 5, e = 5; try{ RowColWeight .createGraph(g,a,n,rcw,e); System.out.print("深度优先搜索序列为："); g.depthFirstSearch(vs); System.out.println(); System.out.print("广度优先搜索序列为："); g.broadFirstSearch(vs); System.out.println(); }

catch (Exceptionex)ex.printStackTraceO,深度优先搜索序列为：ABDCE广度优先搜索序列为：ABEDC【本讲课程的小结】在学习了树的遍历算法的基础上我们学习图的遍历算法理解起来应该比较容易，并且图的遍历和树的遍历一样是非常重要的一种操作，所以对于图的深度优先遍历、广度优先遍历算法以及如何处理非连通图的遍历问题都是需要掌握的内容。【本讲课程的作业】编写求邻接矩阵存储的图G中所有项点的入度的算法

catch (Exception ex){ ex.printStackTrace(); } } } 深度优先搜索序列为：ABDCE 广度优先搜索序列为：ABEDC 【本讲课程的小结】在学习了树的遍历算法的基础上我们学习图的遍历算法理解起来应该 比较容易，并且图的遍历和树的遍历一样是非常重要的一种操作，所以对于图的深度优先 遍历、广度优先遍历算法以及如何处理非连通图的遍历问题都是需要掌握的内容。 【本讲课程的作业】编写求邻接矩阵存储的图 G 中所有顶点的入度的算法