圖的鄰接表實現_LGraph

鄰接表是圖的另一種有效的存儲表示方法. 每個頂點u建立一個單鏈表, 鏈表中每個結點代表一條邊<u, v>, 為邊結點. 每個單鏈表相當于

鄰接矩陣的一行.

adjVex域指示u的一個鄰接點v, nxtArc指向u的下一個邊結點. 如果是網, 增加一個w域存儲邊上的權值.

構造函數完成對一維指針數組a的動態空間存儲分配, 并對其每個元素賦初值NULL. 析構函數首先釋放鄰接表中所有結點, 最后釋放一維

指針數組a所占的空間.

包含的函數Exist(): 若輸入的u, v無效, 則函數返回false. 否則從a[u]指示的邊結點開始, 搜索adjVex值為v的邊結點, 代表邊<u, v>, 若搜索

成功, 返回true, 否則返回false.

函數Insert(): 若輸入的u, v無效, 則插入失敗, 返回Failure. 否則從a[u]指示的邊開始, 搜索adjVex值為v的邊結點, 若不存在這樣的邊結

點, 則創建代表邊<u, v>的新邊結點, 并將其插在由指針a[u]所指示的單鏈表最前面, 并e++. 否則表示<u, v>是重復邊, 返回Duplicate.

函數Remove(): 若輸入的u, v無效, 則刪除失敗, 返回Failure. 否則從a[u]指示的邊開始, 搜索adjVex值為v的邊結點, 若存在這樣的邊, 刪

除邊, e--, 返回Success. 否則表示不存邊<u, v>, 返回NotPresent.

實現代碼:

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
#include "queue"
#include "stack"
#include "cmath"
#include "utility"
#include "map"
#include "set"
#include "vector"
#include "list"
#include "string"
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
enum ResultCode { Underflow, Overflow, Success, Duplicate, NotPresent, Failure };
template <class T>
struct ENode
{
    ENode() { nxtArc = NULL; }
    ENode(int vertex, T weight, ENode *nxt) {
        adjVex = vertex;
        w = weight;
        nxtArc = nxt;
    }
    int adjVex;
    T w;
    ENode *nxtArc;
    /* data */
};
template <class T>
class Graph
{
public:
    virtual ~Graph() {}
    virtual ResultCode Insert(int u, int v, T &w) = 0;
    virtual ResultCode Remove(int u, int v) = 0;
    virtual bool Exist(int u, int v) const = 0;
    /* data */
};
template <class T>
class LGraph: public Graph<T>
{
public:
    LGraph(int mSize);
    ~LGraph();
    ResultCode Insert(int u, int v, T &w);
    ResultCode Remove(int u, int v);
    bool Exist(int u, int v) const;
    int Vertices() const { return n; }
    void Output();
protected:
    ENode<T> **a;
    int n, e;
    /* data */
};
template <class T>
void LGraph<T>::Output()
{
    ENode<T> *q;
    for(int i = 0; i < n; ++i) {
        q = a[i];
        while(q) {
            cout << '(' << i << ' ' << q -> adjVex << ' ' << q -> w << ')';
            q = q -> nxtArc;
        }
        cout << endl;
    }
    cout << endl << endl;
}
template <class T>
LGraph<T>::LGraph(int mSize)
{
    n = mSize;
    e = 0;
    a = new ENode<T>*[n];
    for(int i = 0; i < n; ++i)
        a[i] = NULL;
}
template <class T>
LGraph<T>::~LGraph()
{
    ENode<T> *p, *q;
    for(int i = 0; i < n; ++i) {
        p = a[i];
        q = p;
        while(p) {
            p = p -> nxtArc;
            delete q;
            q = p;
        }
    }
    delete []a;
}
template <class T>
bool LGraph<T>::Exist(int u, int v) const
{
    if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return false;
    ENode<T> *p = a[u];
    while(p && p -> adjVex != v) p = p -> nxtArc;
    if(!p) return false;
    return true;
}
template <class T>
ResultCode LGraph<T>::Insert(int u, int v, T &w)
{
    if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
    if(Exist(u, v)) return Duplicate;
    ENode<T> *p = new ENode<T>(v, w, a[u]);
    a[u] = p;
    e++;
    return Success;
}
template <class T>
ResultCode LGraph<T>::Remove(int u, int v)
{
    if(u < 0 || v < 0 || u > n - 1 || v > n - 1 || u == v) return Failure;
    ENode<T> *p = a[u], *q = NULL;
    while(p && p -> adjVex != v) {
        q = p;
        p = p -> nxtArc;
    }
    if(!p) return NotPresent;
    if(q) q -> nxtArc = p -> nxtArc;
    else a[u] = p -> nxtArc;
    delete p;
    e--;
    return Success;
}
int main(int argc, char const *argv[])
{
    LGraph<int> lg(4);
    int w = 4; lg.Insert(1, 0, w); lg.Output();
    w = 5; lg.Insert(1, 2, w); lg.Output();
    w = 3; lg.Insert(2, 3, w); lg.Output();
    w = 1; lg.Insert(3, 0, w); lg.Output();
    w = 1; lg.Insert(3, 1, w); lg.Output();
    return 0;
}

來自： http://blog.csdn.net/gkhack/article/details/50214577