C#实现图的邻接矩阵和邻接表结构

本文介绍C#实现图的邻接矩阵和邻接表结构。
逻辑结构分为两部分：V和E集合，其中，V是顶点，E是边。因此，用一个一维数组存放图中所有顶点数据；用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。邻接矩阵又分为有向图邻接矩阵和无向图邻接矩阵
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn} [1] 。G的邻接矩阵是一个具有下列性质的n阶方阵：
①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。

邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。 [1]

程序代码如下所示：
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 图的存储结构
{
using VertexType = System.Char;//顶点数据类型别名声明
using EdgeType = System.Int16;//带权图中边上权值的数据类型别名声明
class Program
{
public const int MAxVertexNum =100;//顶点数目的最大值

    static void Main(string[] args)
    {
    }
    /// <summary>
    /// 图的定义--邻接矩阵
    /// </summary>
    public struct MGraph {
        public VertexType[] vex;//顶点表数组
        public EdgeType[][] Edge;//临接矩阵、边表
        public int vexnum,arcnum;//图的当前顶点数和弧数
    }
    /// <summary>
    /// 图的定义--邻接表法
    /// </summary>
    public class ArcNode {//边表节点
       public int adjvex;
       public  ArcNode next;
    }
    public class VNode {  //顶点表节点
        VertexType data;//顶点信息
        ArcNode first;//只想第一条依附改顶点的弧的指针
    }
    public class ALGraph {
        VNode[] vertices;   //邻接表
        int vexnum, arcnum;//图的顶点数和弧数
    }





}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

}