8.2 图的存储结构（邻接矩阵和邻接表）《数据结构与算法（Java版）》
游戏只会红警和三国
编辑于 2021年06月14日 09:50
收录于文集
共14篇

8.2.0 图的接口实现

代码块
clike
自动换行
复制代码
public interface Graph<V> {
	int edgesSize();	//边的数量
	int  verticesSize() ;		//顶点数量
	void addVertex(V v);	//增加一个顶点
	void addEdge(V from,V to);	//增加一条边
	void addEdge(V from,V to,int weight); //增加一条带权值的边
	
	void removeEdge(V from,V to);	//删除一条边
	void removeVertex(V v);			//删除某个顶点
	
	void displayGraph();		//显示一个图
	
	int degree(V v) ;		//返回顶点v的度


}
复制成功

测试用图

代码块
clike
自动换行
复制代码
//图测试类的代码
public class GraphTest {

	public static void main(String[] args) {
	
//		Graph<Character> graph = new UnderetedMatrixGrpah<>(10); //邻接矩阵的测试
		Graph<Character>graph = new UnderetedListGraph<>(10); //邻接表的测试
		
		graph.addVertex('A');
		graph.addVertex('B');
		graph.addVertex('C');
		graph.addVertex('D');
		graph.addVertex('E');
		graph.addVertex('F');
				
		graph.addEdge('A', 'B');
		graph.addEdge('A', 'D');
		graph.addEdge('B', 'C');
		graph.addEdge('B', 'E');
		graph.addEdge('C', 'D');
		graph.addEdge('C', 'F');
		graph.addEdge('D', 'F');
		graph.addEdge('E', 'F');
		
		graph.displayGraph();		
//		graph.removeVertex('B');
//		graph.displayGraph();
		
		System.out.println("顶点C的度：" + graph.degree('C'));

	}

}
复制成功

8.2.1 邻接矩阵

邻接矩阵是表示顶点之间邻接关系的矩阵。设G=(V，E)是含有n（设n>0）个顶点的图，各顶点的编号为0～n-1，则G的邻接矩阵数组A是n阶方阵。

邻接矩阵存储

各种图（网）的邻接矩阵

测试样例的邻接矩阵完整描述

代码块
clike
自动换行
复制代码
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;



/**
 * 
 * @author chp
 *
 * @param 
 * 
 * 	模拟实现一个无向图（邻接矩阵）
 */

public class UnderetedMatrixGrpah implements Graph {
	private List vertexList;  //保存顶点信息
	private int[][] edgeMatrix;	//保存邻接矩阵
	private int edges;		//边的数量
	private int vertices; //顶点数量
	private int size;	//规模
	
	
	public UnderetedMatrixGrpah(int size) {
		this.size = size;
		vertexList = new ArrayList<>();
		edgeMatrix = new int[size][size];
		this.edges = 0;
		this.vertices = 0;
	}
	

	@Override
	public int edgesSize() {
		// TODO Auto-generated method stub
		return this.edges;
	}

	@Override
	public int verticesSize() {
		// TODO Auto-generated method stub
		return this.vertices;
	}

	@Override
	public void addVertex(V v) {
		// 加入一个顶点
		this.vertexList.add(v);	
		this.vertices++;
	}

	@Override
	public void addEdge(V from, V to) {
		// TODO Auto-generated method stub
		this.addEdge(from, to, 1);
	}

	@Override
	public void addEdge(V from, V to, int weight) {
		// TODO Auto-generated method stub
		int i = this.vertexList.indexOf(from);
		int j = this.vertexList.indexOf(to);
		this.edgeMatrix[i][j] = weight;
		this.edgeMatrix[j][i] = weight;
		this.edges++;
		
	}

