图

data_structure

(本文以邻接矩阵为例，存储无向网，介绍图中的各种算法)

一、图的存储

图在存储方面，可以分为两种方式：

• 邻接矩阵
• 邻接表

一张图会包括 顶点和边 ，同时，根据边是否有方向，可以把图分为：

• 有向图
• 无向图

然后 如果边上是带权的话，我们把对应的名字改为

• 有向网
• 无向网

下面，我们以无向网举例，来描述图这种数据结构，因为无向网中，包含了其他所有的特点，其他三种图存储类似。

1.1、邻接矩阵

template<class T>
MGraph<T>::MGraph(T v[], int n, int e)
//v--顶点值的数组，n--顶点数  e--边数//测试过，数据暂时来自于文件
{
    vexnum = n;
    edgenum = e;
    vexs.resize(vexnum);
    edges.resize(vexnum);   //将顶点表与邻接矩阵的行数赋值为顶点数
    int i, j, va, vb, w;
    for (i = 0; i < n; i++) //初始化顶点表
        vexs[i] = v[i];
    for (i = 0; i < n; i++) //预置邻接矩阵大小
        edges[i].resize(vexnum);
    for (i = 0; i < n; i++)//初始化邻接矩阵，
    {
        //对角线为0，其他置INFINITY
        for (j = 0; j < n; j++)
        {
            if (i == j)
                edges[i][j] = 0;            //网图邻接矩阵对角线元素为0
            else 
                edges[i][j] = INFINITY;
        }       
    }
    fstream cin;
    cin.open("data.txt");
    for (i = 0; i < e; i++)
    {
        cin >> va >> vb;                //输入一条边的两个端点的序号和边的权值
        cin >> w;
        edges[va][vb] = edges[vb][va] = w;  //无向网图
    }
    cin.close();
}

在构造函数中，我们需要初始化顶点表，初始化邻接矩阵，数据来源于文件（仅为了测试方便，这边并没有对文件进行规范化，不具有普遍性），经过构造函数后，我们就有了一个存贮这各顶点之间关系的矩阵。

1.2、邻接表

图的另一种存储方式，暂时不做介绍。

二、图的遍历

为了访问一张图中的数据，我们需要遍历一张图，与其他结构不同，图是多对多的结构，所以，我们要避免在图中的无限循环，这里，加上一个visited数组，里面的元素表示着节点的访问情况，对应数据为0，表示未访问，对应为1，表示已访问，根据访问规律的不同，这里介绍两种方式

• 深度优先搜索（DFS）
• 广度优先搜索（BFS）

2.1、深度优先搜索

大致思路如下：

• ①选取一个点作为搜索起点，
• ②对节点数据进行操作，并同时标记访问数组为1
• ③遍历该节点对应的邻接矩阵行，若存在边关系，且节点未访问，递归调用该函数
• ④直至标记数组全为1，或者剩下的节点之间没有边对应关系

但是要注意的是，结束条件中，有一个是剩下的节点没有对应关系了，所以光有这个方法，不能保证图中所有节点全部被访问，所以还需要一个全体循环，同时这个函数还能判断图是否连通，加入一个计数器，如DFS函数被调用超过一次，说明有节点之间没有边关系，所以是非连通图。

具体代码如下：

//连通图的深度优先遍历递归算法
template<class T>
void MGraph<T>::DFS(int v, bool *visited,bool flag)
//这个函数，适合连通图的遍历
{
    if (flag==0)
        cout << vexs[v];                //访问第v个顶点
    visited[v] = true;              //设置访问标志为true（已访问）
    for (int i = 0; i < vexnum; i++)//整体上，走完本行
        if ( (edges[v][i] != 0) && (edges[v][i] != INFINITY)  && !visited[i])//如果存在边，且节点没有访问过，递归访问，
            DFS(i, visited,flag);
}

//图的深度优先遍历递归算法
template<class T>
int MGraph<T>::DFSTraverse(bool flag)
{
    int i=0;
    bool *visited = new bool[vexnum];   //建立访问标记数组
    for (int v = 0; v < vexnum; v++)
        visited[v] = false;             //初始化访问标志数组（未被访问）
    for (v = 0; v < vexnum; v++)
        if (!visited[v])
        {
            DFS(v, visited,flag);               //对尚未访问的顶点调用DFS
            i++;
        }
    delete[]visited;
    return i;
}

这样，我们就能保证，所有的节点都被访问过了，而且访问顺序是一头栽倒底，没法继续了才回退到上一状态。

2.2、广度优先搜索

广度优先搜索，简单的说，就是按邻接矩阵的次序，一行行的访问(当然行的顺序与第一个不为0的边的位置有关)，检测到该节点已经被访问过，就跳过，一直到邻接矩阵的最后一个节点，这边需要用到队列，我选用的是STL的队列。

