数据结构之图 Part2 - 3

时间:2022-09-07 17:33:50

十字链表

简单的说就是邻接表和逆邻接表的合体,解决了原邻接表或者逆邻接表出度和入度的计算无法兼得的问题。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LH.GraphConsole
{
    public struct OrthogonalListGraph
    {
        public NodeItem[] VertexNodes;

        public OrthogonalListGraph(int size)
        {
            VertexNodes = new NodeItem[size];
        }
    }

    public struct NodeItem
    {
        public List<OrthEdgeItem> InList;
        public List<OrthEdgeItem> OutList;

        public NodeItem(List<OrthEdgeItem> inList, List<OrthEdgeItem> outList)
        {
            InList = inList;
            OutList = outList;
        }
    }

    public class OrthEdgeItem
    {
        public int Weight;
        public string Name;

        public OrthEdgeItem(int weight, string name)
        {
            Weight = weight;
            Name = name;
        }
    }
}

简单的主函数:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LH.GraphConsole
{
    class Program
    {
        static void Main(string[] args)
        {
            OrthogonalList();
        }

        private static void OrthogonalList()
        {
            var size = 5;
            var orgthListGraph = new OrthogonalListGraph(size);

            var orgEdge03 = new OrthEdgeItem(1, "edge03");
            var orgEdge10 = new OrthEdgeItem(1, "edge10");
            var orgEdge12 = new OrthEdgeItem(1, "edge12");
            var orgEdge21 = new OrthEdgeItem(1, "edge21");
            var orgEdge20 = new OrthEdgeItem(1, "edge20");

            var inList0 = new List<OrthEdgeItem>();
            inList0.Add(orgEdge10);
            inList0.Add(orgEdge20);

            var outList0 = new List<OrthEdgeItem>();
            outList0.Add(orgEdge03);

            var nodeItem0 = new NodeItem(inList0, outList0);
            var nodeItem1 = new NodeItem();
            var nodeItem2 = new NodeItem();
            var nodeItem3 = new NodeItem();
            var nodeItem4 = new NodeItem();

            orgthListGraph.VertexNodes[0] = nodeItem0;
            orgthListGraph.VertexNodes[1] = nodeItem1;
            orgthListGraph.VertexNodes[2] = nodeItem2;
            orgthListGraph.VertexNodes[3] = nodeItem3;
            orgthListGraph.VertexNodes[4] = nodeItem4;
        }
    }
}

简要说明,只是为了便于理解数据结构,没有刻意的去标准实现,见谅。