Graph(2)--图的实现（邻接矩阵&邻接表 ）

1.邻接矩阵&邻接表

Adjacency matrix O(N2)
Adjacency list O(E+N)
If the graph is sparse, and there are not many edges, then adjacency lists will probably be more space efficient than adjacency matrices.
If the graph is dense, and the number of edges is O(N2), then the adjacency matrix will probably be more space efficient.

2.图的邻接矩阵实现

图的度

网络（带权图）的邻接矩阵

3.图的邻接表实现

无向图

有向图

带权值的

4.图的实现（C++）

4.1 邻接矩阵

#ifndef A_H_INCLUDED
#define A_H_INCLUDED
#include<iostream>
#include<iomanip>
using namespace std;
#define MAXWEIGHT 100//最大权值
////////////////////////////////////
//用邻接矩阵实现图
class Graph
{
private:
    //是否带权
    bool isWeighted;
    //是否有向
    bool isDirected;
    //顶点数
    int numV;
    //边数
    int numE;
    //邻接矩阵
    int **matrix;
public:
    /*
    构造方法
    numV是顶点数，isWeighted是否带权值，isDirected是否有方向
    */
    Graph(int numV, bool isWeighted = false, bool isDirected = false);
    //建图
    void createGraph();
    //析构方法
    ~Graph();
    //获取顶点数
    int getVerNums()
    {return numV;}
    //获取边数
    int getEdgeNums()
    {return numE;}
    //设置指定边的权值
    void setEdgeWeight(int tail, int head, int weight);
    //打印邻接矩阵
    void printAdjacentMatrix();
    //检查输入
    bool check(int i, int j, int w = 1);
};

/*
构造方法
numV是顶点数，isWeighted是否带权值，isDirected是否有方向
*/
Graph::Graph(int numV, bool isWeighted, bool isDirected)
{
    while (numV <= 0)
    {
        cout << "输入的顶点数不正确！，重新输入 ";
        cin >> numV;
    }
    this->numV = numV;
    this->isWeighted = isWeighted;
    this->isDirected = isDirected;

    matrix = new int*[numV];  //指针数组
    int i, j;
    for (i = 0; i < numV; i++)
        matrix[i] = new int[numV];

    //对图进行初始化
    if (!isWeighted)  //无权图
    {
        //所有权值初始化为0
        for (i = 0; i < numV; i++)
        for (j = 0; j < numV; j++)
            matrix[i][j] = 0;
    }
    else  //有权图
    {
        //所有权值初始化为最大权值
        for (i = 0; i < numV; i++)
        for (j = 0; j < numV; j++)
            matrix[i][j] = MAXWEIGHT;
    }
}



//建图
void Graph::createGraph()
{
    cout << "输入边数 ";
    while (cin >> numE && numE < 0)
        cout << "输入有误！，重新输入 ";

    int i, j, w;
    if (!isWeighted)  //无权图
    {
        if (!isDirected)  //无向图
        {
            cout << "输入每条边的起点和终点：\n";
            for (int k = 0; k < numE; k++)
            {
                cin >> i >> j;
                while (!check(i, j))
                {
                    cout << "输入的边不对！重新输入\n";
                    cin >> i >> j;
                }
                matrix[i][j] = matrix[j][i] = 1;
            }
        }
        else  //有向图
        {
            cout << "输入每条边的起点和终点：\n";
            for (int k = 0; k < numE; k++)
            {
                cin >> i >> j;
                while (!check(i, j))
                {
                    cout << "输入的边不对！重新输入\n";
                    cin >> i >> j;
                }
                matrix[i][j] = 1;
            }
        }
    }
    else  //有权图
    {
        if (!isDirected)   //无向图
        {
            cout << "输入每条边的起点、终点和权值：\n";
            for (int k = 0; k < numE; k++)
            {
                cin >> i >> j >> w;
                while (!check(i, j, w))
                {
                    cout << "输入的边不对！重新输入\n";
                    cin >> i >> j >> w;
                }
                matrix[i][j] = matrix[j][i] = w;
            }
        }
        else  //有向图
        {
            cout << "输入每条边的起点、终点和权值：\n";
            for (int k = 0; k < numE; k++)
            {
                cin >> i >> j >> w;
                while (!check(i, j, w))
                {
                    cout << "输入的边不对！重新输入\n";
                    cin >> i >> j >> w;
                }
                matrix[i][j] = w;
            }
        }
    }
}
//析构方法
Graph::~Graph()
{
    int i = 0;
    for (i = 0; i < numV; i++)
        delete[] matrix[i];
    delete[]matrix;
}

