图-邻接矩阵

这是一篇关于无向带权图的模板代码整理，用邻接矩阵表示图，实现图的深度优先遍历和广度优先遍历。

也可以改为有向带权图，需要在插入、删除函数作出相应的改变。

邻接矩阵表示图优缺点总结：稠密图用邻接矩阵。

• 邻接矩阵把所有结点的信息都保留下来，信息保留全面，查询也方便；但，当图中结点的之间联系较少时，这时的邻接矩阵为稀疏矩阵，存储了大量的0或无穷值。信息价值密度低。只有稠密图对应的邻接矩阵才不是稀疏矩阵，因此，复杂的图用邻接矩阵表示为佳。

 

//
//  main.cpp
//  图-邻接矩阵
//
//  Created by scnulpc on 2018/10/22.
//  Copyright © 2018年 scnulpc. All rights reserved.
//

#include <iostream>
#include <queue>
#define maxWeight 99
using namespace std;
const int DefaultVertices = 30;

template <class T,class E>
class Graph     //带权无向图
{
private:
    T * VerticesList;   //顶点表
    E **Edge;           //邻接矩阵
    int maxVertices;    //图中最大顶点数
    int numEdges;       //当前边数
    int numVertices;    //当前顶点数
    
    
public:
    Graph(int sz=DefaultVertices);
    ~Graph();
    int numberOfVertices(){return numVertices;}
    int numberOfEdge(){return numEdges;}
    int getVertexPosition(T v);         //获取顶点v的位置
    T getValue(int i);                  //取顶点i的值，i不合理返回0
    E getWeight(int v1,int v2);         //取边（v1,v2）边上的权值
    int getFirstNeighbor(int v);        //取顶点v的第一个邻接顶点
    int getNextNeighbor(int v,int w);   //取v的邻接顶点w的下一个邻接顶点
    bool insertVertex(const T& vertex); //插入顶点vertex
    bool insertEdge(int v1,int v2,E weight);//插入边
    bool removeVertex(int v);           //删除顶点v及其关联的边
    bool removeEdge(int v1,int v2);     //删除边（v1，v2）
    friend istream& operator>>(istream& in,Graph<T,E> &g);//重载输入
    friend ostream& operator<<(ostream& out,Graph<T,E> &g);//重载输出
    void input();   //测试输入
    void output();  //测试输出
    void outputAsMatrix();  //测试输出
};

template <class T,class E>
Graph<T, E>::Graph(int sz)
{
    VerticesList = new T[sz];
    maxVertices=sz;
    numVertices=0;
    numEdges=0;
    Edge = new E* [sz];
    for (int i=0; i<maxVertices; i++)
    {
        Edge[i] = new E[sz];
    }
    for (int i=0; i<maxVertices; i++)
    {
        for (int j=0; j<maxVertices; j++)
        {
            if (i==j) Edge[i][j]=0;
            else Edge[i][j] = maxWeight;
        }
    }
}
template <class T,class E>
Graph<T, E>::~Graph<T, E>()
{
    delete []VerticesList;
    delete []Edge;
}
template <class T,class E>
int Graph<T,E>::getVertexPosition(T v)
{
    for (int i=0; i<numVertices; i++) {
        if (VerticesList[i]==v)return i;
    }
    return -1;
}
template <class T,class E>
T Graph<T,E>::getValue(int i)
{
    return (i>=0&&i<numVertices)? VerticesList[i]:0;
}
template <class T,class E>
E Graph<T,E>::getWeight(int v1, int v2)
{
    return (v1!=-1&&v2!=-1)? Edge[v1][v2]:0;
}
template <class T,class E>
int  Graph<T,E>::getFirstNeighbor(int v)
{
    if (v!=-1) {
        for (int i=0; i<numVertices; i++) {
            if (Edge[v][i]>0&&Edge[v][i]<maxWeight) return i;
        }
    }
    return -1;
}
template <class T,class E>
int  Graph<T,E>::getNextNeighbor(int v, int w)
{
    if (v!=-1&&w!=-1) {
        for (int column = w+1; column<numVertices; column++) {
            if (Edge[v][column]>0&&Edge[v][column]<maxWeight) return column;
        }
    }
    return -1;
}

