C++繼承實現鄰接矩陣和鄰接表

1、圖的父類

  是一個抽象類，不能實類化對象，應具有的是抽象方法，提供一個接口，在由子類繼承，實現自己的方法，

  應提供的共有抽象方法和保護的數據：

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;  //當前邊數

2、子類繼承、實現自己的方法

  C++實現，繼承的體現，是為了實現多態

  (1)Graph.h

#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;  //存放頂點關系的矩陣用邊表示
};
///////////////////////////////////////////////////////////////下面是鄰接表
template<typename Type>
class Edge{  //邊的存儲結構
public:
    Edge(int num) : dest(num), link(NULL){}
public:
    int dest;
    Edge *link;
};
template<typename Type>
class Vertex{  //頂點的存儲結構
public:
    Type data;
    Edge<Type> *adj;
};
template<typename Type>
class GraphLnk : public Graph<Type>{
#define maxVertices  Graph<Type>::maxVertices  //因為是模板，所以用父類的數據或方法都得加上作用域限定符
#define curVertices  Graph<Type>::curVertices
#define curEdges     Graph<Type>::curEdges
public:
    GraphLnk(int sz = VERTEX_DEFAULT_SIZE){
        maxVertices = sz > VERTEX_DEFAULT_SIZE ? sz : VERTEX_DEFAULT_SIZE;
        vertexTable = new Vertex<Type>[maxVertices];
        for(int i = 0; i < maxVertices; i++){
            vertexTable[i].data = 0;
            vertexTable[i].adj = NULL;
        }

        curVertices = curEdges = 0;
    }
public:
    bool insertVertex(const Type &v){
        if(curVertices >= maxVertices){
            return false;
        }
        vertexTable[curVertices++].data = v;
        return true;
    }
    bool insertEdge(const Type &v1, const Type &v2){
        int v = getVertexIndex(v1);
        int w = getVertexIndex(v2);

        if(v==-1 || w==-1){
            return false;
        }

        Edge<Type> *p = vertexTable[v].adj;
        while(p != NULL){  //這里主要判斷邊是否已經存在
            if(p->dest == w){   //無向圖，判斷一邊即可;
                return false;
            }
            p = p->link;
        }
        //v1-->v2  //采用頭插
        Edge<Type> *s = new Edge<Type>(w);
        s->link = vertexTable[v].adj;
        vertexTable[v].adj = s;

        //v2-->v1  //采用頭插
        Edge<Type> *q = new Edge<Type>(v);
        q->link = vertexTable[w].adj;
        vertexTable[w].adj = q;
        
        curEdges++;
        return true;
    }
    bool removeVertex(const Type &v){
        int i = getVertexIndex(v);
        if(i == -1){
            return false;
        }

        Edge<Type> *p = vertexTable[i].adj;
        while(p != NULL){
            vertexTable[i].adj = p->link;
            int k = p->dest;
            Edge<Type> *q = vertexTable[k].adj;
            if(q->dest == i){
                vertexTable[k].adj = q->link;
                delete q;
            }else{
                while(q->link != NULL && q->link->dest != i){
                    q = q->link;
                }
                Edge<Type> *t = q->link;
                q->link = t->link;
                delete t;
            }
            delete p;
            p = vertexTable[i].adj;
            curEdges--;
        }

        curVertices--;  //下面實行覆蓋
        vertexTable[i].data = vertexTable[curVertices].data;
        vertexTable[i].adj = vertexTable[curVertices].adj;
        vertexTable[curVertices].adj = NULL;

        int k = curVertices;
        p = vertexTable[i].adj;
        while(p != NULL){
            Edge<Type> *s = vertexTable[p->dest].adj;
            while(s != NULL){
                if(s->dest == k){
                    s->dest = i;
                    break;
                }
                s = s->link;
            }
            p = p->link;
        }
        return true;
    }
    bool removeEdge(const Type &v1, const Type &v2){
        int i = getVertexIndex(v1);
        int j = getVertexIndex(v2);


        if(i==-1 || j==-1){  //保證頂點的保存在
            return false;
        }
        //v1-->v2
        Edge<Type> *p = vertexTable[i].adj;
        if(p == NULL){  //判斷有沒有邊
            return false;
        }

        if(p->link == NULL && p->dest == j){ //刪除的是第一個邊，其后沒有邊了；
            vertexTable[i].adj = NULL;
            delete p;    
        }else if(p->dest == j){  //刪除的是第一個邊,并且其后還有邊
            vertexTable[i].adj = p->link;
            delete p;
        }else{
            while(p->link != NULL){
                if(p->link->dest == j){
                    Edge<Type> *q = p->link;
                    p->link = q->link;
                    delete q;
                }
                p = p->link;
            }
        }
        //v2-->v1
        Edge<Type> *s = vertexTable[j].adj;
        if(s == NULL){  //判斷有沒有邊
            return false;
        }

        if(s->link == NULL && s->dest == i){ //刪除的是第一個邊，其后沒有邊了；
            vertexTable[j].adj = NULL;
            delete s;
            curEdges--;
            return false;
        }else if(s->dest == i){  //刪除的是第一個邊,并且其后還有邊
            vertexTable[j].adj = s->link;
            delete s;
            curEdges--;
            return true;
        }else{
            while(s->link != NULL){
                if(s->link->dest == i){
                    Edge<Type> *q = s->link;
                    s->link = q->link;
                    delete q;
                    curEdges--;
                    return true;
                }
                s = s->link;
            }
        }

        return true;
    }
    int getFirstNeighbor(const Type &v){
        int i = getVertexIndex(v);
        if(i != -1){
            Edge<Type> *p = vertexTable[i].adj;
            if(p != NULL){
                return p->dest;
            }
        }

        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;
        }
        Edge<Type> *p = vertexTable[i].adj;
        while(p != NULL){
            if(p->dest == j && p->link != NULL){
                return p->link->dest;
            }
            p = p->link;
        }

        return -1;
    }
public:
    int getVertexIndex(const Type &v)const{
        for(int i = 0; i < curVertices; i++){
            if(vertexTable[i].data == v){
                return i;
            }
        }

        return -1;
    }
    void showGraph()const{
        for(int i = 0; i < curVertices; i++){
            cout<<vertexTable[i].data<<":-->";
            Edge<Type> *p = vertexTable[i].adj;
            while(p != NULL){
                cout<<p->dest<<"-->";
                p = p->link;
            }
            cout<<"Nul. "<<endl;
        }    
    }
private:
    Vertex<Type> *vertexTable;  //指向頂點的指針，是申請數組用的
};

#endif

    (2)、Graph.cpp

#include"Graph.h"

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();
///////////////////////////////////////////////////////////////////////////////////////////
    GraphLnk<char> gl;   //鄰接表
    gl.insertVertex('A');
    gl.insertVertex('B');
    gl.insertVertex('C');
    gl.insertVertex('D');
    gl.insertEdge('A','B');
    gl.insertEdge('A','D');
    gl.insertEdge('B','C');
    gl.insertEdge('C','D');
    gl.showGraph();

    cout<<gl.getFirstNeighbor('A')<<endl;
    cout<<gl.getNextNeighbor('A','B')<<endl;
    gl.removeEdge('B','C');
    cout<<"---------------------"<<endl;
    gl.removeVertex('B');
    gl.showGraph();

    return 0;
}

3、鄰接多重表

  是一個十字交叉鏈的形式；在很大程度上節省了空間，還是要對鏈表的操作很熟悉；