如何在C#中表示给定的邻接表图？

Question

我将编写各种图算法，输入为邻接列表形式的图。以下是一个示例：该图有6个顶点，由6行表示（每行的第一个条目表示该行所代表的顶点编号）。行中的其余条目表示与该行所对应的顶点相邻的顶点。如何在C#中表示这个图？每行中不同的条目数似乎排除了数组，因此我找到了这些列表的列表。我将操作图形，例如合并边缘，我正在寻找一种数据结构，使图形操作既可能又有效。

- HowDoICSharply

---

https://dev59.com/F7D2oIgBc1ULPQZF9wA7#73504595 - KushalSeth

Answer 1

看起来带有整数列表作为值结构的字典可能会很有用：

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};
    }
}

- Vadim

Answer 2

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

代码如下：

    class Edge
    {
    public Node From;
    public Node To;
    }

    class Node
    {
         public List<Edge> EdgesIn;
         public List<Edge> EdgesOut;
    }

    class Graph
    {
         public List<Node> Nodes;
    }

- michaelb

---

谢谢。这是否意味着我需要为图中的每个节点和边创建一个Node对象和一个Edge对象？我想知道如果我有一个大图，比如Facebook图，其中用户作为节点，用户之间的关系作为边，那么跟踪那么多对象在性能方面会很困难吗？ - HowDoICSharply

Answer 3

如果您选择编写自定义类来处理图形，此信息可能会有所帮助。但这里的所有信息都是关于java的。

- isxaker

Answer 4

我发现一种方便的图形表示方式是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"
           }
       ]
   }
}

- inigo333

Answer 5

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]);
            }

- KushalSeth