数据结构（图的遍历）

Myth丶恋晨 2022-06-05 04:26 199阅读 0赞

图的遍历指的是从图中的某个顶点出发，按照某种顺序访问每个顶点，使得每个顶点被访问且仅访问一次。  
对于之前的邻接矩阵表示的图，加以更改，添加相应功能。

private int[] visited;//表示某个顶点是否被访问
            public VexNode<T> this[int index] { get { return adjList[index]; }set { adjList[index] = value; } }
    
            public GraphAdjList(Node<T> []nodes )
            {
                adjList=new VexNode<T>[nodes.Length];
                for (int i = 0; i < adjList.Length; i++)
                {
                    adjList[i].Data = nodes[i];
                    adjList[i].FirstAdj = null;
                }
                //初始化被访问的顶点为未被访问的状态
                visited=new int[nodes.Length];
                for (int i = 0; i < visited.Length; i++)
                {
                    visited[i] = 0;
                }
            }

**深度优先遍历**  
类似于树的先序遍历，假设初始状态是图中所有顶点未曾被访问过，则深度优先遍历可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接顶点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被遍历过。若此时图中尚有未被访问的顶点，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问到为止。

public void DFS()
            {
                for (int i = 0; i < visited.Length; i++)
                {
                    if (visited[i]==0)
                    {
                        DFSAL(i);
                    }
                }
            }
    
            public void DFSAL(int i)
            {
                visited[i] = 1;
                AdjListNode<T> p = adjList[i].FirstAdj;
                while (p!=null)
                {
                    if (visited[p.Adjvex]==0)
                    {
                        DFSAL(p.Adjvex);
                    }
                    p = p.Next;
                }
            }

**广度优先遍历**  
类似于树的层序遍历，假设从图中的某个顶点v出发，访问了v之后，依次访问v的各个未曾访问的邻接顶点。然后分别从这些邻接顶点出发依次访问它们的邻接顶点，并使“先被访问的顶点的邻接顶点”先于“后被访问的顶点的邻接顶点”被访问，直至图中所有已被访问的顶点的邻接顶点都被访问。若此时图中尚有顶点未被访问，则另选图中未被访问的顶点作为起点，重复上述过程，直到图中所有的顶点都被访问为止。

public void BFS()
            {
                for (int i = 0; i < visited.Length; i++)
                {
                    BFSAL(i);
                }
            }
    
            public void BFSAL(int i)
            {
                visited[i] = 1;
                Queue<int> cq=new Queue<int>(visited.Length);
                cq.Enqueue(i);
                while (cq.Count!=0)
                {
                    int k = cq.Dequeue();
                    AdjListNode<T> p = adjList[k].FirstAdj;
                    while (p!=null)
                    {
                        if (visited[p.Adjvex]==0)
                        {
                            cq.Enqueue(p.Adjvex);
                            visited[p.Adjvex] = 1;
                        }
                        p = p.Next;
                    }
                }
            }