//设置指定边的权值
void Graph::setEdgeWeight(int tail, int head, int weight)
{
    if (isWeighted)
    {
        while (!check(tail, head, weight))
        {
            cout << "输入不正确，重新输入边的起点、终点和权值 ";
            cin >> tail >> head >> weight;
        }
        if (isDirected)
            matrix[tail][head] = weight;
        else
            matrix[tail][head] = matrix[head][tail] = weight;
    }
    else
    {
        while (!check(tail, head, 1))
        {
            cout << "输入不正确，重新输入边的起点、终点 ";
            cin >> tail >> head;
        }
        if (isDirected)
            matrix[tail][head] = 1-matrix[tail][head];
        else
            matrix[tail][head] = matrix[head][tail] = 1 - matrix[tail][head];
    }
}
//输入检查
bool Graph::check(int i, int j, int w)
{
    if (i >= 0 && i < numV && j >= 0 && j < numV && w > 0 && w <= MAXWEIGHT)
        return true;
    else
        return false;
}
//打印邻接矩阵
void Graph::printAdjacentMatrix()
{
    int i, j;
    cout.setf(ios::left);
    cout << setw(4) << " ";
    for (i = 0; i < numV; i++)
        cout << setw(4) << i;
    cout << endl;
    for (i = 0; i < numV; i++)
    {
        cout << setw(4) << i;
        for (j = 0; j < numV; j++)
            cout << setw(4) << matrix[i][j];
        cout << endl;
    }
}
////////////////////////////////////
#endif // A_H_INCLUDED

main.cpp

#include <iostream>
#include <iomanip>
#include <stdlib.h>
#include "a.h"
using namespace std;
int main()
{
    cout << "******使用邻接矩阵实现图结构******" << endl;
    bool isDirected, isWeighted;
    int numV;
    cout << "建图" << endl;
    cout << "输入顶点数 ";
    cin >> numV;
    cout << "边是否带权值，0(不带) or 1(带) ";
    cin >> isWeighted;
    cout << "是否是有向图，0(无向) or 1(有向) ";
    cin >> isDirected;
    Graph graph(numV, isWeighted, isDirected);
    cout << "这是一个";
    isDirected ? cout << "有向、" : cout << "无向、";
    isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
    graph.createGraph();
    cout << "打印邻接矩阵" << endl;
    graph.printAdjacentMatrix();
    cout << endl;
    int tail, head, weight;
    cout << "修改指定边的权值" << endl;
    if (isWeighted)  //针对有权图
    {
        cout << "输入边的起点、终点和权值 ";
        cin >> tail >> head >> weight;
        graph.setEdgeWeight(tail, head, weight);
    }
    else  //针对无权图
    {
        cout << "输入边的起点、终点 ";
        cin >> tail >> head;
        graph.setEdgeWeight(tail, head, 1);
    }
    cout << "修改成功！" << endl;
    cout << "打印邻接矩阵" << endl;
    graph.printAdjacentMatrix();
    system("pause");
    return 0;
}

4.2 邻接表

