一、图
二、图的邻接矩阵
三、图的实现方法
- 3.1 第一种方法实现
- 3.2 第二种方法实现
四、图的方法完整代码+测试代码+运行结果
六、说明

学习完“树”的数据结构，接下来就是“图”了，越复杂的数据结构，其实用性往往是最强的，图是需要掌握的。

一、图

图是一种非线性结构；主要由顶点和边构成；
<> 代表有向图，( )代表无向图；
无向图有N个顶点时，最多有N*(N-1)/2条边；有向图最多有N*(N-1)条边；
权：边上具有相关的数，带权图叫做网络；
邻接顶点: 与其接触边上的顶点；
度：与顶点V关联的边数；有向图中度 = 出度 + 入度；
简单路径：路径上各顶点互不重复；
回路/环：路径上第一个顶点与最后一个顶点重合；
连通图/强连通图：各顶点之间有边联系，有向图，双路径存在叫做强连通图；
生成树：是无向连通图的极小连通子图，若有N个顶点，则生成树由N-1条边构成！

二、图的邻接矩阵

邻接矩阵模型

就是将图的多对多的非线性结构用矩阵的方式表示；

我们必须知道：

会由矩阵来恢复图；
第一个邻接顶点：从列开始处，第一个边
下一个邻接顶点：给2个参数，第一个参数表示是谁的下一个邻接顶点，第二个表示从当前顶点开始其后的第一条边；
其顶点存放在数组空间中；
顶点之间的关系通过矩阵来表示边。

存储结构：

int maxVertices;  //最大顶点数
int curVertices;  //当前顶点数
int curEdges;     //当前边数
                  //用的是C++的继承
Type *vertexList; //存放顶点的数组
int **edge;       //存放顶点关系的矩阵用边表示

存储模型如下：

三、图的实现方法

均用C++实现；并且父类给了接口，子类继承实现即可；方便对不同的存储结构的编写。

核心方法，删除顶点。

3.1 第一种方法实现

bool removeVertex(const Type &v){
    int i = getVertexIndex(v);
    if(i == -1){
        return false;
    }
    for(int k = i; k < curVertices-1; ++k){
        vertexList[k] = vertexList[k+1];
    }

    int edgeCount = 0;
    for(int j = 0; j < curVertices; ++j){
        if(edge[i][j] != 0)
            edgeCount++;
    }
    //删除行
    for(int k = i; k < curVertices-1; ++k)
    {
        for(int j = 0; j < curVertices; ++j)
        {
            edge[k][j] = edge[k+1][j];
        }
    }
    //删除列
    for(int k = i; k < curVertices-1; ++k)
    {
        for(int j = 0; j < curVertices; ++j)
        {
            edge[j][k] = edge[j][k+1];
        }
    }

    curVertices--;
    curEdges -= edgeCount;

    return true;
}

以上存在数组的大量移动，效率太低；

3.2 第二种方法实现

bool removeVertex(const Type &v){
    int i = getVertexIndex(v);
    if(i == -1){
        return false;
    }
    vertexList[i] = vertexList[curVertices-1];
    int edgeCount = 0;
    for(int k = 0; k < curVertices; k++){
        if(edge[i][k] != 0){  //统计删除该行的边数
            edgeCount++;
        }
    }
    //删除行
    for(int j = 0; j < curVertices; j++){
        edge[i][j] = edge[curVertices-1][j];
    }
    //删除列
    for(j = 0; j < curVertices; j++){
        edge[j][i] = edge[j][curVertices-1];
    }
    curVertices--;
    curEdges -= edgeCount;
    return true;
}

第二种方法甚好，将要删除的顶点(连边一起删除),用最后一个元素(行/列)去覆盖删除的那个即可，之间的关系不变，但是就避免了大量移动，一次覆盖就好，效率极大！！！

模型如下：

四、图的方法完整代码+测试代码+运行结果

4.1 完整代码

用的是继承，方便写其它的存储结构代码。

#ifndef _GRAPH_H_
#define _GRAPH_H_

#include<iostream>
using namespace std;

#define VERTEX_DEFAULT_SIZE        10

