湖南营销型网站建设 A磐石网络,公司网站建设哪儿济南兴田德润实惠吗,网站建设的整体流程,南宁市学生网页设计因为后面即将发布的大量有关“图”的算法与源代码都需要用到下面的这些基础数据#xff0c;为避免大家去下载#xff0c;特意先发布于此。 一、图#xff08;Graph#xff09;的基础知识
图#xff08;Graph#xff09;是一组对象的图示#xff0c;其中一些对象对通过链…
因为后面即将发布的大量有关“图”的算法与源代码都需要用到下面的这些基础数据为避免大家去下载特意先发布于此。 一、图Graph的基础知识
图Graph是一组对象的图示其中一些对象对通过链接连接。互连对象由称为顶点的点表示连接顶点的链接称为边。
形式上图是一对集VE其中V是顶点集E是连接顶点对的边集。
图形数据结构
数学图可以用数据结构表示。我们可以使用顶点数组和二维边数组来表示图。在继续之前让我们先熟悉一些重要的术语−
顶点− 图的每个节点都表示为一个顶点。在以下示例中带标签的圆表示顶点。因此A到G是顶点。我们可以使用下图所示的数组来表示它们。这里A可以通过索引0来标识。B可以使用索引1等进行识别。
边− 边表示两个顶点之间的路径或两个顶点之间的线。在以下示例中从A到B、B到C等的线表示边。我们可以使用二维数组来表示数组如下图所示。这里AB可以表示为第0行第1列的1BC可以表示为第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
{/// summary/// 图的结点坐标信息/// /summarypublic class Node{/// summary/// 编号/// /summarypublic int Id { get; set; } 0;/// summary/// X坐标/// /summarypublic double X { get; set; } 0.0;/// summary/// Y坐标/// /summarypublic double Y { get; set; } 0.0;//public int Weight { get; set; } 0;/// summary/// 默认构造函数/// /summarypublic Node() {}public Node(int id) {Id id;}/// summary/// 长度原点距离/// /summarypublic double Length{get{double len LengthSquare;if (Math.Abs(len) float.Epsilon) return 0.0;return Math.Sqrt(len);}}/// summary/// 长度平方/// /summarypublic double LengthSquare{get{return (X * X) (Y * Y);}}/// summary/// 缩放/// /summary/// param namerate/parampublic void Scale(double rate){X * rate;Y * rate;}/// summary/// 移动到目的点/// /summary/// param namex/param/// param namey/parampublic void MoveTo(double x, double y){X x;Y y;}/// summary/// 移动/// /summary/// param namedelta/parampublic void Move(Node delta){this.X delta.X;this.Y delta.Y;}/// summary/// 加号重载/// /summary/// param namea/param/// param nameb/param/// returns/returnspublic static Node operator (Node a, Node b){Node c new Node();c.X a.X b.X;c.Y a.Y b.Y;return c;}/// summary/// 减号重载/// /summary/// param namea/param/// param nameb/param/// returns/returnspublic static Node operator -(Node a, Node b){Node c new Node();c.X a.X - b.X;c.Y a.Y - b.Y;return c;}}
}2、边
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{public class Edge{/// summary/// 起点第一点编号/// /summarypublic int First { get; set; } -1;/// summary/// 终点第二点编号/// /summarypublic int Second { get; set; } -1;/// summary/// 权值/// /summarypublic int Weight { get; set; } 0;/// summary/// 默认构造函数/// /summarypublic Edge(){}/// summary/// 两点构造函数/// /summary/// param namef/param/// param names/parampublic Edge(int f, int s){First f;Second s;}/// summary/// 两点及权值构造函数/// /summary/// param namef/param/// param names/param/// param namew/parampublic 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{/// summary/// 是否为有向图/// /summarypublic bool Direction { get; set; } false;/*/// summary/// 节点编码的起始编号0或1/// /summarypublic int Node_Index_Start { get; set; } 0;/// summary/// 节点编码的结束编号/// /summarypublic int Node_Index_End { get; set; } 0;*//// summary/// 节点总数/// /summarypublic int Node_Number { get; set; } 0;/*/// summary/// 连线编码的起始编号0或1/// /summarypublic int Edge_Start { get; set; } 0;*//// summary/// 连接线总数/// /summarypublic int Edge_Number { get; set; } 0;/// summary/// 节点编码列表/// /summarypublic ListNode Nodes { get; set; } new ListNode();/// summary/// 连接线列表/// /summarypublic ListEdge Edges { get; set; } new ListEdge();/// summary/// 节点邻接表/// /summarypublic Listint[] Adjacency { get; set; } null;/// summary/// 邻接矩阵/// /summarypublic 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 Listint[Node_Number 1];for (int i 0; i Node_Number; i){Adjacency[i] new Listint();}}public void AddEdge(int a, int b){Adjacency[a].Add(b);if (Direction false){Adjacency[b].Add(a);}}public void AddEdge(int a, int b, int w){AddEdge(a, b);Edges.Add(new Edge(a, b, w));}public void AddEdge(int idx, int a, int b, int w){Edges[idx] new Edge(a, b, w);}public void AddNode(int a){if (!Nodes.Exists(t t.Id a)){Nodes.Add(new Node(a));}}/// summary/// 按三元组构造图数据/// 三元数组为: {source,destination,weight}/// /summary/// param nameternary_array三元数据/parampublic Graph(int[,] ternary_array, bool dir false){// 有向图无向图Direction dir;Nodes new ListNode();Edges new ListEdge();Edge_Number ternary_array.GetLength(0);for (int i 0; i ternary_array.GetLength(0); i){int n1 ternary_array[i, 0];int n2 ternary_array[i, 1];int wt ternary_array[i, 2];AddEdge(n1, n2, wt);}}/// summary/// 按关联矩阵数据构建图/// [N x N]元素0无连接0 有连接线及weight/// /summary/// param namev节点数/param/// param namee连边数/param/// param namematrix关联矩阵/parampublic Graph(int[,] matrix){Node_Number matrix.GetLength(0);Nodes new ListNode();Edges new ListEdge();Matrix new int[Node_Number, Node_Number];for (int i 0; i Node_Number; i){for (int j 0; j Node_Number; j){if (matrix[i, j] 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;}/// summary/// 按邻接表的构造函数/// /summary/// param nameadj/parampublic Graph(ListListint adj, bool dir false){// 有向图无向图Direction dir;Node_Number adj.Count;Nodes new ListNode();Edges new ListEdge();// 邻接矩阵Adjacency adj.ToArray();int idx 1;foreach (Listint xu in adj){foreach (int xv in xu){AddEdge(idx, xv);}idx;}}/// summary/// 邻接表 转为 邻接矩阵/// 1 起步/// /summary/// returns/returnspublic int[,] AdjacencyMatrix(){if (Matrix null){Matrix new int[Node_Number 1, Node_Number 1];int idx 0;foreach (Listint xu in Adjacency){// 因为 Adjacency[0] 没有被使用跳过if (idx 0){foreach (int xv in xu){Matrix[idx, xv] 1;}}idx;}}return Matrix;}}
}POWER BY TRUFFER.CN
