如何在C#中表示一个给定为邻接列表的图

本文关键字：列表 一个 表示 | 更新日期: 2023-09-27 18:19:52

我将对各种图算法进行编程，作为输入，我已经给出了邻接列表形式的图。

这里有一个例子：

1 2 3 4

2 1 3 4

3 1 2 4

4 1 2 3 5

5 4 6

6 5

该图有6个顶点，由6行表示（每行的第一个条目表示代表该行的顶点的编号）。一行中的其余条目表示与该行对应的顶点相邻的顶点。

在C#中表示这一点的好方法是什么？每行中不同数量的条目似乎排除了一个数组，所以我找到了这些列表。

我要处理图，例如收缩边，我正在寻找一种数据结构，在这种结构中，图操作是可能的，也是有效的。

如何在C#中表示一个给定为邻接列表的图

看起来像是一个以整数列表作为值结构的字典很有用：

using System;
using System.Collections.Generic;
class Program
{
    static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary <int, List<int>>();
        graph[1] = new List<int> {2, 3, 4};
        graph[2] = new List<int> {1, 3, 4};
        graph[3] = new List<int> {1, 2, 4};
        graph[4] = new List<int> {1, 2, 3, 5};
        graph[5] = new List<int> {4, 6};
        graph[6] = new List<int> {5};
    }
}

当我有类似的任务时，我发现拥有以下类很容易：

    class Edge
    {
    public Node From;
    public Node To;
    }
    class Node
    {
         public List<Edge> EdgesIn;
         public List<Edge> EdgesOut;
    }
    class Graph
    {
         public List<Node> Nodes;
    }

如果您将选择自定义类的编码来处理图这些信息可能会有所帮助。但是java 上的所有信息

我发现表示图的一种方便方法是GraphSON格式。您可以在这里查看：GraphSON格式。一个例子：

{
   "graph": {
       "mode":"NORMAL",
       "vertices": [
           {
               "_id": "1",
               "_type": "vertex"
           },
           {
               "_id": "2",
               "_type": "vertex"
           },
           {
               "_id": "3",
               "_type": "vertex"
           }
       ],
       "edges": [
           {
               "weight": 1,
               "_id": "11",
               "_type": "edge",
               "_outV": "2",
               "_inV": "1"
           },
           {
               "weight": 0.5,
               "_id": "12",
               "_type": "edge",
               "_outV": "3",
               "_inV": "2"
           }
       ]
   }
}

C#中的邻接列表工作示例。C#中边缘到相邻列表的转换

            int[][] edges = new int[][]
            {
                new int[] { 0, 1 },
                new int[] { 1, 2 },
                new int[] { 2, 0 }
            };
            var graph = new Dictionary<int, List<int>>();
            for (int i = 0; i < edges.Length; i++)
            {
                var pair = edges[i];
                if (!graph.ContainsKey(pair[0])) graph.Add(pair[0], new List<int>());
                if (!graph.ContainsKey(pair[1])) graph.Add(pair[1], new List<int>());
                graph[pair[0]].Add(pair[1]);
                graph[pair[1]].Add(pair[0]);
            }
相关文章：