6. C#數據結構與算法 非線性結構(圖)


图表示点之间的关系,在C#中通过节点对象的集合来表示点(Vertex),用邻接矩阵(adjacency matrix)来表示点之间的关系。下面来看C#实现。

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace Graph
{
//表示点的类
//每个节点包含两个字段,分别为节点数据以及表示是否被访问过的一个布尔类型。
class Vertex
{
public string Data;
public bool IsVisited;
public Vertex(string Vertexdata)
{
Data = Vertexdata;
}
}
//表示图的类
//图中除了需要点的集合和邻接矩阵之外,还需要一些基本的向图中添加或删除元素的方法,以及一个构造方法来对图进行初始化。
public class Graph
{
//图中所能包含的点的上限
public const int Number = 10;
//顶点数组
private Vertex[] vertiexes;
//邻接矩阵
public int[,] adjmatrix;
//统计当前图中有几个点
int numVerts = 0;
//初始化图
public Graph()
{
//初始化邻接矩阵和顶点数组
adjmatrix = new Int32 [Number,Number];
vertiexes = new Vertex[Number];
//将代表邻接矩阵的表全初始化为0
for (int i = 0; i < Number;i++ )
{
for (int j = 0; j < Number; j++)
{
adjmatrix[i, j] = 0;
}
}
}//end Graph()
//向图中添加节点
public void AddVertex(string v)
{
vertiexes[numVerts] = new Vertex(v);
numVerts++;
}
//向图中添加有向边
public void AddEdge(int vertex1, int vertex2)
{
adjmatrix[vertex1,vertex2]=1;
}
//end AddEdge()
//显示点
public void DisplayVert(int vertexPosition)
{
Console.Write(vertiexes[vertexPosition].Data+" ");
}
 
/***拓扑排序:找到没有后继节点的节点,删除,加入一个栈,然后输出***/
/**
* 拓扑排序(TopSort)
拓扑排序是对一个有向的,并且不是环路的图中所有的顶点线性化。需要如下几个步骤
1.首先找到没有后继的节点。
2.将这个节点加入线性栈中
3.在图中删除这个节点
4.重复步骤1,2,3
* */
//1. 首先需要找到后继节点的方法:
//寻找图中没有后继节点的点
//具体表现为邻接矩阵中某一列全为0
//此时返回行号,如果找不到返回-1
public int FindNoSuccessor()
{
bool isEdge;
//循环行
for (int i = 0; i < numVerts; i++)
{
isEdge = false;
//循环列,有一个1就跳出循环
for (int j = 0; j < numVerts; j++ )
{
if (adjmatrix[i, j] == 1)
{
isEdge = true;
break;
}
}
if (!isEdge)
{
return i;
}
}
return -1;
}//end FindNoSuccessor()
//3. 删除图中的点
// 此外还需要删除图中点的方法,这个方法不仅需要删除图中对应位置的点,还需要删除邻接矩阵对应的行和列,因此设置了两个辅助方法,见代码。
// 需要两个操作,分别从数组中删除点
// 从邻接矩阵中消去被删点的行和列
public void DelVertex(int vert)
{
//保证不越界
if(vert <= numVerts -1)
{
//删除点
for (int i = vert; i < numVerts; i++)
{
vertiexes[i] = vertiexes[i + 1];
}
//删除邻接矩阵的行
for (int j = vert; j < numVerts; j++)
{
MoveRow(j, numVerts);
}
//删除邻接矩阵中的列,因为已经删了行,所以少一列
for (int k = vert; k < numVerts - 1; k++)
{
MoveCol(k,numVerts-1);
}
//删除后减少一个
numVerts--;
}
}//end DelVertex()
//辅助方法,移动邻接矩阵中的行
public void MoveRow(int row, int length)
{
for (int col = row; col < numVerts; col++)
{
adjmatrix[row, col] = adjmatrix[row+1, col];
}
}// end MoveCol()
//辅助方法,移动邻接矩阵中的列
public void MoveCol(int col, int length)
{
for (int row = col; row < numVerts; row++)
{
adjmatrix[row, col] = adjmatrix[row, col + 1];
}

}// end MoveCol()
//拓扑排序
//找到没有后继节点的节点,删除,加入一个栈,然后输出
public void TopSort()
{
int origVerts = numVerts;
//存放返回节点的栈
Stack result = new Stack();
while (numVerts > 0)
{
//找到第一个没有后继节点的节点
int currVertex = FindNoSuccessor();
if (currVertex == -1)
{
Console.WriteLine("the graph is a ring, can not do Topsort().");
return;
}
//如果找到,将其加入返回结果栈
result.Push(vertiexes [currVertex].Data);
//然后删除此节点
DelVertex(currVertex);
}
//输出排序后的结果
Console.Write("this is the Topsort():");
while (result.Count > 0)
{
Console.Write(result.Pop()+" ");
}

}//end TopSort()
//图的遍历
//很多时候,我们需要知道从图中给定点到另一个点是否能走通,比如几个车站之间是否可以连接。
//这时我们需要对图进行查找,查找大概可以分为两类,深度优先遍历和广度优先遍历
//1.深度优先遍历(Depth-First Search)
//深度优先遍历首先从一个点开始,到一条路径结束,然后循环找第二条路径,到结束,依此往复。
//首先我们需要一个辅助方法返回给定的点最近一个连接并且未被访问过的序号。
//从邻接矩阵查找给定点第一个相邻且未被访问过的点
//参数v是igeiding在邻接矩阵的行
public int GetAdjUnvisitedVertex(int v)
{
for (int j = 0; j < numVerts; j++)
{
if (adjmatrix[v, j] == 1 && vertiexes[j].IsVisited == false)
{
return j;
}
}
return -1;
}//end GetAdjUnivisitedVertex()
//深度优先遍历
public void DeptFirstSearch()
{
//声明一个存储临时结果的栈
Stack s = new Stack();
//先访问第一个节点
vertiexes[0].IsVisited = true;
DisplayVert(0);
s.Push(0);
int v;
while (s.Count > 0)
{
//获得和当前节点连接的未访问过节点的序号
v = GetAdjUnvisitedVertex((int)s.Peek());
if (v == -1)
{
s.Pop();
}
else
{
//标记为已经被访问过
vertiexes[v].IsVisited = true;
DisplayVert(v);
s.Push(v);
}
}
//重置所有节点为未访问过
for (int u = 0; u < numVerts; u++)
{
vertiexes[u].IsVisited = false;
}
}
//end 深度优先遍历
 
// 广度优先遍历(Breadth-First Search)
// 广度优先遍历首先遍历层级。算法如下:
public void BreadthFirstSearch()
{
System.Collections.Queue q = new Queue();
/*首先访问第一个节点*/
vertiexes[0].IsVisited = true;
DisplayVert(0);
q.Enqueue(0);
/*第一个节点访问结束*/
int vert1, vert2;
while (q.Count > 0)
{
/*首先访问同层级第一个节点*/
vert1 = (int)q.Dequeue();
vert2 = GetAdjUnvisitedVertex(vert1);
/*结束*/
while (vert2 != -1)
{
/*首先访问第二个节点*/
vertiexes[vert2].IsVisited = true;
DisplayVert(vert2);
q.Enqueue(vert2);
//寻找邻接的
vert2 = GetAdjUnvisitedVertex(vert1);
}
}
//重置所有节点为未访问过
for (int u = 0; u < numVerts; u++)
{
vertiexes[u].IsVisited = false;
}
 
} //end 广度优先遍历
 
//end 图的遍历
}
class Program
{
//代码实现
static void Main(string[] args)
{

////建立图,测试拓扑排序
//Graph g = new Graph();
////向图添加点
//g.AddVertex("A");
//g.AddVertex("B");
//g.AddVertex("C");
//g.AddVertex("D");
////向图添加边
//g.AddEdge(0,1);
//g.AddEdge(1, 2);
//g.AddEdge(2, 3);
//g.AddEdge(3, 4);

////对图进行拓扑排序
////g.TopSort();

////结果: this is the Topsort(): A B C D
 
//建立图,测试图的遍历广度优先,深度优先
Graph g = new Graph();
g.AddVertex("A");
g.AddVertex("B");
g.AddVertex("C");
g.AddVertex("D");
g.AddVertex("E");
g.AddVertex("F");
g.AddVertex("G");
g.AddEdge(0, 1);
g.AddEdge(0, 2);
g.AddEdge(1, 3);
g.AddEdge(2, 4);
g.AddEdge(3, 5);
g.AddEdge(4, 6);
Console.WriteLine("DeptFirstSearch:");
g.DeptFirstSearch();
///结果: DeptFirstSearch: A B D F C E G
Console.WriteLine();
Console.WriteLine("BreadthFirstSearch:");
g.BreadthFirstSearch();
///结果: DeptFirstSearch: A B C D E F G
Console.ReadLine();
 
}
}
}

