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

更多相关文章
一周排行
  • 在开发的时候经常遇到这样的问题,就是需要设置某个控件不可编辑,这个控件可能是一个input文本框,可能是一个select下拉列表 遇到这样的问题,一般有两种处理方法 第一种是将input 控件添加 disabled属
  •  Food Delivery Time Limit:2MS     Memory Limit:65536KB     64bit IO Format:%lld & %llu Description When ...
  • Windows Azure Storage (6) Windows Azure Storage之Table
    <Windows Azure Platform 系列文章目录>   最近想了想 ...
  • 当我们进行linux当中的源码编译时候遇到/usr/bin/ld:cannot find -lxxx类似于这种问题产生有多种原因 1 系统没有安装相对应的lib 2 相对应的lib版本不对 3 lib(.so档)的s ...
  • 一般icon以下几个: Icon.png – 57×57 iPhone (ios5/6) [email protected] – 114×114 iPhone Retina (ios5/6) Icon-72.png – 72×7 ...
  • AD的学习离不开对FMSO的五种角色,它们是AD的最基本也是最核心的概念.这是一个老生常谈的话题了,网上有很多很多的解释,这里只是在这个系列中重新提一下,让自己加深一下记忆. 在企业的环境只是单域单站点时,IT管理员 ...
  • http://www.luocs.com/archives/281.html SCAN概念 先介绍一下什么叫SCAN,SCAN(Single Client Access Name)是Oracle从11g R2开始推出
  • Cisco ASA防火墙上面配置Remote Vpn
  • 1 /* 2 一张有20个顶点的图上. 3 依次输入每个点与哪些点直接相连. 4 并且多次询问两点间,最短需要经过几条路才能从一点到达另一点. 5 6 bfs 水过 7 */ 8 #include<iostre ...
  • 百度是我开始找工作时最想去的企业.我的目标是北京互联网企业,职位是运维dba 或者研发.虽然自己的经验和背景主要是web开发,但是很希望做dba. 在工作除了准备程序设计,算法等,大概7月开始阅读<mysql技 ...