数据结构_图（2_图的存储结构）

二、图的存储结构

2.1 邻接矩阵

2.1.1无向图

static int[][] graph = {
            {0,1,1,0,0,0,0,0},
            {1,0,0,1,1,0,0,0},
            {1,0,0,0,0,1,1,0},
            {0,1,0,0,0,0,0,1},
            {0,1,0,0,0,0,0,1},
            {0,0,1,0,0,0,1,0},
            {0,0,1,0,0,1,0,0},
            {0,0,0,1,1,0,0,0},
    };

2.1.2有向图

static int[][] graph = {
            {0,1,1,0,0,0,0,0},
            {0,0,0,1,1,0,0,0},
            {0,0,0,0,0,1,1,0},
            {0,0,0,0,0,0,0,1},
            {0,0,0,0,0,0,0,1},
            {0,0,0,0,0,0,1,0},
            {0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0},
    };

2.1.3无向网

static int[][] graph = {
            {0,1,3,0,0,0,0,0},
            {1,0,0,5,1,0,0,0},
            {3,0,0,0,0,11,3,0},
            {0,5,0,0,0,0,0,4},
            {0,1,0,0,0,0,0,1},
            {0,0,11,0,0,0,7,0},
            {0,0,3,0,0,7,0,0},
            {0,0,0,4,1,0,0,0},
    };

2.1.4有向网

static int[][] graph = {
            {0,10,1,0,0,0,0,0},
            {0,0,0,6,1,0,0,0},
            {0,0,0,0,0,2,3,0},
            {0,0,0,0,0,0,0,1},
            {0,0,0,0,0,0,0,5},
            {0,0,0,0,0,0,9,0},
            {0,0,0,0,0,0,0,0},
            {0,0,0,0,0,0,0,0},
    };

2.2 邻接表

2.2.1. 顶点结点

public class VNode {
    public Object data;// 顶点信息

    public ArcNode firstArc;// 边节点
}

2.2.2 边结点

public class ArcNode {
    public int adjVex;// 改边所指向的顶点位置

    public int value;// 边的权值

    public ArcNode nextArc;// 指向下一条边
}

2.2.3 邻接表的分类

1. 无向图邻接表
   顶点的度刚好等于其在邻接表中边结点数
2. 有向图邻接表
   顶点在邻接表中边结点数仅为其出度，入度要遍历所有顶点。
3. 无向网邻接表
   1分类中加上权值
4. 有向网邻接表
   2分类中加上权值