using System;
|
using System.Collections.Generic;
|
using System.Linq;
|
using System.Text;
|
using System.Threading.Tasks;
|
using System.Threading;
|
using System.Drawing;
|
using static test.Graphics;
|
|
namespace test
|
{
|
|
|
|
|
|
class Program
|
{
|
|
//static void GetN(person p)
|
//{
|
// p = new person();
|
// p.age = 2;
|
//}
|
|
|
static void Main(string[] args)
|
{
|
|
|
|
|
|
|
|
//ZTPoint A = new ZTPoint(0, 1);
|
//ZTPoint B = new ZTPoint(1, 0);
|
//ZTPoint C = new ZTPoint(3, 0);
|
//ZTPoint D = new ZTPoint(4, 1);
|
//ZTPoint E = new ZTPoint(3, 2);
|
//ZTPoint F = new ZTPoint(2, 1);
|
//ZTPoint G = new ZTPoint(1, 2);
|
|
//var edges = new List<Tuple<ZTPoint, ZTPoint, double>>()
|
//{
|
// new Tuple<ZTPoint,ZTPoint,double>(A,B,12),
|
// new Tuple<ZTPoint,ZTPoint,double>(A,F,16),
|
// new Tuple<ZTPoint,ZTPoint,double>(A,G,14),
|
// new Tuple<ZTPoint,ZTPoint,double>(B,F,7),
|
// new Tuple<ZTPoint,ZTPoint,double>(B,C,10),
|
// new Tuple<ZTPoint,ZTPoint,double>(G,F,9),
|
// new Tuple<ZTPoint,ZTPoint,double>(G,E,8),
|
// new Tuple<ZTPoint,ZTPoint,double>(F,C,6),
|
// new Tuple<ZTPoint,ZTPoint,double>(F,E,2),
|
// new Tuple<ZTPoint,ZTPoint,double>(C,D,3),
|
// new Tuple<ZTPoint,ZTPoint,double>(C,E,5),
|
// new Tuple<ZTPoint,ZTPoint,double>(E,D,4),
|
//};
|
|
//var dij = new Dijkstra(edges);
|
//var path = dij.Find(D, G);
|
|
//for (int i = 0; i < path.Count; i++)
|
//{
|
// Console.WriteLine(path[i].ToString());
|
//}
|
|
|
Console.WriteLine("finish!~");
|
Console.ReadKey();
|
}
|
}
|
|
|
/// <summary>
|
/// 图
|
/// </summary>
|
public class Graphics
|
{
|
public const int MaxSize = 6;
|
public const int INF = 32767; //INF表示∞
|
public const int MAXV = 4; //最大顶点个数
|
//结构体的成员定义里不能直接赋值，也就是等号后的应该移除，在你后面实例化整个结构体以后，
|
//再对Study_Data[n].input=new double[50] 其他成员类似。顺便说下其实用class简单得多。
|
|
public struct VertexType
|
{
|
public string VexNo; //顶点编号
|
public string VexName; //顶点名称
|
public string otherInfo; //顶点其他信息
|
}; //顶点类型
|
public struct MGraph //图的定义
|
{
|
public int[,] edges; //邻接矩阵
|
public int n, e; //顶点数,弧数
|
public VertexType[] vexs; //存放顶点信息
|
}; //图的邻接矩阵类型
|
|
static void Ppath(int[] path, int i, int v) //前向递归查找路径上的顶点
|
{
|
int k;
|
k = path[i];
|
if (k == v) return; //找到了起点则返回
|
Ppath(path, k, v); //找顶点k的前一个顶点v
|
|
Console.Write("{0},", k); //输出路径上的终点
|
// Ppath(path, k, j); //找顶点k的前一个顶点j
|
}
|
|
static void Ppath(MGraph g, int[] path, int i, int v) //前向递归查找路径上的顶点
|
{
|
int k;
|
k = path[i];
|
if (k == v) return; //找到了起点则返回
|
Ppath(path, k, v); //找顶点k的前一个顶点v
|
|
Console.Write("{0},", g.vexs[k].VexName); //输出路径上的终点
|
// Ppath(path, k, j); //找顶点k的前一个顶点j
|
}
|
|
static void Dispath(int[] dist, int[] path, int[] s, int n, int v)
|
{
|
int i;
|
for (i = 0; i < n; i++)
|
{
|
if (s[i] == 1)
|
{
|
Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", v, i, dist[i]);
|
Console.Write("{0},", v); //输出路径上的起点
|
Ppath(path, i, v); //输出路径上的中间点
|
Console.WriteLine("{0}", i); //输出路径上的终点
|
}
|
else
|
Console.WriteLine("从{0}到{1}不存在路径\n", v, i);
|
}
|
}
|
|
static void PutBothpath(MGraph g, int[] dist, int[] path, int[] s, int n, int v, int m)
|
{
|
int i;
|
for (i = 0; i < n; i++)
|
{
|
if (s[i] == 1)
|
{
|
//Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", v, i, dist[i]);
|
//Console.Write("{0},", v); //输出路径上的起点
|
//Ppath(path, i, v); //输出路径上的中间点
|
//Console.WriteLine("{0}", i); //输出路径上的终点
|
if (i == m && dist[i] < INF)
|
{
|
Console.Write(" 从{0}到{1}的最短路径长度为:{2}\t路径为:", g.vexs[v].VexName, g.vexs[i].VexName, dist[i]);
|
Console.Write("{0},", g.vexs[v].VexName); //输出路径上的起点
|
//Ppath(path, i, v); //输出路径上的中间点
|
Ppath(g, path, i, v);
|
Console.WriteLine("{0}", g.vexs[i].VexName); //输出路径上的终点
|
}
|
}
|
else
|
Console.WriteLine("从{0}到{1}不存在路径\n", v, i);
|
}
|
}
|
|
public static void Dijkstra(MGraph g, int v)
|
{
|
int[] dist = new int[MAXV];//从原点v到其他的各定点当前的最短路径长度
|
int[] path = new int[MAXV];//path[i]表示从原点到定点i之间最短路径的前驱节点
|
int[] s = new int[MAXV]; //选定的顶点的集合
|
int mindis, i, j, u;
|
u = 0;
|
for (i = 0; i < g.n; i++)
|
{
|
dist[i] = g.edges[v, i]; //距离初始化
|
s[i] = 0; //s[]置空 0表示i不在s集合中
|
if (g.edges[v, i] < INF) //路径初始化
|
path[i] = v;
|
else
|
path[i] = -1;
|
}
|
s[v] = 1; //源点编号v放入s中
|
path[v] = 0;
|
for (i = 0; i < g.n; i++) //循环直到所有顶点的最短路径都求出
|
{
|
mindis = INF; //mindis置最小长度初值
|
for (j = 0; j < g.n; j++) //选取不在s中且具有最小距离的顶点u
|
if (s[j] == 0 && dist[j] < mindis)
|
{
|
u = j;
|
mindis = dist[j];
|
}
|
s[u] = 1; //顶点u加入s中
|
for (j = 0; j < g.n; j++) //修改不在s中的顶点的距离
|
if (s[j] == 0)
|
if (g.edges[u, j] < INF && dist[u] + g.edges[u, j] < dist[j])
|
{
|
dist[j] = dist[u] + g.edges[u, j];
|
path[j] = u;
|
}
|
}
|
Dispath(dist, path, s, g.n, v); //输出最短路径
|
//PutBothpath(g, dist, path, s, g.n, v, 3);
|
}
|
|
static void initdata()
|
{
|
int i, j;
|
MGraph g;
|
g.n = 4; g.e = 8;
|
g.edges = new int[MAXV, MAXV];
|
g.vexs = new VertexType[MAXV];
|
//int [,] anArray = new int [2, 4] {{1,2,3,4},{5,6,7,8}};
|
int[,] a = new int[MAXV, MAXV] {
|
{0, 5,INF,7},
|
{INF,0, 4,2},
|
{3, 3, 0,2},
|
{INF,INF,1,0}
|
};
|
|
for (i = 0; i < g.n; i++) //建立图的图的邻接矩阵
|
{
|
for (j = 0; j < g.n; j++)
|
{
|
g.edges[i, j] = a[i, j];///////////////////////////////////////////////
|
}
|
}
|
Console.WriteLine("各顶点的最短路径:");
|
}
|
|
public static void initialVexInfo(MGraph g)
|
{
|
g.vexs[0].VexNo = "0361";
|
g.vexs[0].VexName = "西安";
|
|
g.vexs[1].VexNo = "010";
|
g.vexs[1].VexName = "北京";
|
|
g.vexs[2].VexNo = "0681";
|
g.vexs[2].VexName = "武汉";
|
|
g.vexs[3].VexNo = "0571";
|
g.vexs[3].VexName = "杭州";
|
}
|
}
|
|
|
//public class StationSched
|
//{
|
// /// <summary>
|
// /// 所有的站点信息
|
// /// </summary>
|
// List<StationInfo> stations = new List<StationInfo>();
|
|
// /// <summary>
|
// /// 线路信息
|
// /// </summary>
|
// List<ShipInfo> lines = new List<ShipInfo>();
|
|
// /// <summary>
|
// /// 构造函数，初始化站点和线路信息
|
// /// </summary>
|
// public StationSched()
|
// {
|
// stations.Add(new StationInfo() { Sid = 1, Lid = 1 });//0
|
// stations.Add(new StationInfo() { Sid = 2, Lid = 1 });//1
|
// stations.Add(new StationInfo() { Sid = 3, Lid = 1 });//2
|
// stations.Add(new StationInfo() { Sid = 4, Lid = 1 });//3
|
// stations.Add(new StationInfo() { Sid = 5, Lid = 1 });//4
|
// stations.Add(new StationInfo() { Sid = 6, Lid = 1 });//5
|
// stations.Add(new StationInfo() { Sid = 7, Lid = 1 });//6
|
|
// stations.Add(new StationInfo() { Sid = 19, Lid = 2 });//7
|
// stations.Add(new StationInfo() { Sid = 18, Lid = 2 });
|
// stations.Add(new StationInfo() { Sid = 17, Lid = 2 });
|
// stations.Add(new StationInfo() { Sid = 3, Lid = 2 });
|
// stations.Add(new StationInfo() { Sid = 13, Lid = 2 });
|
// stations.Add(new StationInfo() { Sid = 16, Lid = 2 });
|
|
|
// stations.Add(new StationInfo() { Sid = 15, Lid = 3 });//13
|
// stations.Add(new StationInfo() { Sid = 14, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 13, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 12, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 11, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 5, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 10, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 9, Lid = 3 });
|
// stations.Add(new StationInfo() { Sid = 8, Lid = 3 });
|
|
// for (int i = 0; i < 6; i++)
|
// {
|
// lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
|
// }
|
// for (int i = 6; i > 0; i--)
|
// {
|
// lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
|
// }
|
|
// for (int i = 7; i < 12; i++)
|
// {
|
// lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
|
// }
|
// for (int i = 12; i > 7; i--)
|
// {
|
// lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
|
// }
|
|
// for (int i = 13; i < 21; i++)
|
// {
|
// lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i + 1] });
|
// }
|
// for (int i = 21; i > 13; i--)
|
// {
|
// lines.Add(new ShipInfo() { Curr = stations[i], Next = stations[i - 1] });
|
// }
|
|
// }
|
|
// /// <summary>
|
// /// 获取sid站点可以到达的站点信息，去除已经计算过的preid站点
|
// /// </summary>
|
// /// <param name="preid"></param>
|
// /// <param name="sid"></param>
|
// /// <returns></returns>
|
// public List<StationInfo> GetNext(int preid, int sid)
|
// {
|
// List<StationInfo> list = new List<StationInfo>();
|
// foreach (var item in lines)
|
// {
|
// if (item.Curr.Sid == sid && item.Next.Sid != preid) list.Add(item.Next);
|
// }
|
// return list;
|
// }
|
|
// /// <summary>
|
// /// 获取线路信息
|
// /// </summary>
|
// /// <param name="s">起始站点编号</param>
|
// /// <param name="e">结束站点编号</param>
|
// /// <returns></returns>
|
// public List<string> GetResult(int s, int e)
|
// {
|
// List<List<int>> temp = GetLine(s, e);
|
// List<string> result = new List<string>();
|
// List<List<int>> line = new List<List<int>>();
|
// foreach (var item in temp)
|
// {
|
// if (item.Count > 0 && item[item.Count - 1] == e)
|
// line.Add(item);
|
// }
|
// string src = "";
|
// int currLine = -1;
|
// foreach (var item in line)
|
// {
|
// currLine = GetLineNumber(item[0], item[1]);
|
// src += "从[" + currLine + "号线]的[" + item[0] + "]上车";
|
// for (int i = 1; i < item.Count; i++)
|
// {
|
// if (i == item.Count - 1)
|
// {
|
// src += ",在[" + item[i] + "]站点下车。";
|
// result.Add(src);
|
// src = "";
|
// break;
|
// }
|
// int tempLine = GetLineNumber(item[i], item[i + 1]);
|
// if (tempLine != currLine)
|
// {
|
// currLine = tempLine;
|
// src += ",在[" + item[i] + "]站点换乘[" + currLine + "号线]";
|
// }
|
// }
|
|
// }
|
|
// return result;
|
// }
|
|
// /// <summary>
|
// /// 根据相邻的两个点取当前的线路
|
// /// </summary>
|
// /// <param name="s"></param>
|
// /// <param name="e"></param>
|
// /// <returns></returns>
|
// private int GetLineNumber(int l, int r)
|
// {
|
// foreach (var item in lines)
|
// {
|
// if ((item.Curr.Sid == l && item.Next.Sid == r) || (item.Curr.Sid == r && item.Next.Sid == l))
|
// return item.Next.Lid;
|
// }
|
// return -1;
|
// }
|
|
// /// <summary>
|
// /// 获取线路的ID集合
|
// /// </summary>
|
// /// <param name="s">起始站点编号</param>
|
// /// <param name="e">结束站点编号</param>
|
// /// <returns></returns>
|
// private List<List<int>> GetLine(int s, int e)
|
// {
|
// List<List<int>> result = new List<List<int>>();
|
// List<int> curr = new List<int>();
|
// curr.Add(s);
|
// result.Add(curr);
|
// int currLine = 0;
|
// int preSid = s;
|
// int currSid = s;
|
// while (true)
|
// {
|
// if (currLine >= result.Count) return result;
|
// currSid = result[currLine][result[currLine].Count - 1];
|
// if (currSid == e)
|
// {
|
// currLine += 1;
|
// continue;
|
// }
|
// if (result[currLine].Count > 1)
|
// preSid = result[currLine][result[currLine].Count - 2];
|
// if (currSid <= 0)
|
// {
|
// currLine += 1;
|
// continue;
|
// }
|
// List<StationInfo> temp = GetNext(preSid, currSid);
|
|
// if (temp.Count == 0)
|
// {//某条线路到头
|
// currLine += 1;
|
// }
|
// else if (temp.Count == 1)
|
// {//不需要换乘继续前进
|
// result[currLine].Add(temp[0].Sid);
|
// }
|
// else
|
// {//需要换乘了。
|
// for (int i = 1; i < temp.Count; i++)
|
// {
|
// if (!result[currLine].Contains(temp[i].Sid))
|
// {//防止死循环，过滤掉已经计算过的站点。
|
// result.Add(result[currLine].GetRange(0, result[currLine].Count));
|
// result[result.Count - 1].Add(temp[i].Sid);
|
// }
|
// }
|
// result[currLine].Add(temp[0].Sid);
|
// }
|
// }
|
// }
|
//}
|
|
|
|
///// <summary>
|
///// 站点信息
|
///// </summary>
|
//public class StationInfo
|
//{
|
// public int Lid { get; set; }
|
// public int Sid { get; set; }
|
|
// public override string ToString()
|
// {
|
// return "Sid:" + Sid + "--Lid:" + Lid;
|
// }
|
//}
|
|
///// <summary>
|
///// 关系信息
|
///// </summary>
|
//public class ShipInfo
|
//{
|
// public StationInfo Curr { get; set; }
|
// public StationInfo Next { get; set; }
|
|
// public override string ToString()
|
// {
|
// return "Curr:" + Curr.Sid + "--Next:" + Next.Sid;
|
// }
|
//}
|
}
|
