1.调用代码入口：
using System;
namespace 图_图的遍历
{
internal class Program
{
private static void Main(string[] args)
{
var a = new AdjacencyList<char>();
Console.WriteLine("1.初始化树结构：");
Console.WriteLine("=================================");
//添加顶点；
a.AddVertex('A');
a.AddVertex('B');
a.AddVertex('C');
a.AddVertex('D');
a.AddVertex('E');
a.AddVertex('F');
a.AddVertex('G');
a.AddVertex('H');
//添加边；
a.AddEdge('A', 'B');
a.AddEdge('A', 'C');
a.AddEdge('B', 'D');
a.AddEdge('B', 'E');
a.AddEdge('C', 'F');
a.AddEdge('C', 'G');
a.AddEdge('D', 'H');
a.AddEdge('E', 'H');
a.AddEdge('F', 'H');
a.AddEdge('G', 'H');
Console.WriteLine("=================================");
Console.WriteLine("2.树的深度优先遍历：");
new DepthFirstTraversal<char>(a.Items).Process();
Console.WriteLine("=================================");
Console.WriteLine("3.树的广度优先遍历：");
new BreadthFirstTraversal<char>(a.Items).Process();
Console.Read();
}
}
}
2.图-图节点类：
namespace 图_图的遍历
{
/// <summary>
/// 链表中的节点
/// </summary>
public class Node<T>
{
/// <summary>
/// 邻接点域
/// </summary>
public Vertex<T> Adjvex;
/// <summary>
/// 下一个邻接点指针域
/// </summary>
public Node<T> Next;
/// <summary>
/// 链表中的节点
/// </summary>
/// <param name="value"></param>
public Node(Vertex<T> value)
{
Adjvex = value;
}
}
}
3.图-图表头节点类：
using System;
namespace 图_图的遍历
{
/// <summary>
/// 链表中的表头节点
/// </summary>
/// <typeparam name="T"></typeparam>
public class Vertex<T>
{
/// <summary>
/// 数据
/// </summary>
public T Data;
/// <summary>
/// 邻接表表头指针
/// </summary>
public Node<T> FirstEdge;
/// <summary>
/// 访问标志，遍历时使用
/// </summary>
public Boolean Visited;
/// <summary>
/// 表头节点
/// </summary>
/// <param name="value"></param>
public Vertex(T value) //构造方法；
{
Data = value;
}
}
}
4.深度优先遍历：
using System;
using System.Collections.Generic;
namespace 图_图的遍历
{
/// <summary>
/// 深度优先遍历
/// </summary>
/// <typeparam name="T"></typeparam>
public class DepthFirstTraversal<T>
{
private readonly List<Vertex<T>> _items; //图的顶点集合；
/// <summary>
/// 深度优先遍历
/// </summary>
/// <param name="items"></param>
public DepthFirstTraversal(List<Vertex<T>> items)
{
_items = items;
}
/// <summary>
/// 遍历树
/// </summary>
public void Process()
{
InitVisted();
DepthFirst(_items[0]);
Console.WriteLine("");
}
/// <summary>
/// 初始化节点访问状态
/// </summary>
private void InitVisted()
{
foreach (var vertex in _items)
{
vertex.Visited = false;
}
}
/// <summary>
/// 使用递归进行深度优先遍历
/// </summary>
/// <param name="vertex"></param>
private void DepthFirst(Vertex<T> vertex)
{
vertex.Visited = true;
Console.Write(vertex.Data + " ");
Node<T> node = vertex.FirstEdge;
while (node != null)
{
if (!node.Adjvex.Visited)
{
DepthFirst(node.Adjvex); //递归访问节点；
}
node = node.Next;
}
}
}
}
5.广度优先遍历：
using System;
using System.Collections.Generic;
namespace 图_图的遍历
{
/// <summary>
/// 广度优先遍历
/// </summary>
public class BreadthFirstTraversal<T>
{
private readonly List<Vertex<T>> _items; //图的顶点集合；
public BreadthFirstTraversal(List<Vertex<T>> items)
{
_items = items;
}
/// <summary>
/// 广度优先遍历
/// </summary>
public void Process()
{
InitVisted();
BFS(_items[0]);
Console.WriteLine("");
}
/// <summary>
/// 初始化节点访问状态
/// </summary>
private void InitVisted()
{
foreach (var vertex in _items)
{
vertex.Visited = false;
}
}
/// <summary>
/// 使用队列进行广度优先遍历
/// </summary>
/// <param name="vertex"></param>
private void BFS(Vertex<T> vertex)
{
var queue = new Queue<Vertex<T>>(); //创建一个队列；
Console.Write(vertex.Data + " "); //访问节点；
vertex.Visited = true;
queue.Enqueue(vertex); //进队；
while (queue.Count > 0) //只要队列不为空，就循环；相当于：一层一层的进行访问；
{
Vertex<T> w = queue.Dequeue();
Node<T> node = w.FirstEdge;
while (node != null)
{
if (!node.Adjvex.Visited)
{
Console.Write(node.Adjvex.Data + " ");
node.Adjvex.Visited = true;
queue.Enqueue(node.Adjvex);
}
node = node.Next;
}
}
}
}
}
执行结果：
