C#实现图的深度优先遍历--非递归代码
本文介绍C#实现图的深度优先遍历–非递归代码
1、程序如下所示
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace 图的应用__深度优先搜索算法
{
using VertexType = System.Char;//顶点数据类型别名声明
using EdgeType = System.Int16;//带权图中边上权值的数据类型别名声明
class Program
{
public const int MAxVertexNum = 100;//顶点数目的最大值
public const int MAXSize = 100;
static void Main(string[] args)
{
MGraph G = new MGraph();
int u;
int[] d = new int[MAxVertexNum];
G.vexnum = 8;
G.arcnum = 8;
G.vex = new VertexType[MAxVertexNum];
G.Edge = new EdgeType[MAxVertexNum, MAxVertexNum];
for (int i = 0; i < MAxVertexNum; ++i)
{
for (int j = 0; j < MAxVertexNum; ++j)
{
G.Edge[i, j] = 0;
}
}
//图的赋值
G.vex[0] = ‘a’; G.vex[1] = ‘b’; G.vex[2] = ‘c’; G.vex[3] = ‘d’; G.vex[4] = ‘e’; G.vex[5] = ‘f’;
G.vex[6] = ‘g’; G.vex[7] = ‘h’;
G.Edge[0, 1] = 1; G.Edge[0, 2] = 1;
G.Edge[1, 0] = 1; G.Edge[1, 3] = 1; G.Edge[1, 4] = 1;
G.Edge[2, 0] = 1; G.Edge[2, 5] = 1; G.Edge[2, 6] = 1;
G.Edge[3, 1] = 1;
G.Edge[4, 1] = 1; G.Edge[4, 7] = 1;
G.Edge[5, 2] = 1;
G.Edge[6, 2] = 1;
G.Edge[7, 4] = 1;
Console.WriteLine(“递归深度优先:”);
DFS_Traverse(G);
Console.ReadLine();
}
/// <summary>
/// 图的定义--邻接矩阵
/// </summary>
public struct MGraph
{
public VertexType[] vex;//顶点表数组
public EdgeType[,] Edge;//临接矩阵、边表
public int vexnum, arcnum;//图的当前顶点数和弧数
}
/// <summary>
/// 图的定义--邻接表法
/// </summary>
public class ArcNode
{//边表节点
public int adjvex;
public ArcNode next;
}
public class VNode
{ //顶点表节点
VertexType data;//顶点信息
ArcNode first;//只想第一条依附改顶点的弧的指针
}
public class ALGraph
{
VNode[] vertices; //邻接表
int vexnum, arcnum;//图的顶点数和弧数
}
/// <summary>
/// 深度优先搜索的递归实现
/// </summary>
/// <param name="G"></param>
/// <param name="v"></param>
/// <returns></returns>
static void DFS_Traverse(MGraph G) {
bool[] visited = new bool[MAxVertexNum];
for (int i=0;i<G.vexnum;++i) {
visited[i] = false; }
for (int v=0;v<G.vexnum;++v) {
if (!visited[v]) {
DFS2(G,v,ref visited);
}
}
}
/// <summary>
/// 递归实现
/// </summary>
/// <param name="G"></param>
/// <param name="v"></param>
static void DFS(MGraph G,int v, ref bool[] visited) {
visit(G,v);
visited[v] = true;
for (int w=FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w)) {
if (!visited[w]) {
DFS(G, w, ref visited);
}
}
}
/// <summary>
/// 非递归实现
/// </summary>
/// <param name="G"></param>
/// <param name="v"></param>
static void DFS2(MGraph G, int v, ref bool[] visited) {
SqStack S = new SqStack();
S.data = new int[MAxVertexNum];
Push(ref S,v);//入栈
while (!StackEmpty(S)) {
PoP(ref S, ref v);
if (!visited[v]) { visit(G, v); }
visited[v] = true;
for (int w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)) {
if (!visited[w]) {
Push(ref S, w);
}
}
}
}
//控制台打印遍历点
static void visit(MGraph G, int v)
{
Console.Write(G.vex[v] + " ");
}
//查找G中,V顶点的首个邻接点
static int FirstNeighbor(MGraph G, int v)
{
int b = -1;
for (int i = 0; i < G.vexnum; ++i)
{
if (G.Edge[v, i] == 1)
{
b = i;
break;
};
}
return b;//返回首个邻接点
}
//查找G中,V顶点的W邻节点后的下一个邻接点
static int NextNeighbor(MGraph G, int v, int w)
{
int b = -1;
for (int i = w + 1; i < G.vexnum; ++i)
{
if (G.Edge[v, i] == 1)
{
b = i;
break;
};
}
return b;//返回下一个邻接点
}
/// <summary>
/// 栈定义
/// </summary>
public struct SqStack
{
public int[] data;
public int top;//栈顶
}
/// <summary>
/// 判断栈是否为空
/// </summary>
/// <param name=""></param>
/// <returns></returns>
static bool StackEmpty(SqStack S)
{
if (S.top == -1)
{
return true;
}
else
{
return false;
}
}
/// <summary>
/// 栈初始化
/// </summary>
/// <param name="S"></param>
static void InitStack(ref SqStack S)
{
S.top = -1;
}
/// <summary>
/// 压栈
/// </summary>
/// <param name="S"></param>
/// <returns></returns>
static bool Push(ref SqStack S, int e)
{
if (S.top >= MAxVertexNum - 1)
{
return false;
}
S.top = S.top + 1;
S.data[S.top] = e;//先加1,再进栈
return true;
}
/// <summary>
/// 出栈
/// </summary>
/// <param name="S"></param>
/// <param name="e"></param>
/// <returns></returns>
static bool PoP(ref SqStack S, ref int e)
{
if (S.top == -1) { return false; }
e = S.data[S.top--];//出栈
return true;
}
/// <summary>
///
///读取栈顶元素
/// </summary>
/// <param name="S"></param>
/// <param name="e"></param>
/// <returns></returns>
bool GetTop(ref SqStack S, ref int e)
{
if (S.top == -1) { return false; }
e = S.data[S.top];//读取元素
return true;
}
}
}
2、测试如下:
相关文章
- C# JToken类的使用,实现解析动态json数据、遍历、查找
- 请求大神,C#如何截取字符串中指定字符之间的部分 按指定字符串分割 一分为二 c# 去除字符串中的某个已知字符
- C#学习记录——基本图形绘制
- C# Window Service安装、卸载、恢复选项操作
- C# mongodb中内嵌文档数组条件查询
- C#【必备技能篇】DatagridView添加行时,设置行标题单元格的值为行数
- C#,楔子数(Sphenic Number)的暴力算法与高效算法源代码
- C# 中的Async 和 Await 的用法详解
- 《Visual C# 2010入门经典》一1.6 问与答
- c# 比较字符串
- C#遍历List并删除某个或者几个元素的方法
- C# DataSet的基本用法
- C#中遍历各类数据集合的方法总结
- C# IO操作,写入文本到txt文件.
- 《C#零基础入门之百识百例》(八十七)系统类HasTable哈希表解析 -- 几种遍历方式
- C#使用Autofac实现控制反转IoC和面向切面编程AOP