MatrixUDG

本文通过Java实现邻接矩阵无向图。

一. 邻接矩阵无向图的介绍

邻接矩阵无向图是一种数据结构，其利用数组存储顶点，二维数组存储顶点之间的关系来存储数据。如下面所示

Tips: 不难发现它是用空间换时间的策略，这么存边会造成很大的空间浪费，对于顶点关系的检索速度会很快。优化的话可以考虑使用稀疏数组来替换二维数组。同样的策略也适用于邻接矩阵有向图

二. 邻接矩阵无向图的代码说明

1. 基本定义

public class Graph<T> {
    // 顶点
    private ArrayList<T> vertexs;
    // 边
    private int[][] edge;
}

• vertexs 用于存储顶点值
• edge用于存储各个顶点的关系，我们把这种关系称之为边

2. 创建图

// 初始化
Graph(int n){
    vertexs = new ArrayList<T>();
    edge = new int[n][n];
    visited = new boolean[n];
}

// 插入顶点
public void insertVertex(T vertex){
    vertexs.add(vertex);
}

// 插入边
public void insertEdge(int v1, int v2, int weight){
    edge[v1][v2] = weight;
    edge[v2][v1] = weight;
}

方便大家学习，提供了源代码