//图的广度优先遍历算法
template<class T>
void MGraph<T>::BFSTraverse()
{
    queue<int> q;   //构造队列q，其长度为10
    bool *visited = new bool[vexnum];
    int i, j;
    for (i = 0; i < vexnum; i++)
        visited[i] = false;
    for (i = 0; i < vexnum; i++)
    {
        if (!visited[i])
        {
            cout << vexs[i];
            visited[i] = true;
            q.push(i);
            while (!q.empty())
            {
                int u = q.front();
                q.pop();
                for (j = 0; j < vexnum; j++)
                {
                    if ( (edges[u][i] != 0) && (edges[u][i] != INFINITY)  && !visited[j])
                    {
                        cout << vexs[j];
                        visited[j] = true;
                        q.push(j);
                    }
                }
            }
        }
    }
    delete[]visited;
}

三、其他功能性函数

为了满足图的一些需求，编写了一些功能函数。

3.1、打印函数

直观的把邻接矩阵打出来，便于观察或者调试。同时会打印出顶点数，以及边数目。

template <class T>
void MGraph<T>::Print()
{
    cout<<"*****************************打印************************\n";
    for(int i=0; i<vexnum; i++)
        cout<<"\t"<<vexs[i];
    cout<<endl;
    cout<<"______________________________________________"<<endl;
    for(i=0; i<vexnum; i++)
    {
        cout<<vexs[i]<<"|"<<"\t";
        for(int j=0; j<vexnum; j++)
        {
            if (edges[i][j]!=INFINITY)
            {
                cout<<edges[i][j]<<"\t";
            }
            else
                cout<<"∞"<<"\t";
        }
            cout<<endl;
    }
    cout<<"顶点数:"<<vexnum<<"个"<<endl<<"边数:"<<edgenum<<"条"<<endl;
}

3.2、返回图中顶点数

//返回图中的边数
template<class T>
int MGraph<T>:: EdgeNum()
{
    return this->edgenum;
}

3.3、返回第i个顶点的值

若输入有误，返回空值

template<class T>
T MGraph<T>::GetVexValue(int i)
{
    if (i<vexnum &&i>=0)
        return this->vexs[i];
    else
        return NULL;
}

3.4、返回顶点表中值的序号

若找到，返回该值在顶点表中的序号，否则返回-1

template<class T>
int MGraph<T>::GetVexValueNum(T v)
{
    for (int i=0;i<vexs.size();i++)
    {
        if(vexs[i]==v)
            return i;
    }
    cout<<"Not found"<<endl;
    return -1;
}

3.5、返回邻接矩阵中第i个顶点到第j个顶点的权值

若找到，返回该位置在邻接矩阵中的权值，否则返回-1

template<class T>
int MGraph<T>::GetEdgeValue(int i, int j)
{
    if(i < vexnum && j < vexnum)
    {
        return edges[i][j];
    }
    else 
        cout<<"error!"<<endl;
    return -1;
}

3.6、插入一个顶点

仅插入点，没有任何边的关系,
方法：进行一系列扩容，并把顶点数+1；

template<class T>
void MGraph<T>::InsertVex(T v)
{
    int i;
    vexnum++;//定点数+1
    vexs.resize(vexnum);//扩容
    vexs[vexnum-1]=v;//赋值
    edges.resize(vexnum);   //扩充邻接矩阵行
    for (i=0; i<vexnum; i++)
        edges[i].resize(vexnum);//扩充邻接矩阵列
    //初始化邻接矩阵
    for (i=0; i<vexnum;i++)
    {
        edges[i][vexnum-1]=edges[vexnum-1][i]=INFINITY;
    }
    this->Print();
}

3.7、删除一个顶点

按输入值查找顶点，并删除该顶点及对应关系，成功返回true

template<class T>
bool MGraph<T>::RemoveVex(T v)
{
    int n=this->GetVexValueNum(v);
    if (n!=-1)
    {   
        int num=this->GetEdgeNum(n);
        this->vexnum--;
        this->edgenum=this->edgenum-num;
        vexs.erase(vexs.begin()+n);
        this->edges.erase(this->edges.begin()+n);
        for (int i=0;i<this->edges.size();i++)
        {
            this->edges[i].erase(this->edges[i].begin()+n);
        }
        this->Print();
        return true;
    }   
    return false;
}

3.8、插入一条边

满足边不存在，和点存在
//成功返回true

template<class T>
bool MGraph<T>::InsertEdge(EdgeType<T> e)
{
    int i=this->GetVexValueNum(e.head);
    int j=this->GetVexValueNum(e.tail); 
    if (i!=-1 && j!=-1 && i!=j&&edges[i][j]==INFINITY)
    {
        edges[i][j]=edges[j][i]=e.weight;
        this->edgenum++;
        return true;
    }
    return false;
}

