如何做出图的构造及遍历

超、凢脫俗 2023-09-30 15:26 8阅读 0赞

刚入门小萌新，代码简单请不要介意，仅供参考

#include <queue>
    #include <stack>
    #include <iostream>
    using namespace std;
    
    enum GraphType
    {
        UNDIR_UNWEIGHT_GRAPH,        //无向无权图
        UNDIR_WEIGHT_GRAPH,            //无向带权图
        DIR_UNWEIGHT_GRAPH,            //有向无权图
        DIR_WEIGHT_GRAPH            //有向带权图
    };
    
    //结点颜色代表遍历情况
    enum ColorType
    {
        WHITE,    //未访问
        GRAY,    //正在访问，邻接点还没访问完
        BLACK    //访问完毕
    };
    
    template<typename VertexType,typename InfoType>
    class Graph
    {
    public:
        Graph(int vertexNum, GraphType type) :m_vertexNum(vertexNum), m_type(type), m_arcNum(0)
        {
            for (int i = 0; i < MAX_VERTEX_NUM; ++i)
            {
                m_vertices[i].firstArc = nullptr;
            }
        }
    
        void Create()
        {
            switch (m_type)
            {
            case UNDIR_UNWEIGHT_GRAPH:
                CreateUndirUnweightGraph();
                break;
            case UNDIR_WEIGHT_GRAPH:
                CreateUndirWeightGraph();
                break;
            case DIR_UNWEIGHT_GRAPH:
                CreateDirUnweightGraph();
                break;
            case DIR_WEIGHT_GRAPH:
                CreateDirWeightGraph();
                break;
            default:
                break;
            }
        }
    
        //输出图的信息
        void Display()
        {
            for (int i = 0; i < m_vertexNum; ++i)
            {
                cout << "第" << i + 1 << "个结点为" << m_vertices[i].data << " 邻接表为：";
                ArcNode* node = m_vertices[i].firstArc;
                while (node)
                {
                    cout << "->" << m_vertices[node->vertexIndex].data << "(" << node->info << ")";
                    node = node->next;
                }
                cout << endl;
            }
        }
    
        void BFS()
        {
            for (int i = 0; i < m_vertexNum; ++i)
            {
                m_vertices[i].color = WHITE;
            }
            cout << "图的广度优先遍历为：";
            BFS(&m_vertices[0]);
            cout << endl;
        }
    
        void DFS()
        {
            for (int i = 0; i < m_vertexNum; ++i)
            {
                m_vertices[i].color = WHITE;
            }
            cout << "图的深度优先遍历为：";
            DFS(&m_vertices[0]);
            cout << endl;
        }
    private:
        struct ArcNode
        {
            int vertexIndex;        //该弧指向的顶点位置
            struct ArcNode* next;    //指向下一个弧
            InfoType info;            //该弧的相关信息，如权重等
        };
    
        struct Vertex
        {
            VertexType data;    //顶点信息
            ArcNode* firstArc;    //指向第一条依附该节点弧的指针
            ColorType color;    //访问情况
        };
    
        //最大顶点数
        static const int MAX_VERTEX_NUM = 20;
        Vertex m_vertices[MAX_VERTEX_NUM];    //顶点列表
        int m_vertexNum;    //当前顶点数量
        int m_arcNum;        //当前弧数量
        GraphType m_type;    //图类型：有向无权图、有向带权图、无向无权图、无向无权图
    private:
        //初始化顶点列表
        void InitVertices()
        {
            cout << "请输入每个顶点的关键字" << endl;
            VertexType data;
            for (int i = 0; i < m_vertexNum; ++i)
            {
                cin >> data;
                m_vertices[i].data = data;
            }
        }
        //插入一个表结点
        void Insert(int headVertex, int tailVertex, InfoType info)
        {
            //构造一个邻接表结点，即创建一条弧
            ArcNode* newNode = new ArcNode;
            newNode->info = info;
            newNode->next = nullptr;
            newNode->vertexIndex = tailVertex;
    
            //找到邻接表的最后一个节点
            ArcNode* lastNode = m_vertices[headVertex].firstArc;
            if (lastNode == nullptr)
                m_vertices[headVertex].firstArc = newNode;
            else
            {
                while (lastNode->next)
                {
                    lastNode = lastNode->next;
                }
                lastNode->next = newNode;
            }
            ++m_arcNum;
        }
    
        //创建无向无权图
        void CreateUndirUnweightGraph()
        {
            InitVertices();
            cout << "请分别输入每条边的起始结点:" << endl;
            int head, tail;
            while (cin >> head >> tail)
            {
                //无向图head->tail tail->head插入两次
                Insert(head, tail, 0);
                Insert(tail, head, 0);
            }
        }
        //创建无向有权图
        void CreateUndirWeightGraph()
        {
            InitVertices();
            cout << "请分别输入每条边的起始结点和权值:" << endl;
            int head, tail;
            InfoType weight;
            while (cin >> head >> tail >> weight)
            {
                Insert(head, tail, weight);
                Insert(tail, head, weight);
            }
        }
        //创建有向无权图
        void CreateDirUnweightGraph()
        {
            InitVertices();
            cout << "请分别输入每条边的起始结点值:" << endl;
            int head, tail;
            while (cin >> head >> tail)
            {
                Insert(head, tail,0);
            }
        }
        //创建有向带权图
        void CreateDirWeightGraph()
        {
            InitVertices();
            cout << "请分别输入每条边的起始结点和权值:" << endl;
            int head, tail;
            InfoType weight;
            while (cin >> head >> tail >> weight)
            {
                Insert(head, tail, weight);
            }
        }
    
        void BFS(Vertex* vertex)
        {
            vertex->color = GRAY;
            queue<Vertex*> vertices;
            vertices.push(vertex);
            while (!vertices.empty())
            {
                Vertex* curVertex = vertices.front();
                vertices.pop();
                cout << curVertex->data << "->";
                ArcNode* node = curVertex->firstArc;
                while (node)
                {
                    Vertex* tmpVertex = &m_vertices[node->vertexIndex];
                    if (tmpVertex->color == WHITE)
                    {
                        tmpVertex->color = GRAY;
                        vertices.push(tmpVertex);
                    }
                    node = node->next;
                }
                curVertex->color = BLACK;
            }
        }
    
        void DFS(Vertex* vertex)
        {
            vertex->color = GRAY;
            stack<Vertex*> vertices;
            vertices.push(vertex);
            while (!vertices.empty())
            {
                Vertex* curVertex = vertices.top();
                vertices.pop();
                cout << curVertex->data << "->";
                ArcNode* node = curVertex->firstArc;
                while (node)
                {
                    Vertex* tmp = &m_vertices[node->vertexIndex];
                    if (tmp->color == WHITE)
                    {
                        tmp->color = GRAY;
                        vertices.push(tmp);
                    }
                    node = node->next;
                }
                curVertex->color = BLACK;
            }
        }
    };
    
    int main()
    {
        int  vertexNum;
        cout << "请输入要创建的图的结点数：";
        cin >> vertexNum;
        Graph<char, int> g(vertexNum,GraphType::UNDIR_UNWEIGHT_GRAPH);
        g.Create();
        g.Display();
        g.BFS();
        g.DFS();
    }