本文共 1576 字，大约阅读时间需要 5 分钟。

图：图是一种数据结构，其中节点可以具有一个或者多个相邻元素，俩个节点的连接称为边，节点也称为顶点。

图的表示方式

邻接矩阵

邻接矩阵是表示图形中顶点之间相邻关系的矩阵，对于n个顶点的图而言，矩阵是的row和col表示的是1…n个点。

1. 邻接矩阵需要为每个顶点都分配n个边的空间，其实有很多边都是不存在,会造成空间的一定损失.
2. 邻接表的实现只关心存在的边，不关心不存在的边。因此没有空间浪费，邻接表由数组+链表组成

import java.util.ArrayList;import java.util.Arrays;public class Graph {	private ArrayList
   
     vertexList; // 存放顶点集合	private int[][] edges; // 矩阵	private int num; // 边的数目	public Graph(int n) {		edges = new int[n][n];		vertexList = new ArrayList
    
     (n);		num = 0;	}	// 插入节点	public void addVer(String vertex) {		vertexList.add(vertex);	}	// 添加边	public void addNum(int v1, int v2, int weight) {		// v1和v2指的是点的下标。weight表示权值		edges[v1][v2] = weight;		edges[v2][v1] = weight;		num++;	}	// 返回节点的个数	public int nodeNum() {		return vertexList.size();	}	// 返回边一共有多少条	public int edgeNum() {		return num;	}	// 通过索引返回值	public String getValue(int i) {		return vertexList.get(i);	}	// 返回v1和v2的权值	public int getWeight(int v1, int v2) {		return edges[v1][v2];	}	// 显示图对应的矩阵	public void show() {		for (int[] link : edges) {			System.err.println(Arrays.toString(link));		}	}	public static void main(String[] args) {		int n = 5; // 节点的个数		String vertexString[] = { "A", "B", "C", "D", "F" };		// 创建图对象		Graph gp = new Graph(5);		// 向图对象添加节点		for (String value : vertexString) {			gp.addVer(value);		}		// 添加边AB AC AD AE BC BD CE DE		gp.addNum(0, 1, 1);		gp.addNum(0, 2, 1);		gp.addNum(0, 3, 1);		gp.addNum(0, 4, 1);		gp.addNum(1, 2, 1);		gp.addNum(1, 3, 1);		gp.addNum(2, 4, 1);		gp.addNum(3, 4, 1);		// 显示图的矩阵		gp.show();	}}
    
   

对上图的实现到最后打印出来矩阵，可以看到与上图构建的矩阵是相同的：

转载地址：http://agmzi.baihongyu.com/