	@Override
	public void removeEdge(V from, V to) {
		// 删除一条边		
		int i = this.vertexList.indexOf(from);
		int j = this.vertexList.indexOf(to);
		this.edgeMatrix[i][j] = 0;
		this.edgeMatrix[j][i] = 0;
		this.edges--;
	}

}
复制成功
代码块
clike
自动换行
复制代码
@Override
	public void removeVertex(V v) {
		// 删除一个顶点
		int index = this.vertexList.indexOf(v); // 被删除顶点的序号

		for (int i = 0; i < this.vertices; i++) {
			if (this.edgeMatrix[index][i] != 0) { // 表示index与i之间有一条边
				this.edges--;
			}
		}

		// index后面的所有行前移一行
		for (int i = index; i < this.vertices - 1; i++) {
			for (int j = 0; j < this.vertices; j++) {
				this.edgeMatrix[i][j] = this.edgeMatrix[i + 1][j];
			}
		}

		// index后面的所有列前移一列
		for (int i = 0; i < this.vertices; i++) {
			for (int j = index; j < this.vertices - 1; j++) {
				this.edgeMatrix[i][j] = this.edgeMatrix[i][j + 1];
			}
		}
      
      //为了保证后面新增的顶点不收到之前存储值的影响，还要做哪些操作？请大家自行补充代码。

		this.vertexList.remove(index);
		this.vertices--;

	}

	@Override
	public void displayGraph() {
		// 显示当前图
		System.out.println("这是一个无向图（邻接矩阵）：");
		System.out.println("顶点：" + this.vertexList);
		System.out.println("图的邻接矩阵是：");
		for (int i = 0; i < this.vertices; i++) {
			for (int j = 0; j < this.vertices; j++) {
				System.out.print(this.edgeMatrix[i][j] + " ");
			}
			System.out.println();
		}
	}

	@Override
	public int degree(V v) {
		// 返回图的顶点v的度

		int index = this.vertexList.indexOf(v); // 获取顶点的序号
		int count = 0;
		for (int i = 0; i < this.vertices; i++) {
			if (this.edgeMatrix[index][i] != 0) { // 表示index与i之间有一条边
				count++;
			}
		}
		return count;
	}
复制成功

邻接矩阵的特点

图的邻接矩阵表示是唯一的。

对于含有n个顶点的图，采用邻接矩阵存储时，无论是有向图还是无向图，也无论边的数目是多少，其存储空间均为O(n2)，所以邻接矩阵适合于存储边数较多的稠密图。

无向图的邻接矩阵一定是一个对称矩阵。因此在顶点个数n很大时可以采用对称矩阵的压缩存储方法减少存储空间。

对于无向图，邻接矩阵的第i行（或第i列）非空元素的个数正好是顶点i的度。

对于有向图，邻接矩阵的第i行（或第i列）非空元素的个数正好是顶点i的出度（或入度）。

用邻接矩阵方法存储图，确定任意两个顶点之间是否有边相连的时间为O(1)。

8.2.2  邻接表

每个顶点建立一个单链表，第i（0≤i≤n-1）个单链表中的结点表示依附于顶点i的边（有向图是顶点i出边）。

每个单链表上附设一个表头结点，将所有表头结点构成一个头结点数组。

图的邻接表存储结构

测试样例的邻接表完整描述

代码块
clike
自动换行
复制代码

import java.util.LinkedList;
import java.util.Queue;

/**
 * 
 * @author chp
 *
 * @param <V>
 * 
 *            模拟一个无向图的邻接表实现
 */
public class UnderetedListGraph<V>implements Graph<V>{
	Vertex<V>[] vertexList; // 邻接 数组
	private int edges; // 边的数量
	private int vertices; // 顶点的数量

	public UnderetedListGraph(int size) {
		vertexList = new Vertex[size];
		this.edges = 0;
		this.vertices = 0;
	}

	class Vertex<V>{
		V data; // 顶点值
		LinkedList<Integer>adj; // 邻接表

		Vertex(V data) {
			this.data = data; // 顶点值
			this.adj = new LinkedList<>(); // 每个顶点的邻接点构成的邻接表
		}
	}

	@Override
	public int edgesSize() {
		// TODO Auto-generated method stub
		return this.edges;
	}

