72图的存储结构 72.1邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E) 是具有n(n>0)个顶点的图,顶点的顺序依次为0~n-1,则 G的邻接矩阵A是n阶方阵,其定义如下: (1)如果G是无向图,则: A[iU=1:若(i∈E(G)0其他 (2)如果G是有向图,则: A[i=1:若<∈E(G)0:其他
7.2 图的存储结构 7.2.1 邻接矩阵存储方法 邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V，E) 是具有n（n＞0）个顶点的图，顶点的顺序依次为0～n-1，则 G的邻接矩阵A是n阶方阵，其定义如下： （1）如果G是无向图，则： A[i][j]=1：若(i,j)∈E(G) 0:其他 （2）如果G是有向图，则： A[i][j]=1：若<i,j>∈E(G) 0:其他
(3)如果G是带权无向图,则: A[iwn:着且(i)∈E(G)0:污∞:其他 (4)如果G是带权有向图,则: A[iUi=wn:着谁且i∈E(G)0:i∞:其他
（3）如果G是带权无向图，则： A[i][j]= wij ：若i≠j且(i,j)∈E(G) 0：i=j ∞：其他 （4）如果G是带权有向图，则： A[i][j]= wij ：若i≠j且<i,j>∈E(G) 0：i=j ∞：其他
01234 0 01234 1“0110 对称 0 … 01 0 200^11 不对称 3 30000.0 001
1 0 1 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 2 3 0 41 2 3 0 4 A 1 ＝ 0 1 2 3 4 01234 A 2 ＝ 0 1 2 3 4 01234 对称 不对称
图的邻接矩阵类型 MGraph定义如下 struct VertexType /顶点类型 public int no; /顶点编号 public string data; /顶点其他信息 struct MGraph /图邻接矩阵类型 public int edges; ∥接矩阵的边数组,假设权值为整数 public int n,e: /顶点数,边数 ; public VertexType [ vexs;/存放顶点信息 主要特点:一个图的邻接矩阵表示是唯一的
图的邻接矩阵类型MGraph定义如下： struct VertexType //顶点类型 { public int no; //顶点编号 public string data; //顶点其他信息 }; struct MGraph //图邻接矩阵类型 { public int [,] edges; //邻接矩阵的边数组，假设权值为整数 public int n,e; //顶点数，边数 public VertexType [] vexs; //存放顶点信息 }; 主要特点：一个图的邻接矩阵表示是唯一的
722邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结合 的存储方法。在表示含n个顶点的图的邻接表中,每个顶点 建立一个单链表,第i(0≤n-1)个单链表中的结点表示依 附于顶点的边(对有向图是以顶点为尾的边)。每个单链 表上附设一个表头结点,将所有表头结点构成一个表头结点 数组。边结点(或表结点)和表头结点的结构如下: 边结点(或表结点) 表头结点 adver nextarc weight data firestar 其中,边结点由三个域组成, adjvex指示与顶点邮接 的顶点的编号, nextarc指示下一条边的结点, weight存储 与边相关的信息,如权值等。表头结点由两个组成, data存储顶点名称或其他信息, firstaid指向顶点的链表 中第一个边结点
7.2.2 邻接表存储方法 图的邻接表存储方法是一种顺序分配与链式分配相结合 的存储方法。在表示含n个顶点的图的邻接表中，每个顶点 建立一个单链表，第i（0≤i≤n-1）个单链表中的结点表示依 附于顶点i的边（对有向图是以顶点i为尾的边）。每个单链 表上附设一个表头结点，将所有表头结点构成一个表头结点 数组。边结点（或表结点）和表头结点的结构如下： 其中，边结点由三个域组成，adjvex指示与顶点i邻接 的顶点的编号，nextarc指示下一条边的结点，weight存储 与边相关的信息，如权值等。表头结点由两个域组成， data存储顶点i的名称或其他信息，firstarc指向顶点i的链表 中第一个边结点