template <class T,class E>
bool Graph<T,E>::insertVertex(const T &vertex)
{
    if (numVertices==maxVertices) return false;
    VerticesList[numVertices++]=vertex;
    return true;
}
template <class T,class E>
bool  Graph<T,E>::insertEdge(int v1, int v2, E weight)
{
    if (v1!=-1&&v2!=-1) {
        Edge[v1][v2]=Edge[v2][v1]=weight;
        return true;
    }
    return false;
}
template <class T,class E>
bool Graph<T,E>::removeVertex(int v)    //充分利用要被删除的那一行，那一列的空间，替换为最后一行，一列，numVertex--
{
    if (v<0||v>=numVertices)return false;   //顶点不在图中
    if (numVertices==1) return false;       //只剩一个顶点，不删除
    VerticesList[v]=VerticesList[numVertices-1];//顶点表中删除该结点
    for (int i=0; i<numVertices; i++)
    {
        if (Edge[v][i]>0&&Edge[v][i]<maxWeight)
        {
            //Edge[v][i]=Edge[i][v]=maxWeight;
            numEdges--;
        }
    }
    for (int i=0; i<numVertices; i++)       //用最后一列填补第v列
    {
        Edge[i][v] = Edge[i][numVertices-1];
        Edge[i][numVertices-1] = maxWeight;
    }
    for (int i=0; i<numVertices; i++)       //用最后一行填补第v行
    {
        Edge[v][i]=Edge[numVertices-1][i];
        Edge[numVertices-1][i]=maxWeight;
    }
    Edge[numVertices-1][numVertices-1]=0;   //对角线为0
    numVertices--;                          //顶点数减一
    return true;
}

template <class T,class E>
bool Graph<T,E>::removeEdge(int v1, int v2)
{
    if (v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices&&Edge[v1][v2]>0&&Edge[v1][v2]<maxWeight)
    {
        Edge[v1][v2]=Edge[v2][v1]=maxWeight;
        numEdges--;
        return true;
    }
    return false;
}