3.9、删除一条边

成功返回true

template<class T>
bool MGraph<T>::DeleteEdge(EdgeType<T> e)
{
    int i=this->GetVexValueNum(e.head);
    int j=this->GetVexValueNum(e.tail); 
    if (i!=-1 && j!=-1 && i!=j)
    {
        edges[i][j]=edges[j][i]=INFINITY;
        this->edgenum--;
        return true;
    }
    return false;
}

3.10、遍历邻接矩阵&遍历邻接表

//遍历邻接矩阵
template<class T>
void MGraph<T>::PrintEdges()
{
    this->Print();
}

//遍历邻接表
template<class T>
void MGraph<T>::PrintVexs()
{
    for(int i=0; i<vexs.size(); i++)
        cout<<vexs[i]<<"\t";
    cout<<endl;
}

3.11、返回每个顶点相关的边数目

template<class T>
int MGraph<T>::GetEdgeNum(int n)
{
    int num=0;
    for (int i=0;i<vexnum;i++)
    {
        if (edges[n][i]!=0&&edges[n][i]!=INFINITY)
        {
            num++;
        }
    }
    return num;
}   

3.12、判断图是否为连通图

template<class T>
bool MGraph<T>::IsConnect()
{
    int i=this->DFSTraverse(1);
    if (i==1)
        return true;
    else
        return false;
}

四、最小生成树算法

首先 介绍一下生成树，简单的说，多一根线有回路，少一根线不连通。
然后，介绍一下最小生成树，也就是一张图中，每两点之间是有权值的，当权值之和小时，这棵树就是最小生成树。
下面介绍二中最小生成树的算法：Prim以及kruskal

4.1、Prim

算法是算出以某个顶点为起点的最小生成树

需要定义一个miniedges数组，元素类型为：

//最小生成树
template <class T>
struct Edge
{
    T adjvex;
    int lowcost;
};

这个数组很重要，是整个算法的核心部分，
数组一开始存储的是输入顶点的元素内容以及该顶点到对应其他顶点的权值，
通过循环，每次需要做下面几件事情:

• 找到miniedge中不为0的最小值权值的编号，返回，记为k
• 上述两个之间对应的是最小边，把其权值置为0，表明已经访问过，
• 下面修改值，以找到的第k个元素来修正miniedges参数，访问邻接矩阵中的第k行，把权值与miniedges中的权值进行比较，若更小，则替换miniegdes中的元素及其权值。否则不变。
• 这样，一轮循环下来，会找到与已经知晓的点权值最小的点
• 按照这个方法，只要找全所有的点，就生成了最小树

代码如下：

//Prim算法
template<class T>
void MGraph<T>::Prim(int v)
{
    if (!this->IsConnect())
    {
        cout<<"非连通图"<<endl;
        return ;
    }
    int i,j;
    Edge<T> * miniedges = new Edge<T> [vexnum];
    for(i=0; i<vexnum; i++)
    {
        miniedges[i].adjvex = GetVexValue(v);
        miniedges[i].lowcost = GetEdgeValue(v,i);
    }
    miniedges[v].lowcost = 0;
    for(i=1; i<vexnum; i++)
    {
        int k = MiniNum(miniedges);
        cout<<miniedges[k].adjvex<<"-->"<<GetVexValue(k)<<endl;
        miniedges[k].lowcost = 0;
        for(j=0; j<vexnum; j++)
        {
            if(GetEdgeValue(k,j)<miniedges[j].lowcost)
            {
                miniedges[j].adjvex = GetVexValue(k);
                miniedges[j].lowcost = GetEdgeValue(k,j);
            }
        }
    }
    delete []miniedges;
}

//返回最小权值的顶点
template<class T>
int MGraph<T>::MiniNum(Edge<T> * miniedges)
{
    int min = INFINITY;
    int k;
    for(int i=0;i<vexnum;i++)
    {
        if (miniedges[i].lowcost!=0 && (min > miniedges[i].lowcost) )
        {       
            min = miniedges[i].lowcost;
            k = i;
        }
    }
    return k;   
}

4.2、Kruskal算法

这个算法的思想，就是每次找最小权值的边，连起来即可，所以我们先要把所有边包含顶点的信息放到一个数组或者向量里面，并进行排序，注意，我们要选取的是不构成回路的最小边，所以，我们需要一个辅助数组来判断不构成回路：components数组。通过统一编号判断是否形成回路。
代码如下：

