《数据结构》课程教学资源（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; }