首页 > > 程序设计 > C/C++ >

图的遍历---广度优先遍历和深度优先遍历

2018-06-17 20:35:05来源：未知阅读 ()

图的遍历：从图的任意一个顶点出发，按照某一种次序，对图中的所有顶点访问一次并且只能访问一次。遍历经常

用两种方法：广度优先遍历和深度优先遍历。

广度优先遍历：类似于树的按层次遍历的过程。假设从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问

过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的

顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访问，则另选图

中的一个未曾被访问的顶点作为起始点，重复上述过程，直至图中所有顶点都被访问到为止。

深度优先遍历：类似于树的先根遍历，是树的先根遍历的推广。假设初始状态是图中所有顶点未曾被访问，则深度

优先遍历可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有

和v有路径想通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为起始点，重复

上述过程，直至图中所有顶点都被访问到为止。

下面用代码来实现两种遍历方法：

#include <iostream>
#include <queue>
using namespace std;

#define SIZE 10
struct Edge
{
    Edge(int v):destvalue(v),link(NULL){}
    int destvalue;
    Edge *link;
};
struct Vertex
{
    Vertex():list(NULL){}
    char data;
    Edge *list;
};
class GraphLink
{
public:
    GraphLink()
    {
        MaxVertex = SIZE;
        NumVertex = NumEdge = 0;
        VertexTable = new Vertex[MaxVertex];
    }
    void InsertVertex(char v)
    {
        if(NumVertex >= MaxVertex)
            return;
        VertexTable[NumVertex++].data = v;
    }
    int GetVertexI(char v)
    {
        for(int i = 0;i<NumVertex;i++)
        {
            if(VertexTable[i].data == v)
                return i;
        }
        return -1;
    }
    void InsertEdge(char v1,char v2)
    {
        int p1 = GetVertexI(v1);
        int p2 = GetVertexI(v2);
        if(p1 == -1 || p2 == -1)
            return;
        Edge *ed = new Edge(p2);
        ed->link = VertexTable[p1].list;
        VertexTable[p1].list = ed;
        
        ed = new Edge(p1);
        ed->link = VertexTable[p2].list;
        VertexTable[p2].list = ed;
        NumEdge++;
    }
    void Show()
    {
        Edge *ed = NULL;
        for(int i = 0;i<NumVertex;i++)
        {
            cout<<i<<":"<<VertexTable[i].data<<"->";
            ed = VertexTable[i].list;
            while(ed)
            {
                cout<<ed->destvalue<<"->";
                ed = ed->link;
            }
            cout<<"nul"<<endl;
        }
    }
    void BFS(char value)
    {
        queue<int> q;
        int v = GetVertexI(value);
        bool *visited = new bool[NumVertex];
        Edge *ed = NULL;
        int w;
        for(int i = 0;i<NumVertex;i++)
            visited[i] = false;
        if(v == -1)
            return;
        cout<<value<<" ";
        visited[v] = true;
        q.push(v);
        while(!q.empty())
        {
            v = q.front();
            q.pop();
            ed = VertexTable[v].list;
            while(ed)
            {
                w = ed->destvalue;
                if(!visited[w])
                {
                    cout<<VertexTable[w].data<<" ";
                    q.push(w);
                    visited[w] = true;
                }
                ed = ed->link;
            }
        }
    }
    void DFS(char v)
    {
        bool *visited = new bool[NumVertex];
        for(int i = 0;i<NumVertex;i++)
            visited[i] = false;
        DFS(GetVertexI(v),visited);
        delete [] visited;
        visited = NULL;
    }
    char GetVertex(int v)
    {
        return VertexTable[v].data;
    }
    void DFS(int v,bool *visited)
    {
        cout<<GetVertex(v)<<" ";
        visited[v] = true;
        int w = GetFirstNeighbor(v);
        while(w != -1)
        {
            if(!visited[w])
            {
                DFS(w,visited);
            }
            w = GetNextNeighbor(v,w);
        }
    }
    int GetFirstNeighbor(int v)         //v的第一个邻接顶点
    {
        if(v == -1)
            return -1;
        Edge *p = VertexTable[v].list;
        if(p)
            return p->destvalue;
        return -1;
    }
    int GetNextNeighbor(int v,int w)    //v的邻接顶点w的下一个邻接顶点
    {
        if(v == -1 || w== -1)
            return -1;
        Edge *p = VertexTable[v].list;
        while(p && p->destvalue != w)
            p = p->link;
        if(p && p->link)
            return p->link->destvalue;
        return -1;
    }
private:
    int MaxVertex;
    int NumVertex;
    int NumEdge;
    Vertex *VertexTable;
};