//Kruskal算法
template<class T>
void MGraph<T>::Kruskal(vector<EdgeType <T> >&tree)
{
    if (!this->IsConnect())
    {
        cout<<"非连通图"<<endl;
        return ;
    }
    int i;
    vector<EdgeType <T> >graph;
    GetGraph(graph);
    tree.resize(vexnum-1);
    int *components=new int[edgenum];
    for(i=0;i<vexnum;i++)
        components[i]=i;
    int k=0;
    int j=0;
    while(k<vexnum-1)
    {
        int h1=GetVexValueNum(graph[j].head);
        int t1=GetVexValueNum(graph[j].tail);
        int h2=components[h1];
        int t2=components[t1];
        if(h2!=t2)
        {
            tree[k].head=GetVexValue(h1);
            tree[k].tail=GetVexValue(t1);
            tree[k].weight=graph[j].weight;
            k++;
            for(i=0;i<vexnum;i++)
                if(components[i]==t2)
                    components[i]=h2;
        }
        j++;
    }
    delete []components;
}

//将图的边按权值排序，放到形参中
template<class T>
void MGraph<T>::GetGraph(vector<EdgeType<T> > &graph)
{
    graph.resize(edgenum);
    int min = 0;
    int k = 0;
    int i,j;
    for (i=0; i<vexnum; i++)//这边是为了把所有的非0，非无穷大边加入到向量中，并进行排序
    {
        for (j=0; j<i; j++)
        {
            if (edges[j][i]<INFINITY && i!=j)
            {
                graph[k].head = GetVexValue(j);
                graph[k].tail = GetVexValue(i);
                graph[k].weight = edges[j][i];
                k++;
            }
        }
    }
    EdgeType<T> e;
    for (i=1; i<edgenum; i++)
    {
        for (j=edgenum-1; j>=i; j--)                                                                                                                                                                                                                                                                     
        {
            if(graph[j].weight<graph[j-1].weight)
            {
                e = graph[j-1];
                graph[j-1] = graph[j];
                graph[j] = e;
                e = graph[j];
            }
        }
    }
}

还有注意，因为生成树必须是连通图，为了避免产生错误，我们最好再函数的开始加入是否为连通图的判定，若不是，空返回即可。

五、测试函数

对每个函数进行测试，以体现正确性。

int main()
{
    char a[]={'a','b','c','d','e'};
    MGraph<char> m(a,5,7);
    cout<<endl<<"打印测试："<<endl;
    m.Print();
    cout<<endl<<"深度遍历测试："<<endl;
    m.DFSTraverse();
    cout<<endl<<"广度遍历测试："<<endl;
    m.BFSTraverse();
    cout<<endl<<"返回图中顶点数："<<endl;
    cout<<m.VexterNum();                                //返回图中的顶点数量1
    cout<<endl<<"返回图中边数："<<endl;
    cout<<m.EdgeNum();                                  //返回图中的边数量1
    cout<<endl<<"返回顶点表中的第2个顶点的值："<<endl;
    cout<<m.GetVexValue(2);                         //返回顶点表中的第i个顶点的值1
    cout<<endl<<"返回顶点表中值‘c’的序号："<<endl;
    cout<<m.GetVexValueNum('c');                        //返回顶点表中值的序号1
    cout<<endl<<"返回邻接矩阵中第3个顶点到第2个顶点的权值："<<endl;
    cout<<m.GetEdgeValue(3,2);                  //返回邻接矩阵中第i个顶点到第j个顶点的权值1
    cout<<endl<<"返回序号3所连接的边的条数："<<endl;
    cout<<m.GetEdgeNum(3);                          //返回序号n所连接的边的条数
    cout<<endl<<"插入一个顶点'f'测试："<<endl;
    m.InsertVex('f');                           //插入一个顶点1
    cout<<endl<<"删除一个顶点'a'测试："<<endl;
    cout<<m.RemoveVex('a');                     //删除一个顶点1
    EdgeType<char> e={'f','e',5};
    cout<<endl<<"插入f-e边测试："<<endl;
    m.InsertEdge(e);                    //插入一条边1
    m.Print();
    cout<<endl<<"遍历邻接矩阵测试："<<endl;
    m.PrintEdges();                             //遍历邻接矩阵1
    cout<<endl<<"遍历邻接表测试："<<endl;
    m.PrintVexs();                              //遍历邻接表1
    cout<<endl<<"测试最小生成树（Prim）："<<endl;
    m.Prim();           //Prim算法求最小生成树
    cout<<endl<<"测试最小生成树（Kruskal）："<<endl;
    vector< EdgeType<char> > tree;
    m.Kruskal(tree);            //Kruskal算法构造最小生成树
    m.PrintSubTree(tree);
    cout<<endl<<"删除f-e边测试："<<endl;
    m.DeleteEdge(e);                    //删除一条边1
    m.Print();
    return 0;
}