C#实现图（Graph）的算法

C#实现图（Graph）的算法2013-11-13简介

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

PS:本片文章是我复习的笔记，代码注释很全。勿吐槽。

表示点的对象

下面实现代码:

class Vertex{publicstring Data;publicbool IsVisited;public Vertex（string Vertexdata）{Data = Vertexdata;}}

每个节点包含两个字段，分别为节点数据以及表示是否被访问过的一个布尔类型。

表示图的对象

图中除了需要点的集合和邻接矩阵之外，还需要一些基本的向图中添加或删除元素的方法，以及一个构造方法来对图进行初始化。

publicclass Graph{//图中所能包含的点上限privateconstint Number = 10;//顶点数组private Vertex[] vertiexes;//邻接矩阵publicint[,] adjmatrix;//统计当前图中有几个点int numVerts = 0;//初始化图public Graph（）{//初始化邻接矩阵和顶点数组adjmatrix = new Int32[Number, Number];vertiexes = new Vertex[Number];//将代表邻接矩阵的表全初始化为0for （int i = 0; i < Number; i++）{for （int j = 0; j < Number; j++）{adjmatrix[i, j] = 0;}}} //向图中添加节点publicvoid AddVertex（String v）{vertiexes[numVerts] = new Vertex（v）;numVerts++;}//向图中添加有向边publicvoid AddEdge（int vertex1, int vertex2）{adjmatrix[vertex1, vertex2] = 1;//adjmatrix[vertex2, vertex1] = 1;}//显示点publicvoid DisplayVert（int vertexPosition）{Console.WriteLine（vertiexes[vertexPosition]+""）;}}

拓扑排序（TopSort）

拓扑排序是对一个有向的，并且不是环路的图中所有的顶点线性化。需要如下几个步骤

1.首先找到没有后继的节点。

2.将这个节点加入线性栈中

3.在图中删除这个节点

4.重复步骤1，2，3

因此，首先需要找到后继节点的方法：

//寻找图中没有后继节点的点//具体表现为邻接矩阵中某一列全为0//此时返回行号，如果找不到返回-1privateint 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; }