图的遍历.cpp

图的遍历算法cpp程序

// 图的遍历


#include <iostream>
#include <queue>

using namespace std;

class Graph
{
public:
    Graph();
    ~Graph();
    void DFSTraverse();
    void BFSTraverse();    

private:
    // 图的邻接表存储表示 
    struct ArcNode
    {
        int adjVexPos;  // 该弧（边）所指向的顶点位置
        ArcNode* nextArc;  // 指向下一条弧（边）的指针 
        ArcNode(int pos = -1, ArcNode* nt = 0);
    };
    struct VertexNode
    {
        int data;           // 顶点信息 
        ArcNode* firstArc;  // 指向第一条依附该顶点的弧（边）的指针 
        VertexNode();
    };
    VertexNode adjList[8];
    int vertexNum, arcNum;  // 图的顶点数和弧（边）数
    bool visited[8];
    
    void DFS(int v);
}; 

inline Graph::ArcNode::ArcNode(int pos, ArcNode* nt)
{
    adjVexPos = pos;
    nextArc = nt;
}

inline Graph::VertexNode::VertexNode()
{
    data = -1;
    firstArc = 0;
}

Graph::Graph()
{
    vertexNum = 8;
    arcNum = 9;
    
    // 图的邻接矩阵表 
    int adjMatrix[8][8] = { {0, 1, 1, 0, 0, 0, 0, 0},
                            {1, 0, 0, 1, 1, 0, 0, 0},
                            {1, 0, 0, 0, 0, 1, 1, 0},
                            {0, 1, 0, 0, 0, 0, 0, 1},
                            {0, 1, 0, 0, 0, 0, 0, 1},
                            {0, 0, 1, 0, 0, 0, 1, 0},
                            {0, 0, 1, 0, 0, 1, 0, 0},
                            {0, 0, 0, 1, 1, 0, 0, 0} };
        
    cout << "该图的邻接矩阵为: \n";
    for(int i = 0; i < vertexNum; ++i)
    {
        for(int j = 0; j < vertexNum; ++j)
            cout << adjMatrix[i][j] << '\t';
        cout << endl;
    }
    
    // 通过邻接矩阵构造邻接表
    for(int i = vertexNum-1; i >= 0; --i)
    {
        adjList[i].data = i + 1;
        for(int j = vertexNum-1; j >= 0; --j)
        {
            if(adjMatrix[i][j])
            {
                ArcNode* temp = new ArcNode(j, adjList[i].firstArc);
                adjList[i].firstArc = temp;
            }
        }
    } 
}

Graph::~Graph()
{
    // 将 adjList 中申请的节点释放 
    for(int i = 0; i < vertexNum; ++i)
    {
        ArcNode* temp = adjList[i].firstArc;
        while(temp)
        {
            adjList[i].firstArc = temp->nextArc;
            delete temp;
            temp = adjList[i].firstArc;
        }
    }
}

// 深度优先遍历 
void Graph::DFSTraverse()
{
    // vertexNum = 8;
    for(int i = 0; i < vertexNum; ++i)
        visited[i] = false;
    
    cout << "深度优先遍历：\n";
    for(int v = 0; v < vertexNum; ++v)
        if( !visited[v] )  // 对尚未访问的顶点调用 DFS 
            DFS(v);
            
    cout << endl;
}

// 从第 v 个顶点出发递归地深度优先遍历
void Graph::DFS(int v)
{
    visited[v] = true;
    cout << adjList[v].data << '\t';
    ArcNode* temp = adjList[v].firstArc;
    while(temp)
    {
        int pos = temp->adjVexPos;
        if(!visited[pos])
            DFS(pos);
        temp = temp->nextArc;
    }
}

// 广度优先非递归遍历图 
void Graph::BFSTraverse()
{
    for(int i = 0; i < vertexNum; ++i)
        visited[i] = false;
        
    queue<VertexNode> vnQueue;
    
    cout << "广度优先非递归遍历图\n";
    for(int v = 0; v < vertexNum; ++v)
    {
        if( !visited[v] )
        {
            visited[v] = true;
            cout << adjList[v].data << '\t';
            vnQueue.push(adjList[v]);
            while(!vnQueue.empty())
            {
                VertexNode vntemp = vnQueue.front();
                vnQueue.pop();
                ArcNode* temp = vntemp.firstArc;
                while(temp)
                {
                    int pos = temp->adjVexPos;
                    if(!visited[pos])
                    {
                        visited[pos] = true;
                        cout << adjList[pos].data << '\t';
                        vnQueue.push(adjList[pos]);
                    }
                    temp = temp->nextArc;
                }
            }
        }
    }
    cout << endl;
}

int main()
{
    Graph g;
    g.DFSTraverse();
    g.BFSTraverse();
    system("pause");
    return 0;
}