template<typename Type>    
class Graph{
public:
    bool isEmpty()const{
        return curVertices == 0;
    }
    bool isFull()const{
        if(curVertices >= maxVertices || curEdges >= curVertices*(curVertices-1)/2)
            return true;  //图满有2种情况：(1)、当前顶点数超过了最大顶点数，存放顶点的空间已满
        return false;     //(2)、当前顶点数并没有满，但是当前顶点所能达到的边数已满
    }
    int getCurVertex()const{
        return curVertices;
    }
    int getCurEdge()const{
        return curEdges;
    }
public:
    virtual bool insertVertex(const Type &v) = 0;  //插入顶点
    virtual bool insertEdge(const Type &v1, const Type &v2) = 0; //插入边
    virtual bool removeVertex(const Type &v) = 0;  //删除顶点
    virtual bool removeEdge(const Type &v1, const Type &v2) = 0; //删除边
    virtual int getFirstNeighbor(const Type &v) = 0; //得到第一个相邻顶点
    virtual int getNextNeighbor(const Type &v, const Type &w) = 0; //得到下一个相邻顶点
public:
    virtual int getVertexIndex(const Type &v)const = 0; //得到顶点下标
    virtual void showGraph()const = 0;  //显示图
protected:
    int maxVertices;  //最大顶点数
    int curVertices;  //当前顶点数
    int curEdges;  //当前边数
};

template<typename Type>
class GraphMtx : public Graph<Type>{ //邻接矩阵继承父类矩阵
#define maxVertices  Graph<Type>::maxVertices  //因为是模板，所以用父类的数据或方法都得加上作用域限定符
#define curVertices  Graph<Type>::curVertices
#define curEdges     Graph<Type>::curEdges
public:
    GraphMtx(int vertexSize = VERTEX_DEFAULT_SIZE){  //初始化邻接矩阵
        maxVertices = vertexSize > VERTEX_DEFAULT_SIZE ? vertexSize : VERTEX_DEFAULT_SIZE;
        vertexList = new Type[maxVertices]; //申请顶点空间
        for(int i = 0; i < maxVertices; i++){  //都初始化为0
            vertexList[i] = 0;
        }
        edge = new int*[maxVertices];  //申请边的行
        for(i = 0; i < maxVertices; i++){ //申请列空间
            edge[i] = new int[maxVertices];
        }
        for(i = 0; i < maxVertices; i++){ //赋初值为0 
            for(int j = 0; j < maxVertices; j++){
                edge[i][j] = 0;
            }
        }
        curVertices = curEdges = 0; //当前顶点和当前边数
    }
    GraphMtx(Type (*mt)[4], int sz){  //通过已有矩阵的初始化
        int e = 0; //统计边数
        maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE;
        vertexList = new Type[maxVertices]; //申请顶点空间
        for(int i = 0; i < maxVertices; i++){  //都初始化为0
            vertexList[i] = 0;
        }
        edge = new int*[maxVertices];  //申请边的行
        for(i = 0; i < maxVertices; i++){ //申请列空间
            edge[i] = new Type[maxVertices];
        }
        for(i = 0; i < maxVertices; i++){ //赋初值为矩阵当中的值
            for(int j = 0; j < maxVertices; j++){
                edge[i][j] = mt[i][j];
                if(edge[i][j] != 0){
                    e++; //统计列的边数
                }
            }
        }
        curVertices = sz;
        curEdges = e/2;
    }
    ~GraphMtx(){}
public:
    bool insertVertex(const Type &v){
        if(curVertices >= maxVertices){
            return false;
        }
        vertexList[curVertices++] = v;
        return true;
    }
    bool insertEdge(const Type &v1, const Type &v2){
        int maxEdges = curVertices*(curVertices-1)/2;
        if(curEdges >= maxEdges){
            return false;
        }

        int v = getVertexIndex(v1);
        int w = getVertexIndex(v2);

        if(v==-1 || w==-1){
            cout<<"edge no exit"<<endl; //要插入的顶点不存在，无法插入
            return false;
        }
        if(edge[v][w] != 0){  //当前边已经存在，不能进行插入
            return false;
        }

        edge[v][w] = edge[w][v] = 1; //因为是无向图，对称的，存在边赋为1；
        return true; 
    }  //删除顶点的高效方法
    bool removeVertex(const Type &v){
        int i = getVertexIndex(v);
        if(i == -1){
            return false;
        }
        vertexList[i] = vertexList[curVertices-1];
        int edgeCount = 0;
        for(int k = 0; k < curVertices; k++){
            if(edge[i][k] != 0){  //统计删除该行的边数
                edgeCount++;
            }
        }
        //删除行
        for(int j = 0; j < curVertices; j++){
            edge[i][j] = edge[curVertices-1][j];
        }
        //删除列
        for(j = 0; j < curVertices; j++){
            edge[j][i] = edge[j][curVertices-1];
        }
        curVertices--;
        curEdges -= edgeCount;
        return true;
    }
/*  //删除顶点用的是数组一个一个移动的方法，效率太低。
    bool removeVertex(const Type &v){
        int i = getVertexIndex(v);
        if(i == -1){
            return false;
        }
        for(int k = i; k < curVertices-1; ++k){
            vertexList[k] = vertexList[k+1];
        }

        int edgeCount = 0;
        for(int j = 0; j < curVertices; ++j){
            if(edge[i][j] != 0)
                edgeCount++;
        }

        for(int k = i; k < curVertices-1; ++k)
        {
            for(int j = 0; j < curVertices; ++j)
            {
                edge[k][j] = edge[k+1][j];
            }
        }

        for(int k = i; k < curVertices-1; ++k)
        {
            for(int j = 0; j < curVertices; ++j)
            {
                edge[j][k] = edge[j][k+1];
            }
        }

        curVertices--;
        curEdges -= edgeCount;

        return true;
    }        
*/
    bool removeEdge(const Type &v1, const Type &v2){
        int v = getVertexIndex(v1);
        int w = getVertexIndex(v2);

        if(v==-1 || w==-1){  //判断要删除的边是否在当前顶点内
            return false;  //顶点不存在
        }
        if(edge[v][w] == 0){ //这个边根本不存在，没有必要删
            return false;
        }
        edge[v][w] = edge[w][v] = 0; //删除这个边赋值为0，代表不存在；
        curEdges--;

        return true;
    }
    int getFirstNeighbor(const Type &v){
        int i = getVertexIndex(v);
        if(i == -1){
            return -1;
        }
        for(int col = 0; col < curVertices; col++){
            if(edge[i][col] != 0){
                return col;
            }
        }
        return -1;
    }
    int getNextNeighbor(const Type &v, const Type &w){
        int i = getVertexIndex(v);
        int j = getVertexIndex(w);

        if(i==-1 || j==-1){
            return -1;
        }
        for(int col = j+1; col < curVertices; col++){
            if(edge[i][col] != 0){
                return col;
            }
        }

        return -1;
    }
public:
    void showGraph()const{
        if(curVertices == 0){
            cout<<"Nul Graph"<<endl;
            return;
        }

        for(int i = 0; i < curVertices; i++){
            cout<<vertexList[i]<<"  "; 
        }
        cout<<endl;
        for(i = 0; i < curVertices; i++){
            for(int j = 0; j < curVertices; j++){
                cout<<edge[i][j]<<"  ";
            }
            cout<<vertexList[i]<<endl;
        }
    }
    int getVertexIndex(const Type &v)const{
        for(int i = 0; i < curVertices; i++){
            if(vertexList[i] == v){
                return i;
            }
        }

        return -1;
    }
private:
    Type *vertexList;  //存放顶点的数组
    int **edge;  //存放顶点关系的矩阵用边表示
};