参考:
http://www.cnblogs.com/CareySon/archive/2012/04/20/ImpleGraphWithCSharp.html

本文出自 “Ricky's Blog” 博客,请务必保留此出处http://57388.blog.51cto.com/47388/1658812

更多相关文章
一周排行
  • 一.DRBD简介 DRBD的全称为:Distributed ReplicatedBlock Device(DRBD)分布式块设备复制,DRBD是由内核模块和相关脚本而构成,用以构建高可用性的集群.其实现方式是通过网络 ...
  • 最近几天发现网通线路的服务器出现流量不稳定的情况,具体的表现是,流量时而高,时而低,在流量低的时候发现系统的负载很小,几乎为0,但是过一会,负载又高上去,流量也上去,很是奇怪,查找了2天没有找到原因,后来看到一边文章
  • Fastest Wordpress Theme wpfast Download
    Are you in search of fastest wordpress theme ...
  • var $ = document; // shortcut var cssId = 'myCss'; // you could encode the css path itself to generate id..
  • 


    		    TIP/IP 埠號大全
    1 tcpmux TCP 端口服务多路复用 5 rje 远程作业入口 7 echo Ech ...
  • 主要修改两个文件:image.js和upload_json.ashx文件. 一.修改image.js文件 打开kindeditor/plugins/image目录下的image.js文件,找到 '<input ...
  • 在使用UITextField来判断登陆按钮状态时只有 shouldChangeCharactersInRange函数,是在文件还没有改变前就调用了,而不是在改变后调用,要想实现改变后调用的功能,导致登陆按钮显示状态不
  • 今天看postfix日志,发现日志中报大量的NOQUEUE:reject:RCPTfromunknown[183.60.103.208]:5045.5.2,而且在不停的换IP,频率很高,一分钟能收到2000左右的连接
  • shell的命令可以分为内部命令和外部命令. 内部命令是由特殊的文件格式.def实现的,如cd,ls等.而外部命令是通过系统调用或独立程序实现的,如awk,sed. source和exec都是内部命令. fork 使 ...
  • 1:Ant的下载地址http://ant.apache.org/bindownload.cgi 2:下载tar.gz格式的 3:下载到/usr/local下面用命令 wget http://apache.etoak.