图的邻接多重表存储

今天药忘吃喽~ 2022-08-05 05:07 140阅读 0赞

## Triple.h ##

//用二维数组初始化每条边的值
    template<class T>
    class Triple
    {
        public:
            int data[100][3];
            Triple()
            {
            }
            /*Triple(int arr[][],int n)
            {
                for(int i = 0 ;i < n;i++)
                {
                    this->data[i][0] = arr[i][0];
                    this->data[i][1] = arr[i][1];
                    this->data[i][2] = arr[i][2];
                }
            }*/
            ~Triple()
            {
            }
    };

## Ebox.h ##

//边节点
    template<class T>
    class Ebox
    {
        public:
            Ebox()
            {
            }
            int mark;
            int vertex_i;
            int vertex_j;
            int value;
            Ebox *i_link;//指向顶点I有关的下一条边 
            Ebox *j_link;//指向顶点J有关的下一条边 
    };

## LinkedMatrix.h ##

//顶点
    #include"Ebox.h"
    template<class T>
    class LinkedMatrix
    {
    
    
        public:
            int data;//顶点名称
            Ebox <T>*First_edge;//指向边链
            LinkedMatrix()
            {
            }
    };

## Adjacency\_mul.h ##

#include"LinkedMatrix.h"
    #include"Triple.h"
    #define MAX_INT 12345678
    template<class T>
    class AdjlistGraph
    {
        private:
            int n;//定点数
            LinkedMatrix <int> *adjlist;//邻接表
            int path[100][100];//记录两点最短路径
            int dist[100][100];//记录最短路径的值
        public:
            AdjlistGraph()
            {
                this->n = 0;
            }
            AdjlistGraph(int vertices[],int vertexCount,Triple<int>*edges,int edgeCount)
            {
                int i;
                this->n = vertexCount;
                adjlist = new LinkedMatrix<int>[vertexCount];
            // adjlist = new LinkedMatrix[this->n];
                for( i = 0;i < vertexCount;i++) 
                { 
                    adjlist[i].data = vertices[i];
                    adjlist[i].First_edge = NULL;
                } 
    
                for(i = 0;i < edgeCount;i++)
                {
                    Ebox<T> *p = new Ebox<T>;
                    p->vertex_i = edges->data[i][0];
                    p->vertex_j = edges->data[i][1];
                    p->value = edges->data[i][2];                               //头插边节点
                    p->i_link = adjlist[p->vertex_i].First_edge;
                    p->j_link = adjlist[p->vertex_j].First_edge ;
                    adjlist[p->vertex_i].First_edge = adjlist[p->vertex_j].First_edge  = p;
                }
    
    
            }
            void Mark_unvisited()
            {
            //标记一条边是否被访问过
                int i;
                Ebox<T>*p;
                for(i = 0;i < this->n;i++)
                {
                    p = adjlist[i].First_edge;
                    while(p)           //每个节点相邻的边都初始化
                    {
                        p->mark = 0;
                        if(p->vertex_i == i)
                        {
                            p = p->i_link;
                        }
                        else
                            p = p->j_link;
                    }
                }
            }
    
            void Display()
            {
            //输出边
                int i;
                Ebox<T>*p;
                Mark_unvisited();
                for(i = 0;i < this->n;i++)
                {
                    p = adjlist[i].First_edge;
                    while(p)
                    {
                            if(p->vertex_i == i)
                            {   
                                if(p->mark == 0)
                                {
                                    cout << p->vertex_i << "---" << p->vertex_j << "'s value = " << p->value <<endl;
                                    p->mark = 1;
                                }
                                p = p->i_link;
                            }
                            else
                            {
                                if(p->mark == 0)
                                {
                                    cout << p->vertex_i << "---" << p->vertex_j << "'s value = " << p->value <<endl;
                                    p->mark = 1;
    
                                }
                                 p = p->j_link;
                            }
    
    
                    }
                }
            }