图形结构 - 图小结

什么是图

图（Graph）是一种非线性的数据结构，其中的结点可以具有零个或多个相邻元素。

基本概念

顶点（Vertex）：结点
边（Edge）：两个结点之间的连接
度：与顶点相关的边的个数

图的种类

有向图：如果给图的每条边规定一个方向，那么这个图称为有向图
- 出度：从顶点出发的边数
- 入度：指向顶点的边数
无向图：边没有方向的图
有权图：如果图的边有各自的权重，得到的图是有权图。比如地铁线路图，连接两站的边的权重可以是距离，也可以是价格
无权图：如果图的边没有权重，或者权重都一样
连通图：如果图中任意两点都是连通的，那么图被称作是连通图
图的连通性是图的基本性质。
- 无向图中的一个极大连通子图称为其的一个连通分量
- 有向图中，如果对任意两个顶点$V_i$与$V_j$都存在i到j以及j到i的路径，则称为强连通图，对应有强连通分量的概念

图的存储

顺序存储：邻接矩阵
链式存储：邻接表

邻接矩阵

采用一个大小为$V * V$的矩阵$G$

有权图，$G_{ij}$表示为$V_i$ 到$V_j$的权重
无权图，则设为1表示存在边，0表示不存在边

如上图的邻接矩阵为：

	$V_0$	$V_1$	$V_2$	$V_3$	$V_4$
$V_0$	0	1	1	0	1
$V_1$	1	0	0	1	1
$V_2$	1	0	0	1	1
$V_3$	0	1	1	0	0
$V_4$	1	1	1	0	0

设计结点结构

typedef struct GNode{
    int Nv; /* 顶点数 */
    int Ne;  /* 边数 */
    int vers[MAXVEX]; /* 顶点数组 */
    int arc[MAXVEX][MAXVEX]; /* 邻接矩阵，可理解为边表 */
}GNode, *Graph;

构建邻接矩阵

/* 初始化邻接矩阵 */
void initGraph(int Nv, int Ne, Graph G) {
    /* 顶点数超过最大顶点数 */
    if (Nv > MAXVEX) {
        return;
    }
    G->Nv = Nv;
    G->Ne = Ne;
    
    for (int i = 0; i < Nv; i++) {
        G->vers[i] = INF;
        for (int j = 0; j < Nv; j++) {
            G->arc[i][j] = INF;
        }
    }
}

/* 插入顶点表 */
void insertVertex(int i, int v, Graph G) {
    G->vers[i] = v;
}

/* 插入边表 */
void insertEdge(int i, int j, int weight, Graph G) {
    G->arc[i][j] = weight;
    
    // 如果是无向图
    G->arc[j][i] = G->arc[i][j];
}

邻接表

邻接表有2部分组成，分别为：

顶点表：包括元素和边表结构类型的指针
边表：包括元素和本身结构类型的指针
边表为链表结构，这里以头插法为例

在上面的例子中，顶点$V_0$的表示：

设计结点结构

/* 边表 */
typedef struct EdgeNode {
    Element data; /* 权重 */
    struct GNode *next; /* 边指针 */
}EdgeNode;

/* 顶点 */
typedef struct {
    int vertex; /* 顶点信息 */
    EdgeNode * edgeNext; /* 顶点的下一个边 */
}VertexNode, AdjList[MAXVEX];

/* 邻接表 */
typedef struct Graph {
    int Nv; /* 顶点数 */
    int Ne; /* 边数 */
    AdjList adjList; /* 顶点表 */
}Graph;

构建邻接表

/* 初始化 */
void initGraph(int Nv, int Ne, Graph *G) {
    /* 顶点数超过最大顶点数 */
    if (Nv > MAXVEX) {
        return;
    }
    G->Nv = Nv;
    G->Ne = Ne;
    for (int i = 0; i < Nv; i++) {
        G->adjList[i].vertex = 0;
        G->adjList[i].edgeNext = NULL;
    }
}

/* 插入顶点表 */
void insertVertex(int i, int v, Graph *G) {
    G->adjList[i].vertex = v;
}

/* 插入边表 */
void insertEdge(int i, int j, int weight, Graph *G) {
   
    EdgeNode *temp = malloc(sizeof(EdgeNode));
    temp->data = weight;
    temp->adjList_vertex = j;

    temp->next = G->adjList[i].edgeNext;
    G->adjList[i].edgeNext = temp;
        
    /* 无向图 */      
    EdgeNode *temp2 = malloc(sizeof(EdgeNode));
    temp2->data = weight;
    temp2->adjList_vertex = i;
    
    temp2->next = G->adjList[j].edgeNext;
    G->adjList[j].edgeNext = temp2;
}

图的遍历

图的遍历最常用的有两种：深度优先搜索（Depth-first Search, DFS）和广度优先搜索（Breadth-First Search, BFS）

