无向图由于边不区分方向，所以其邻接矩阵是一个对称矩阵。邻接矩阵中的0表示边不存在，主对角线全为0表示图中不存在自环。
带权有向图的邻接矩阵:
在带权有向图的邻接矩阵中，数字表示权值weight，「无穷」表示弧不存在。由于权值可能为0，所以不能像在无向图的邻接矩阵中那样使用0来表示弧不存在。
public class Digraph { private int vertexsNum; private int edgesNum; private int[][] arc; public Digraph(int[][] data, int vertexsNum) { this.vertexsNum = vertexsNum; this.edgesNum = data.length; arc = new int[vertexsNum][vertexsNum]; for (int i = 0; i < vertexsNum; i++) { for (int j = 0; j < vertexsNum; j++) { arc[i][j] = Integer.MAX_VALUE; } } for (int i = 0; i < data.length; i++) { int tail = data[i][0]; int head = data[i][1]; arc[tail][head] = 1; } } //用于测试，返回一个顶点的邻接点 public Iterable<Integer> adj(int vertex) { Set<Integer> set = new HashSet<>(); for (int i = 0; i < vertexsNum; i++) { if (arc[vertex][i] != Integer.MAX_VALUE) set.add(i); } return set; } public static void main(String[] args) { int[][] data = { {0,3}, {1,0}, {1,2}, {2,0}, {2,1}, }; Digraph wd = new Digraph(data,4); for(int i :wd.adj(1)) { System.out.println(i); } }}
优缺点：
优点：结构简单,操作方便
缺点：对于稀疏图，这种实现方式将浪费大量的空间。

结交游戏开发的各位新朋友，欢迎加入游戏源码群，群聊号码：去2掉9中3文1就5是6群4号4码0

2.2、邻接表
邻接表是一种将数组与链表相结合的存储方法。其具体实现为：将图中顶点用一个一维数组存储，每个顶点Vi的所有邻接点用一个单链表来存储。这种方式和树结构中孩子表示法一样。
对于有向图其邻接表结构如下:
有向图的邻接表是以顶点为弧尾来存储边表的，这样很容易求一个顶点的出度（顶点对应单链表的长度），但若求一个顶点的入度，则需遍历整个图才行。这时可以建立一个有向图的逆邻接表即对每个顶点v都建立一个弧头尾v的单链表。如上图所示。
代码：
/** * 有向图的邻接表实现 * */public class AdjListDigraph { private class EdgeNode { int index; EdgeNode next; EdgeNode(int index, EdgeNode next){ this.index = index; this.next = next; } } private class VertexNode { int id; EdgeNode headNode; } private VertexNode[] vertexs; private int vertexsNum; private int edgesNum; public AdjListDigraph(int[][] data, int vertexsNum) { this.vertexsNum = vertexsNum; this.edgesNum = data.length; vertexs = new VertexNode[vertexsNum]; for (int i = 0; i < vertexs.length; i++) { vertexs[i] = new VertexNode(); vertexs[i].id = i; // } for (int i = 0; i < data.length; i++) { int index = data[i][1]; EdgeNode next = vertexs[data[i][0]].headNode; EdgeNode eNode = new EdgeNode(index,next); vertexs[data[i][0]].headNode = eNode; //头插法 } } //用于测试，返回一个顶点的邻接点 public Iterable<Integer> adj(int index) { Set<Integer> set = new HashSet<>(); EdgeNode current = vertexs[index].headNode; while(current != null) { VertexNode node = vertexs[current.index]; set.add(node.id); current = current.next; } return set; } public static void main(String[] args) { int[][] data = { {0,3}, {1,0}, {1,2}, {2,0}, {2,1}, }; AdjListDigraph ald = new AdjListDigraph(data,4); for(int i :ald.adj(1)) { System.out.println(i); } }}
本算法的时间复杂度为 O(N + E)，其中N、E分别为顶点数和边数，邻接表实现比较适合表示稀疏图。