因为后面即将发布的大量有关“图”的算法与源代码都需要用到下面的这些基础数据，为避免大家去下载，特意先发布于此。
一、图（Graph）的基础知识
图（Graph）是一组对象的图示，其中一些对象对通过链接连接。互连对象由称为顶点的点表示，连接顶点的链接称为边。
形式上，图是一对集（V，E），其中V是顶点集，E是连接顶点对的边集。
图形数据结构
数学图可以用数据结构表示。我们可以使用顶点数组和二维边数组来表示图。在继续之前，让我们先熟悉一些重要的术语−
顶点− 图的每个节点都表示为一个顶点。在以下示例中，带标签的圆表示顶点。因此，A到G是顶点。我们可以使用下图所示的数组来表示它们。这里A可以通过索引0来标识。B可以使用索引1等进行识别。
边− 边表示两个顶点之间的路径或两个顶点之间的线。在以下示例中，从A到B、B到C等的线表示边。我们可以使用二维数组来表示数组，如下图所示。这里AB可以表示为第0行第1列的1，BC可以表示为第1行第2列的1，依此类推，其他组合保持为0。
邻接关系− 如果两个节点或顶点通过边相互连接，则它们是相邻的。在以下示例中，B与A相邻，C与B相邻，依此类推。
路径− 路径表示两个顶点之间的边序列。
二、图的基本操作
以下是图形的基本主要操作：
添加顶点 — 将顶点添加到图形中。
添加边 — 在图形的两个顶点之间添加边。
显示顶点 — 显示图形的顶点。
遍历 — 深度优先遍历，宽度优先遍历；
布局 — 图的布局算法
三、图的相关数据
1、节点
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
///
/// 图的结点（坐标）信息
///
public class Node
{
///
/// 编号
///
public int Id { get; set; } = 0;
///
/// X坐标
///
public double X { get; set; } = 0.0;
///
/// Y坐标
///
public double Y { get; set; } = 0.0;
//public int Weight { get; set; } = 0;
///
/// 默认构造函数
///
public Node()
{
}
public Node(int id)
{
Id = id;
}
///
/// 长度（原点距离）
///
public double Length
{
get
{
double len = LengthSquare;
if (Math.Abs(len)
2、边
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public class Edge
{
///
/// 起点（第一点）编号
///
public int First { get; set; } = -1;
///
/// 终点（第二点）编号
///
public int Second { get; set; } = -1;
///
/// 权值
///
public int Weight { get; set; } = 0;
///
/// 默认构造函数
///
public Edge()
{
}
///
/// 两点构造函数
///
///
///
public Edge(int f, int s)
{
First = f;
Second = s;
}
///
/// 两点及权值构造函数
///
///
///
///
public Edge(int f, int s, int w)
{
First = f;
Second = s;
Weight = w;
}
}
}
3、图
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public partial class Graph
{
///
/// 是否为有向图？
///
public bool Direction { get; set; } = false;
/*
///
/// 节点编码的起始编号0或1
///
public int Node_Index_Start { get; set; } = 0;
///
/// 节点编码的结束编号
///
public int Node_Index_End { get; set; } = 0;
*/
///
/// 节点总数
///
public int Node_Number { get; set; } = 0;
/*
///
/// 连线编码的起始编号0或1
///
public int Edge_Start { get; set; } = 0;
*/
///
/// 连接线总数
///
public int Edge_Number { get; set; } = 0;
///
/// 节点编码列表
///
public List Nodes { get; set; } = new List();
///
/// 连接线列表
///
public List Edges { get; set; } = new List();
///
/// 节点邻接表
///
public List[] Adjacency { get; set; } = null;
///
/// 邻接矩阵
///
public int[,] Matrix { get; set; } = null;
public Graph()
{
}
public Graph(int v, int e = 0, bool direct = false)
{
Direction = direct;
Node_Number = v;
Edge_Number = e;
Adjacency = new List[Node_Number + 1];
for (int i = 0; i t.Id == a))
{
Nodes.Add(new Node(a));
}
}
///
/// 按三元组构造图数据
/// 三元数组为: {source,destination,weight}
///
/// 三元数据
public Graph(int[,] ternary_array, bool dir = false)
{
// 有向图？无向图？
Direction = dir;
Nodes = new List();
Edges = new List();
Edge_Number = ternary_array.GetLength(0);
for (int i = 0; i 0 有连接线及weight
///
/// 节点数
/// 连边数
/// 关联矩阵
public Graph(int[,] matrix)
{
Node_Number = matrix.GetLength(0);
Nodes = new List();
Edges = new List();
Matrix = new int[Node_Number, Node_Number];
for (int i = 0; i 0)
{
AddEdge(i, j, matrix[i, j]);
Matrix[i, j] = matrix[i, j];
}
}
}
}
public Edge FindEdge(int a, int b)
{
foreach (Edge e in Edges)
{
if (e.First == a && e.Second == b)
{
return e;
}
if (Direction == false)
{
if (e.First == b && e.Second == a)
{
return e;
}
}
}
return null;
}
///
/// 按邻接表的构造函数
///
///
public Graph(List adj, bool dir = false)
{
// 有向图？无向图？
Direction = dir;
Node_Number = adj.Count;
Nodes = new List();
Edges = new List();
// 邻接矩阵
Adjacency = adj.ToArray();
int idx = 1;
foreach (List xu in adj)
{
foreach (int xv in xu)
{
AddEdge(idx, xv);
}
idx++;
}
}
///
/// 邻接表 转为 邻接矩阵
/// 1 起步！
///
///
public int[,] AdjacencyMatrix()
{
if (Matrix == null)
{
Matrix = new int[Node_Number + 1, Node_Number + 1];
int idx = 0;
foreach (List xu in Adjacency)
{
// 因为 Adjacency[0] 没有被使用！跳过！
if (idx > 0)
{
foreach (int xv in xu)
{
Matrix[idx, xv] = 1;
}
}
idx++;
}
}
return Matrix;
}
}
}
POWER BY TRUFFER.CN