	@Override
	public int verticesSize() {
		// TODO Auto-generated method stub
		return this.vertices;
	}

	@Override
	public void addVertex(V v) {
		// 增加一个顶点
		this.vertexList[this.vertices++] = new Vertex<>(v);

	}

	@Override
	public void addEdge(V from, V to) {
		// 增加一条边
		int i = this.getPosition(from);
		int j = this.getPosition(to);

		this.vertexList[i].adj.add(j);
		this.vertexList[j].adj.add(i);
		this.edges++;
	}

	private int getPosition(V v) {
		// TODO Auto-generated method stub
		for (int i = 0; i < this.vertices; i++) {
			if (this.vertexList[i].data.equals(v)) {
				return i;
			}
		}
		return -1;
	}

	@Override
	public void addEdge(V from, V to, int weight) {
		// TODO Auto-generated method stub

	}

	@Override
	public void removeEdge(V from, V to) {
		// 删除一条边
		int i = this.getPosition(from);
		int j = this.getPosition(to);

		this.vertexList[i].adj.remove(new Integer(j)); // 思考？
		this.vertexList[j].adj.remove(new Integer(i)); // 删除的应该是一个对象，而不是根据索引index来进行删除
		this.edges++;

	}

	@Override
	public void removeVertex(V v) {
		// 删除一个顶点
		/*
		 * 1. 查询顶点v的序号index 2. 更新边的个数 3. 删除所有邻接点对应的index 4. 在数组中删除当前的顶点 5. 更新顶点的个数 6.
		 * 更新所有邻接表中序号值，将所有大于index的值全部减
		 */
		int index = this.getPosition(v);

		this.edges = this.edges - this.degree(v);

		for (int i : this.vertexList[index].adj) {
			this.vertexList[i].adj.remove(new Integer(index));
		}

		for (int i = index; i < this.vertices - 1; i++) {
			this.vertexList[i] = this.vertexList[i + 1];
		}
		this.vertices--;
		for (int i = 0; i < this.vertices; i++) {
			LinkedList<Integer>list = vertexList[i].adj;
			for (int j = 0; j < list.size(); j++) {
				if (list.get(j) > index) {
					list.set(j, list.get(j) - 1);
				}

			}
		}

	}

	@Override
	public void displayGraph() {
		// 显示当前图
		System.out.println("这是一个使用邻接表存储的图：");
		for (int i = 0; i < this.vertices; i++) {
			System.out.print("顶点：" + this.vertexList[i].data);
			System.out.println(",邻接表" + this.vertexList[i].adj);
		}

	}

	@Override
	public int degree(V v) {
		// TODO Auto-generated method stub
		return this.vertexList[getPosition(v)].adj.size();
	}

}
复制成功

邻接表的特点

邻接表表示不唯一。

对于有n个顶点和e条边的无向图，其邻接表有n个表头结点和2e个边结点；对于有n个顶点和e条边的有向图，其邻接表有n个表头结点和e个边结点。显然，对于边数目较少的稀疏图，邻接表比邻接矩阵要节省空间。

对于无向图，顶点i（0≤i≤n-1）对应的单链表的边结点个数正好是顶点i的度。

对于有向图，顶点i（0≤i≤n-1）对应的单链表的边结点个数仅仅是顶点i的出度。顶点i的入度是邻接表中adj中元素值为i的边结点个数。

用邻接表存储图时，确定任意两个顶点之间是否有边相连的时间为O(m)（m为最大顶点出度，m<n）。

视频资源：

8.2.1.1 邻接矩阵（实现）​

8.2.1.2 邻接矩阵（删除边和顶点）​

8.2.1.3 邻接矩阵的特点​

8.2.2.1 邻接表的实现1​

8.2.2.2 邻接表的实现2​

8.2.2.3 邻接表的特点​

编程 算法 图 深度优先 广度优先 数据结构 Java 陈平 邻接矩阵 邻接表
本文为我原创，未经授权禁止转载
cv11600440