图的基本操作

来源：www.rxwcv.cn
图的存储结构主要分两种，一种是邻接矩阵，一种是邻接表。

基本概念

邻接矩阵

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中的边或弧的信息。
下图就是一个无向图的邻接矩阵

从上面可以看出，无向图的边数组是一个对称矩阵。所谓对称矩阵就是n阶矩阵的元满足aij = aji。即从矩阵的左上角到右下角的主对角线为轴，右上角的元和左下角相对应的元全都是相等的。
从这个矩阵中，很容易知道图中的信息。
（1）要判断任意两顶点是否有边无边就很容易了；
（2）要知道某个顶点的度，其实就是这个顶点vi在邻接矩阵中第i行或（第i列）的元素之和；
（3）求顶点vi的所有邻接点就是将矩阵中第i行元素扫描一遍，arc[i][j]为1就是邻接点；

下图是一个有向图的邻接矩阵

顶点数组为vertex[4]={v0,v1,v2,v3}，弧数组arc[4][4]为上图的矩阵。
主对角线上数值依然为0.但因为是有向图，所以此矩阵并不对称，比如从v1到v0有弧，得到arc[1][0]=1，而v0到v1没有弧，因此arc[0][1]=0。有向图论入度和出度，顶点v1的入度为1，正好是第v1列上的数之和。顶点v1的出度为2，即第v1行的各数之和。与无向图同样的办法，判断顶点vi到vj是否存在弧，只需要查找矩阵中arc[i][j]是否为1即可。要想知道vi的所有邻接点就是将矩阵第i行元素扫描一遍，查找arc[i][j]为1的顶点。

邻接表

对于边数相对顶点较少的图，邻接矩阵对存储空间的极大浪费。
邻接表的处理方法是这样的：
（1）图中顶点用一个一维数组存储，当然，顶点也可以用单链表来存储，不过，数组可以较容易的读取顶点的信息，更加方便。 另外，对于顶点数组中，每个数据元素还需要存储指向第一个邻接点的指针，以便于查找该顶点的边信息。
（2）图中每个顶点vi的所有邻接点构成一个线性表，由于邻接点的个数不定，所以，用单链表存储，无向图称为顶点vi的边表，有向图则称为顶点vi作为弧尾的出边表。

下图是一个无向图的邻接表结构

从图中我们知道，顶点表的各个结点由data和firstedge两个域表示，data是数据域，存储顶点的信息。firstedge是指针域，指向边表的第一个结点，即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域，存储某顶点的邻接点在顶点表中的下标，next则存储指向边表中下一个结点的指针，比如v1顶点与v0、v2互为邻接点，则在v1的边表中，adjvex分别为v0的0和v2的2.如果想知道某个顶点的度，就去查找这个顶点的边表中结点的各数。若要判断顶点vi和vj是否存在边，只需要测试顶点vi的边表adjvex中是否存在结点vj的下标就行了。若求顶点的所有邻接点，其实就是对此顶点的边表进行遍历，得到的adjvex域对应的顶点就是邻接点。

两种基本结构

邻接矩阵

#define MAXV 100 //最大顶点个数
#define INF 32767       //INF表示∞
//邻接矩阵
typedef struct {
    int no;//顶点编号
    int info;//顶点其他信息，可存放带权图的权值
}VertexType; //顶点类型

typedef struct {
    int edges[MAXV][MAXV]; //邻接矩阵
    int n, e;//顶点数，边数
    VertexType vexs[MAXV];//顶点表
}MGraph;

邻接表

//边表结点
typedef struct EdgeNode {
    int adjvex;//该弧的终点位置
    struct EdgeNode *nextarc;//指向下一条弧的指针
    int info;//该弧的相关信息，存放权值
}EdgeNode;
//顶点表节点
typedef int Vertex;
typedef struct VextexNode {
    Vertex data;//顶点信息
    int count; //顶点的入度
    bool visited;//表示该节点是否被访问
    EdgeNode *firstEdge;//指向第一条弧
}VextexNode,AdjList[MAXV];
//邻接表
typedef struct {
    AdjList adjList;//邻接表
    int n, e;//图中顶点数和边数
}ALGraph;

用普通数组构造图的邻接矩阵

void arrayToMat(int *arr, int n, MGraph &g) {
    int i, j, count = 0;//count用于统计边数，即矩阵中非0元素的个数
    g.n = n;
    for (i = 0; i < g.n; ++i) {
        for (j = 0; j < g.n; ++j) {
            g.edges[i][j] = arr[i*n + j];//将Arr看作n×n的二维数组，Arr[i*n+j]即是Arr[i][j]，计算存储位置的功夫在此应用
            if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
                ++count;
            }
        }
    }
    g.e = count;
}