#endif

4.2 测试代码

#include"Graph.h"

#define VERTEX_SIZE        4

int main(void){
    GraphMtx<char> gm;

    gm.insertVertex('A'); //插入顶点
    gm.insertVertex('B');
    gm.insertVertex('C');
    gm.insertVertex('D');

    gm.insertEdge('A','B'); //插入边
    gm.insertEdge('A','D');
    gm.insertEdge('B','C');
    gm.insertEdge('C','D');

    cout<<gm.getFirstNeighbor('A')<<endl; //B
    cout<<gm.getNextNeighbor('A','B')<<endl;//D
    gm.showGraph();
    gm.removeEdge('A','B');
    gm.removeVertex('B');
    cout<<"-----------------------------------------------------------------"<<endl;
    gm.showGraph();


/*  用矩阵关系直接初始化图，没啥意思
    int mtx[VERTEX_SIZE][VERTEX_SIZE] = {
                                            {0, 1, 0, 1},
                                            {1, 0, 1, 0},
                                            {0, 1, 0, 1},
                                            {1, 0, 1, 0},  
    };
    GraphMtx<int> gm(mtx, VERTEX_SIZE);
    gm.showGraph();
*/
    return 0;
}

4.3 运行结果

六、说明

原创文章链接：从零开始学习数据结构-->图之邻接矩阵

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

从零开始学习数据结构_图之邻接矩阵.md

从零开始学习数据结构_图之邻接矩阵.md

一、图

二、图的邻接矩阵

三、图的实现方法

3.1 第一种方法实现

3.2 第二种方法实现

四、图的方法完整代码+测试代码+运行结果

4.1 完整代码

4.2 测试代码

4.3 运行结果

六、说明

Files

从零开始学习数据结构_图之邻接矩阵.md

Latest commit

History

从零开始学习数据结构_图之邻接矩阵.md

File metadata and controls

一、图

二、图的邻接矩阵

三、图的实现方法

3.1 第一种方法实现

3.2 第二种方法实现

四、图的方法完整代码+测试代码+运行结果

4.1 完整代码

4.2 测试代码

4.3 运行结果

六、说明