#ifndef A_H_INCLUDED
#define A_H_INCLUDED
#include<iostream>
#include<iomanip>
using namespace std;
//最大权值
#define MAXWEIGHT 100
////////////////////////////////////////////
//边节点
typedef struct edgenode_tag
{
    int adjvex;  //邻接点
    int weight;  //边的权值
    struct edgenode_tag *next;
}EdgeNode;
//顶点节点
typedef struct vertex_tag
{
    int vertex;   //顶点
    EdgeNode *next;
}Vertex;
class Graph
{
private:
    //是否带权
    bool isWeighted;
    //是否有向
    bool isDirected;
    //顶点数
    int numV;
    //边数
    int numE;
    //邻接表
    Vertex *adjList;
public:
    /*
    构造方法
    numV是顶点数，isWeighted是否带权值，isDirected是否有方向
    */
    Graph(int numV, bool isWeighted = false, bool isDirected = false);
    //建图
    void createGraph();
    //析构方法
    ~Graph();
    //获取顶点数
    int getVerNums()
    {return numV;}
    //获取边数
    int getEdgeNums()
    {return numE;}
    //插入边
    void insertEdge(int tail, int head, int weight = 1);
    void insertedge(int tail, int head, int weight);
    //设置指定边的权值
    void setEdgeWeight(int tail, int head, int weight);
    //打印邻接表
    void printAdjacentList();
    //检查输入
    bool check(int tail, int head, int weight = 1);
};
    /*
    构造方法
    numV是顶点数，isWeighted是否带权值，isDirected是否有方向
    */
    Graph::Graph(int numV, bool isWeighted, bool isDirected)
    {
        while (numV <= 0)
        {
            cout << "输入的顶点数不正确！，重新输入 ";
            cin >> numV;
        }
        this->numV = numV;
        this->isWeighted = isWeighted;
        this->isDirected = isDirected;
        //边数初始化为0
        numE = 0;
        adjList = new Vertex[numV];  //指针数组
        for (int i = 0; i < numV; i++)
        {
            adjList[i].vertex = i;
            adjList[i].next = NULL;
        }
    }
    //建图
    void Graph::createGraph()
    {
        //用一个新的变量表示边数，numE的修改则留到insertedge()中
        int numEdge = 0;
        cout << "输入边数 ";
        while (cin >> numEdge && numEdge < 0)
            cout << "输入有误！，重新输入 ";

        int i, j, w;
        if (!isWeighted)  //无权图
        {
            cout << "输入每条边的起点和终点：\n";
            for (int k = 0; k < numEdge; k++)
            {
                cin >> i >> j;
                while (!check(i, j))
                {
                    cout << "输入的边不对！重新输入\n";
                    cin >> i >> j;
                }
                insertEdge(i, j);
            }
        }
        else  //有权图
        {
            cout << "输入每条边的起点、终点和权值：\n";
            for (int k = 0; k < numEdge; k++)
            {
                cin >> i >> j >> w;
                while (!check(i, j, w))
                {
                    cout << "输入的边不对！重新输入\n";
                    cin >> i >> j >> w;
                }
                insertEdge(i, j, w);
            }
        }
    }
    //析构方法
    Graph::~Graph()
    {
        int i;
        EdgeNode *p, *q;
        for (i = 0; i < numV; i++)
        {
            if (adjList[i].next)
            {
                p = adjList[i].next;
                while (p)
                {
                    q = p->next;
                    delete p;
                    p = q;
                }
            }
        }
        delete[]adjList;
    }
    //设置指定边的权值
    void Graph::setEdgeWeight(int tail, int head, int weight)
    {
        if (!isWeighted)  //无权图
        {
            while (!check(tail, head))
            {
                cout << "输入的边不对！重新输入\n";
                cin >> tail >> head;
            }
            insertEdge(tail, head);
        }
        else  //有权图
        {
            while (!check(tail, head, weight))
            {
                cout << "输入的边不对！重新输入\n";
                cin >> tail >> head >> weight;
            }
            insertEdge(tail, head, weight);
        }
    }
    //插入边
    void Graph::insertEdge(int vertex, int adjvex, int weight)
    {
        insertedge(vertex, adjvex, weight);
        if (!isDirected)  //无向图
            insertedge(adjvex, vertex, weight);
    }
    void Graph::insertedge(int vertex, int adjvex, int weight)
    {
        EdgeNode *p, *q, *r;
        p = q = r = NULL;
        if (adjList[vertex].next)   //非第一个节点
        {
            p = adjList[vertex].next;
            //移动p到合适位置
            while (p && (p->adjvex < adjvex))
            {
                q = p;
                p = p->next;
            }
            if (p && (p->adjvex == adjvex))  //修改已有边权值
                p->weight = weight;
            else
            {
                r = new EdgeNode;
                r->adjvex = adjvex;
                r->weight = weight;
                r->next = p;
                //当加入的新节点位于表的第一个位置
                if (adjList[vertex].next == p)
                    adjList[vertex].next = r;
                else
                    q->next = r;
                numE++;
            }
        }
        else
        {
            p = new EdgeNode;
            p->adjvex = adjvex;
            p->weight = weight;
            p->next = NULL;
            adjList[vertex].next = p;
            numE++;
        }
    }
    //输入检查
    bool Graph::check(int tail, int head, int weight)
    {
        if (tail >= 0 && tail < numV && head >= 0 && head < numV
            && weight > 0 && weight <= MAXWEIGHT)
            return true;
        else
            return false;
    }
    //打印邻接表
    void Graph::printAdjacentList()
    {
        int i;
        EdgeNode *edge = NULL;
        for (i = 0; i < numV; i++)
        {
            edge = adjList[i].next;
            if (edge) //为什么加一个if判断？跟后面的换行有关。若某顶点无邻接点(无边)，则会空出一行
            {
                while (edge)
                {
                    cout << "w(" << i << "," << edge->adjvex << ")=" << edge->weight << "  ";
                    edge = edge->next;
                }
                cout << endl;
            }
        }
    }
////////////////////////////////////////////
#endif // A_H_INCLUDED

#include <iostream>
#include "a.h"
#include <stdlib.h>
using namespace std;

int main(void)
{
        cout << "******使用邻接表实现图结构***by David***" << endl;
        bool isDirected, isWeighted;
        int numV;
        cout << "建图" << endl;
        cout << "输入顶点数 ";
        cin >> numV;
        cout << "边是否带权值，0(不带) or 1(带) ";
        cin >> isWeighted;
        cout << "是否是有向图，0(无向) or 1(有向) ";
        cin >> isDirected;
        Graph graph(numV, isWeighted, isDirected);
        cout << "这是一个";
        isDirected ? cout << "有向、" : cout << "无向、";
        isWeighted ? cout << "有权图" << endl : cout << "无权图" << endl;
        graph.createGraph();
        cout << "打印邻接表" << endl;
        graph.printAdjacentList();
        cout << endl;
        int tail, head, weight;
        cout << "修改指定边的权值" << endl;
        if (isWeighted)  //针对有权图
        {
            cout << "输入边的起点、终点和权值 ";
            cin >> tail >> head >> weight;
            graph.setEdgeWeight(tail, head, weight);
        }
        else  //针对无权图
        {
            cout << "输入边的起点、终点 ";
            cin >> tail >> head;
            graph.setEdgeWeight(tail, head, 1);
        }
        cout << "修改成功！" << endl;
        cout << "打印邻接矩阵" << endl;
        graph.printAdjacentList();
        system("pause");
        return 0;
}

References：
[1] http://blog.csdn.net/zhangxiangdavaid/article/details/38321327
[2] http://blog.csdn.net/zhangxiangdavaid/article/details/38321327