图的存储表示.ppt

《图的存储表示.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、图的存储表示在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。设图A=(V,E)是一个有n个顶点的图,图的邻接矩阵是一个二维数组A.edge[n][n]，定义：邻接矩阵(AdjacencyMatrix)无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。在有向图中,统计第i行1的个数可得顶点i的出度，统计第j行1的个数可得顶点j的入度。01230123在无向图中,统计第i行(列)1的个数可得顶点i的度。网络的邻接矩阵863129542031邻接表(AdjacencyList)无向图的邻接表同一个顶点发出的边链接在同一个边链表中，

2、每一个链结点代表一条边(边结点),结点中有另一顶点的下标adjvex和指针nextarc。ABCDdatafirstarcABCD0123adjvexnextarc130210adjvexnextarc有向图的邻接表和逆邻接表ABCdatafirstarcABC012邻接表(出边表)ABC012逆邻接表(入边表)102011adjvexnextarcadjvexnextarcadjvexnextarcdatafirstarc网络(带权图)的邻接表BACD69528ABCD01231536283219(出边表)(顶点表)Adjvexinfonextar

3、cdatafirstarc带权图的边结点中保存该边上的权值info。顶点i的边链表的表头指针firstarc在顶点表的下标为i的顶点记录中，该记录还保存了该顶点的其它信息。在邻接表的边链表中，各个边结点的链入顺序任意，视边结点输入次序而定。设图中有n个顶点，e条边，则用邻接表表示无向图时，需要n个顶点结点，2e个边结点；用邻接表表示有向图时，若不考虑逆邻接表，只需n个顶点结点，e个边结点。十字链表是有向图的另一种存储结构在用邻接表表示有向图时,有时需要同时使用邻接表和逆邻接表。用有向图的十字链表可把两个表结合起来表示。边结点的结构tailtexheadtexhlinktlink

4、info其中，tailtex和headtex指明该有向边始顶点和终顶点的位置。顶点结点的结构每个顶点有一个结点，它相当于出边表和入边表的表头结点：其中，数据成员data存放与该顶点相关的信息，指针Firstin指示以该顶点为弧头的第一个弧结点，Firstout指示以该顶点为弧尾的第一个弧结点。dataFirstinFirstouthlink是指向弧头相同的下一条弧的指针；tlink是指向弧尾相同的下一条弧的指针。Info指向该弧的相关信息。有向图的十字链表tvexhvexhlinktlink010312233440e1e2e3e4e5e6dataFinFou

5、tABCDE01234e1e2e3e4e5e6ABCDE邻接多重表(AdjacencyMultilist)是无向图的另一种链式存储结构在邻接多重表中,每一条边只有一个边结点。为有关边的处理提供了方便。边结点的结构markvertex1path1vertex2path2其中,mark是记录是否处理过的标记;vertex1和vertex2是该边两顶点位置。path1域是链接指针,指向下一条依附顶点vertex1的边；path2是指向下一条依附顶点vertex2的边链接指针。顶点结点的结构存储顶点信息的结点表以顺序表方式组织,每一个顶点结点有两个数据成员：其中，data存放与该顶点相

6、关的信息，Firstout是指示第一条依附该顶点的边的指针。在邻接多重表中,所有依附同一个顶点的边都链接在同一个单链表中。从顶点i出发,可以循链找到所有依附于该顶点的边，也可以找到它的所有邻接顶点。dataFirstout需要时还可设置一个存放与该边相关的权值的域cost。markvtx1path1vtx2path2010321234124dataFoutABCDE01234e1e2e3e4e5e6ABCDEe1e4e2e3e5e6