深度优先搜索：类似树的前序遍历，即从一个选定的顶点出发，对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次
广度优先搜索：类似树的层序遍历，即从一个选定的顶点出发，将与其直接相连的点都记录起来，然后依次再对这些点与其直接相连的点进行记录，重复到所有点都被访问

深度优先搜索

举例：上面是一个无向图，当我们从A点出发，进行深度优先搜索时，得到的访问过程为：

A -> B -> E （没有路，回溯到A）
上一个结点->C->F->H->G->D（没有路，最终回溯到A，A也没有未访问的相邻结点，搜索结束）

最终的结果就是：A->B->E->C->F->H->G->D

基本思路

用一个数组存放是否被访问过的标志

初始化数组状态
选择从某一个顶点出发
递归依次访问相邻结点

邻接矩阵 - 深度优先搜索

typedef int Boolean; 
Boolean visit[MAXVEX];
void DFS(Graph G, int i) {
    visit[i] = 1;
    printf("%c  ", G->vers[i]);
    
    for (int j = 0; j < G->Nv; j++) {
        if (G->arc[i][j] == 1 && !visit[j]) {
            DFS(G, j);
        }
    }
}

void DFSTraverse(Graph G) {
    memset(visit, 0, MAXVEX);
    
    for (int i = 0; i < G->Nv; i++) {
        if (!visit[i]) {
            DFS(G, i);
        }
    }
}

邻接表 - 深度优先搜索

typedef int Boolean;
Boolean visited[MAXVEX];
void DFS(Graph G, int i) {

    EdgeNode *node = G.adjList[i].edgeNext;
    
    visited[i] = 1;
    printf("%c  ", G.adjList[i].vertex);
    
    while (node) {
        if (!visited[node->adjList_vertex]) {
            DFS(G, node->adjList_vertex);
        }
        node = node->next;
    }
}

void DFSTravese(Graph G) {
    memset(visited, 0, MAXVEX);
    
    for (int i = 0; i < G.Nv; i++) {
        if (!visited[i]) {
            DFS(G, i);
        }
    }
}

广度优先搜索

广度优先搜索需要借助队列来实现。

同样的，根据上面的无向图，当我们从A点出发，进行广度优先搜索时，得到的过程：

队列入队A
队列出队A，入队B、C、D
队列出队B，入队E
重复出队与入队的过程，直到访问所有结点

基本思路

用一个数组存放是否被访问过的标志

初始化数组状态
选择从某一个顶点出发
循环访问每一个结点

邻接矩阵 - 广度优先搜索

typedef int Boolean;
Boolean visited[MAXVEX];

void BFSTraverse(GNode G) {
    memset(visited, 0, MAXVEX);

    char temp = 0;

    // 借助队列
    SeqQueue Q;
    initQueue(&Q);
    
    for (int i = 0; i < G.Nv; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            printf("%c  ", G.vers[i]);
            
            enQueue(&Q, i);
            while (!isEmptyQueue(Q)) {
                deQueue(&Q, &temp);
                
                for (int k = 0; k < G.Nv; k++) {
                    if (G.arc[i][k] == 1 && !visited[k]) {
                        visited[k] = 1;
                        printf("%c  ", G.vers[k]);
                        enQueue(&Q, k);
                    }
                }
            }
        }
    }
}

邻接表 - 广度优先搜索

typedef int Boolean;
Boolean visited[MAXVEX];

void BFSTravese(Graph G) {
    memset(visited, 0, MAXVEX);
    
    seqQueue Q;
    initQueue(&Q);
    char temp;
    
    EdgeNode * node;
    
    for (int i = 0; i < G.Nv; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            printf("%c  ", G.adjList[i].vertex);
            
            enQueue(&Q, i);
            while (!isEmpty(Q)) {
                deQueue(&Q, temp);
                    
                node = G.adjList[i].edgeNext;
                while (node) {
                    if (!visited[node->adjList_vertex]) {
                        visited[node->adjList_vertex] = 1;
                        printf("%c  ", G.adjList[node->adjList_vertexi].vertex);
                        enQueue(&Q, node->adjList_vertex);
                    }
                    node = node->next;
                }
            }
            
        }
    }
}

广度优先搜索与深度优先搜索对比

深度优先搜索

用栈（stack）来实现的，整个过程可以想象成一个倒立的树形：

把根结点压入栈
每次从栈中弹出一个元素，搜索所有在它下一级的元素，把这些元素压入栈中。并把这个元素标记为它下一级元素的前驱
遍历完所有的元素，结束程序

广度优先搜索

广度优先搜索使用队列（queue）来实现，整个过程也可以看做一个倒立的树形：

把根结点放入队
每次从队列的头部去除一个元素，查看这个元素所有的下一级元素，把它们入队。并把这个元素记为它下一个元素的前驱
遍历完所有的元素，结束程序

完整代码