template <class T,class E>
istream& operator>>(istream& in,Graph<T, E> &g)
{
    int i,j,k,n,m;
    T e1,e2;
    E weight;
    cout<<"输入顶点数n和变数m"<<endl;
    in>>n>>m;
    cout<<"输入"<<n<<"个顶点的信息"<<endl;
    for (i=0; i<n; i++)
    {
        in>>e1;
        g.insertVertex(e1);
    }
    i=0;
    cout<<"输入"<<m<<"条边的信息\n端点e1 端点e2 权重"<<endl;
    while(i<m)
    {
        in>>e1>>e2>>weight;
        j=g.getVertexPosition(e1);
        k=g.getVertexPosition(e2);
        if (j==-1||k==-1) {
            cout<<"边两端信息有误，重新输入这条边"<<endl;
        }
        else
        {
            g.insertEdge(e1, e2, weight);
        }
    }
    return in;
}
template <class T,class E>
ostream& operator<<(ostream& out,Graph<T, E> &g)
{
    int i,j,n,m;T e1,e2;E w;
    n=g.numberOfVertices();
    m=g.numberOfEdge();
    out<<n<<","<<m<<endl;
    for (i=0; i<n; i++) {
        for (j=i+1; j<n; j++)
        {
            w=g.getWeight(i, j);
            if (w>0&&w<w<maxWeight) {
                e1 = g.getValue(i);
                e2 = g.getValue(j);
                out<<"("<<e1<<","<<e2<<","<<w<<")"<<endl;
            }
        }

    }
    return out;
}
template <class T,class E>
void Graph<T,E>::input()
{
    int i,j,k,n,m;
    T e1,e2;
    E weight;
    cout<<"输入顶点数n和变数m"<<endl;
    cin>>n>>m;
    cout<<"输入"<<n<<"个顶点的信息"<<endl;
    for (i=0; i<n; i++)
    {
        cin>>e1;
        insertVertex(e1);
    }
    i=0;
    cout<<"输入"<<m<<"条边的信息\n端点e1 端点e2 权重"<<endl;
    while(i<m)
    {
        cin>>e1>>e2>>weight;
        j=getVertexPosition(e1);
        k=getVertexPosition(e2);
        if (j==-1||k==-1) {
            cout<<"边两端信息有误，重新输入这条边"<<endl;
        }
        else
        {
            insertEdge(j, k, weight);
            i++;
        }
    }
    
}
template <class T,class E>
void Graph<T,E>::output()
{
    int i,j,n,m;T e1,e2;E w;
    n=numberOfVertices();
    m=numberOfEdge();
    cout<<n<<","<<m<<endl;
    for (i=0; i<n; i++) {
        for (j=i+1; j<n; j++)
        {
            w=getWeight(i, j);
            if (w>0&&w<w<maxWeight) {
                e1 = getValue(i);
                e2 = getValue(j);
                cout<<"("<<e1<<","<<e2<<","<<w<<")"<<endl;
            }
        }
        
    }
    
}
template <class T,class E>
void Graph<T,E>::outputAsMatrix()
{
    int i,j,n,m;T e1,e2;E w;
    n=numberOfVertices();
    m=numberOfEdge();
    cout<<n<<","<<m<<endl;
    cout<<"   ";
    for (int i=0; i<n; i++) {
        cout<<VerticesList[i]<<"  ";
    }
    cout<<endl;
    for (i=0; i<n; i++) {
        cout<<VerticesList[i]<<" ";
        for (j=0; j<n; j++)
        {
            w=getWeight(i, j);
            cout<<w<<" ";
        }
        cout<<endl;
    }
}

//邻接矩阵图的深度优先搜索
template <class T,class E>
void DFS(Graph<T,E> *G,const T v)
{
    int n = G->numberOfVertices();
    bool *visit = new bool[n];
    for (int i=0; i<n; i++)visit[i]=false;
    int index = G->getVertexPosition(v);
    DFS(G, index, visit);
    delete []visit;
        
}
template <class T,class E>
void DFS(Graph<T,E> *G,int v,bool visit[])
{
    cout<<G->getValue(v)<<" ";
    visit[v]=1;
    int w = G->getFirstNeighbor(v);
    while (w!=-1)
    {
        if (visit[w]==false) DFS(G, w, visit);
        w=G->getNextNeighbor(v, w);
    }
}

//邻接矩阵图的广度遍历
template <class T,class E>
void BFS(Graph<T,E> *G,const T v)
{
    int index = G->getVertexPosition(v);
    if (index==-1) return;
    queue<int > q ;
    q.push(index);
    int n = G->numberOfVertices();
    bool *visited = new bool[n];
    for (int i=0; i<n; i++)visited[i]=false;
    visited[index]=true;
    int temp;
    while (!q.empty())
    {
        temp = q.front();q.pop();
        cout<<G->getValue(temp)<<" ";
        
        int w = G->getFirstNeighbor(temp);
        while (w!=-1) {
            if (visited[w]==false) {q.push(w);visited[w]=true;}
            w = G->getNextNeighbor(temp, w);
        }
    }
    
}
/*测试数据 9 10 A B C D E F G H I
 A D 1
 A C 1
 A B 1
 B E 1
 B C 1
 E G 1
 D F 1
 C F 1
 F H 1
 H I 1
 */
int main(int argc, const char * argv[])
{
    Graph<char, int > *graph = new Graph<char, int>(20);
    graph->input();
    graph->output();
    graph->outputAsMatrix();
    DFS(graph, 'A');
    cout<<endl;
    cout<<"广度遍历"<<endl;
    BFS(graph, 'A');
    return 0;
}