using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace AdjacencyList{    public class AdjacencyList
     
          {        List
      
       
        > items;//图的顶点集合        public AdjacencyList():this(10){}//构造方法        public AdjacencyList(int capacity)//按指定的容量进行构造        {            items = new List
        
         
          >(capacity);        }        public void AddVertex(T item)//添加一个节点        {            if (Contains(item))            {                throw new ArgumentException("插入了重复节点！");            }            items.Add(new Vertex
          
           (item)); } public void AddEdge(T from,T to)//添加无向边 { Vertex
           
             fromVer = Find(from);//找到起始节点 if (fromVer == null) { throw new ArgumentException("头节点并不存在！"); } Vertex
            
              toVer = Find(to);//找到结束节点 if (toVer == null) { throw new ArgumentException("尾节点并不存在！"); } //无向边两个节点都需记录的边的信息 AddDirectedEdge(fromVer,toVer); AddDirectedEdge(toVer,fromVer); } public bool Contains(T item)//查图中是否包含某项 { foreach (Vertex
             
               v in items) { if (v.data.Equals(item)) { return true; } } return false; } private Vertex
              
                Find(T item)//查找指定项并返回 { foreach (Vertex
               
                 v in items) { if (v.data.Equals(item)) { return v; } } return null; } //添加有向边 private void AddDirectedEdge(Vertex
                
                  fromVer,Vertex
                 
                   toVer) { if (fromVer.firstEdge == null)//无邻接点的时候 { fromVer.firstEdge = new Node(toVer); } else { Node tmp, node = fromVer.firstEdge; do { //检查是否添加了重复边 if(node.adjvex.data.Equals(toVer.data)) { throw new ArgumentException("添加了重复的边！"); } tmp=node; node=node.next; }while(node!=null); tmp.next = new Node(toVer);//添加到链表末尾。 } } public override string ToString()//仅用于测试 { //打印每个顶点和它的邻接点 string s = string.Empty; foreach (Vertex
                  
                    v in items) { s += v.data.ToString() + ":"; if (v.firstEdge != null) { Node tmp = v.firstEdge; while (tmp != null) { s += tmp.adjvex.data.ToString(); tmp = tmp.next; } } s += "\r\n"; } return s; } public void DFSTraverse()//深度优先搜索 { InitVisited();//将visited标志全部置为false DFS(items[0]);//从第一个顶点开始遍历 } private void DFS(Vertex
                   
                     v)//使用递归进行深度优先遍历 { v.visited = true;//将访问标志设为true Console.WriteLine(v.data+" ");//访问 Node node = v.firstEdge; while(node!=null)//访问此顶点的所有邻节点 { //如果邻节点未被访问，则递归访问它的边 if (!node.adjvex.visited) { DFS(node.adjvex);//递归 } node = node.next;//访问下一个节点 } } private void InitVisited()//初始化visited标志 { foreach (Vertex
                    
                      v in items) { v.visited = false;//全部设为false } } //广度优先搜索遍历 public void BFSTraverse() { InitVisited();// BFS(items[0]);//从第一个顶点开始遍历 } private void BFS(Vertex
                     
                       v)//使用队列进行广度优先搜索 { //创建一个队列 Queue
                      
                       
                        > queue = new Queue
                        
                         
                          >(); Console.WriteLine(v.data+" "); v.visited = true; queue.Enqueue(v); while(queue.Count>0) { Vertex
                          
                            w = queue.Dequeue(); Node node = w.firstEdge; while (node != null) { if (!node.adjvex.visited) { Console.WriteLine(node.adjvex.data+" ");//访问 node.adjvex.visited = true;//设置访问标志 queue.Enqueue(node.adjvex);//进队 } node = node.next;//访问下一个邻节点 } } } //非连通图的遍历 public void DFSTraverse2()//非连通图深度优先遍历 { InitVisited(); foreach (Vertex
                           
                             v in items) { if (!v.visited) { DFS(v); } } } public void BFSTraverse2()//非连通图广度优先遍历 { InitVisited(); foreach (Vertex
                            
                              v in items) { if (!v.visited) { BFS(v); } } } //嵌套类表示链表中的表节点 public class Node { public Vertex
                             
                               adjvex;//邻接点域 public Node next;//下一个邻接点指针域 public Node(Vertex
                              
                                value) { adjvex = value; } } //嵌套类表示存放数组中的表头节点 public class Vertex
                               
                                 { public TValue data;//数据 public Node firstEdge;//邻接链表头指针 public Boolean visited;//访问标志用于遍历 public Vertex(TValue value) { data = value; } } }}