用普通数组构造图的邻接表

void arrayToList(int* arr, int n, ALGraph &g) {
    int i, j, count = 0;
    g.n = n;
    EdgeNode *ep;
    //输入顶点信息，将边表置为0
    for (i = 0; i < g.n; ++i) {
        g.adjList[i].data = i;
        g.adjList[i].firstEdge = nullptr;
    }
    //建立边表
    for (i = 0; i < n; ++i) {//检查邻接矩阵中每个元素
        for (j = n - 1; j >= 0; --j) {
            if (arr[i*n + j] != 0) {  //存在一条边，将Arr看作n×n的二维数组，Arr[i*n+j]即是Arr[i][j]
                ep = (EdgeNode*)malloc(sizeof(EdgeNode));//创建一个节点*ep
                ep->adjvex = j;
                ep->info = arr[i*n + j];
                ep->nextarc = g.adjList[i].firstEdge;//采用头插法插入*ep
                g.adjList[i].firstEdge = ep;
                ++count;
            }
        }
    }
    g.e = count;
}

邻接矩阵转邻接表

void MatToList(MGraph g, ALGraph &G) {
    int i, j;
    EdgeNode* ep;
    for (i = 0; i < g.n; ++i) {
        G.adjList[i].firstEdge = nullptr;
    }
    for (i = 0; i < g.n; ++i) {
        for (j = g.n - 1; j >= 0; --j) {
            if (g.edges[i][j] != 0) {
                ep = (EdgeNode*)malloc(sizeof(EdgeNode));
                ep->adjvex = j;
                ep->info = g.edges[i][j];
                ep->nextarc = G.adjList[i].firstEdge;
                G.adjList[i].firstEdge = ep;
            }
        }
    }
    G.n = g.n;
    G.e = g.e;
}

邻接表转邻接矩阵

void ListToMat(ALGraph G, MGraph &g) {
    int i, j;
    EdgeNode *ep;
    g.n = G.n;
    g.e = G.e;
    for (i = 0; i < G.n; ++i) {
        for (j = 0; j < G.n; ++j) {
            g.edges[i][j] = 0;
        }
    }
    for (i = 0; i < G.n; ++i) {
        ep = G.adjList[i].firstEdge;
        while (ep) {
            g.edges[i][ep->adjvex] = ep->info;
            ep = ep->nextarc;
        }
    }
}

输出邻接矩阵

void dispMat(MGraph g) {
    int i, j;
    for (i = 0; i < g.n; ++i) {
        for (j = 0; j < g.n; ++j) {
            if (g.edges[i][j] == INF) {
                cout << "∞ ";
            }
            else {
                cout << g.edges[i][j] << " ";
            }
        }
        cout << endl;
    }
}

输出邻接表

void dispAdj(ALGraph g) {
    int i;
    EdgeNode* ep;
    for (i = 0; i < g.n; ++i) {
        ep = g.adjList[i].firstEdge;
        cout << i << ":";
        while (ep) {
            cout << "->" << ep->adjvex << "/" << ep->info;
            ep = ep->nextarc;
        }
        cout << endl;
    }
}

初始化邻接表节点的访问

初始化为0，表示还没有被访问过

void initVisted(ALGraph &G) {
    for (int i = 0; i < G.n; ++i) {
        G.adjList[i].visited = 0;
    }
}

图的宽度搜索

void BFS(ALGraph G, int start, vector<int>& v) {
    queue<int> q;
    q.push(start);
    G.adjList[start].visited = 1;

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        v.push_back(current);
        EdgeNode *ep;
        ep = (EdgeNode*)malloc(sizeof(EdgeNode));
        ep = G.adjList[current].firstEdge;//ep指向头结点，遍历边表
        while (ep) {
            if (!G.adjList[ep->adjvex].visited) {
                q.push(ep->adjvex);
                G.adjList[ep->adjvex].visited = 1;
            }
            ep = ep->nextarc;
        }
    }
}

图的深度搜索

void DFS(ALGraph G, int start, vector<int>& v) {
    stack<int> s;
    s.push(start);
    G.adjList[start].visited = 1;
    v.push_back(start);
    while (!s.empty()) {
        int current = s.top();
        s.pop();
        EdgeNode *ep;
        ep = (EdgeNode*)malloc(sizeof(EdgeNode));
        ep = G.adjList[current].firstEdge;
        while (ep) {
            if (!G.adjList[ep->adjvex].visited) {
                s.push(current);
                s.push(ep->adjvex);
                G.adjList[ep->adjvex].visited = 1;
                v.push_back(ep->adjvex);
                break;
            }
            ep = ep->nextarc;
        }
    }
}