在图论中，图可以根据边的特性被分为不同的类型。加权图和非加权图是两种常见的图类型，它们在算法设计和数据结构的应用中扮演着重要的角色。

非加权图

非加权图是一种简单的图，其中所有的边都是没有权重的，或者可以认为每条边的权重都是相同的。在非加权图中，边仅仅表示节点之间的连接关系，而不提供其他的信息。非加权图常用于表示是否存在某种关系，比如社交网络中的朋友关系或计算机网络中的连接。

示例

考虑一个简单的社交网络，其中节点代表个人，边代表他们之间的朋友关系。

XML
Alice -- Bob
  | \
  |  Charlie
  |
Dave

在这个非加权图示例中，Alice、Bob、Charlie和Dave是网络中的个人，边表示他们之间的朋友关系。

加权图

加权图是图的另一种形式，它的边附带了权重信息。权重可以表示边的长度、成本、时间或任何其他的度量标准。加权图在多种场景中都有应用，如路径规划、网络流量分析和最小生成树等问题。

示例

考虑一个城市地图，其中节点代表城市，边代表城市之间的道路，边的权重代表道路的长度（或旅行时间）。

XML
Alice -5- Bob
  | \
3 |  2 Charlie
  |
1 Dave

在这个加权图示例中，数字代表从一个城市到另一个城市的道路长度。例如，从Alice到Bob的距离是5个单位，而从Alice到Charlie的距离是2个单位。

C#中的图表示

在C#中，我们可以通过定义类和使用集合类型来表示加权图和非加权图。

非加权图的表示

C#
using System;
using System.Collections.Generic;

public class Graph
{
    private Dictionary<string, HashSet<string>> adjacencyList;

    public Graph()
    {
        adjacencyList = new Dictionary<string, HashSet<string>>();
    }

    public void AddEdge(string vertex1, string vertex2)
    {
        if (!adjacencyList.ContainsKey(vertex1))
            adjacencyList[vertex1] = new HashSet<string>();

        if (!adjacencyList.ContainsKey(vertex2))
            adjacencyList[vertex2] = new HashSet<string>();

        adjacencyList[vertex1].Add(vertex2);
        adjacencyList[vertex2].Add(vertex1);
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList)
        {
            Console.Write(vertex.Key + ": ");
            foreach (var edge in vertex.Value)
                Console.Write(edge + " ");
            Console.WriteLine();
        }
    }
}

调用

C#
static void Main(string[] args)
{
    // 创建一个新的无向无权图
    Graph socialNetwork = new Graph();

    // 添加边来表示朋友关系
    socialNetwork.AddEdge("Alice", "Bob");
    socialNetwork.AddEdge("Alice", "Charlie");
    socialNetwork.AddEdge("Alice", "Dave");
    socialNetwork.AddEdge("Bob", "Charlie");

    // 打印出图的邻接列表表示
    socialNetwork.PrintGraph();
}

加权图的表示

C#
using System;
using System.Collections.Generic;

public class WeightedGraph
{
    private Dictionary<string, Dictionary<string, int>> adjacencyList;

    public WeightedGraph()
    {
        adjacencyList = new Dictionary<string, Dictionary<string, int>>();
    }

    public void AddEdge(string vertex1, string vertex2, int weight)
    {
        if (!adjacencyList.ContainsKey(vertex1))
            adjacencyList[vertex1] = new Dictionary<string, int>();

        if (!adjacencyList.ContainsKey(vertex2))
            adjacencyList[vertex2] = new Dictionary<string, int>();

        adjacencyList[vertex1][vertex2] = weight;
        adjacencyList[vertex2][vertex1] = weight;
    }

    public void PrintGraph()
    {
        foreach (var vertex in adjacencyList)
        {
            Console.Write(vertex.Key + ": ");
            foreach (var edge in vertex.Value)
                Console.Write($"{edge.Key}({edge.Value}) ");
            Console.WriteLine();
        }
    }
}

调用

C#
static void Main(string[] args)
{
    // 创建一个新的加权图
    WeightedGraph cityMap = new WeightedGraph();

    // 添加边来表示城市之间的道路及其权重
    cityMap.AddEdge("Alice", "Bob", 5);
    cityMap.AddEdge("Alice", "Charlie", 2);
    cityMap.AddEdge("Alice", "Dave", 1);
    cityMap.AddEdge("Bob", "Charlie", 3);

    // 打印出图的邻接列表表示
    cityMap.PrintGraph();
}

在上述代码中，Graph类表示一个非加权图，使用邻接表存储图的连接关系。WeightedGraph类表示一个加权图，使用一个嵌套的字典来存储每个顶点及其相邻顶点和对应的权重。

总结

加权图和非加权图是图论中的两个基本概念，它们在算法设计和数据结构的实际应用中扮演着重要的角色。非加权图适用于只需要表示连接关系的场景，而加权图适用于需要考虑边的权重信息的复杂场景。在C#中，我们可以通过创建自定义的数据结构来有效地表示和操作这些图。