二、图的存储结构
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分类中加上权值
网友评论