数据结构(15)-图结构初探

定义

图(Graph)是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G(V, E)，其中G表示图，V是图G中顶点的集合，E是图G中边的集合。

在线性表中，元素之间的关系是一对一；而在树形结构中，上层元素和下层元素之间的关系则是一对一或者一对多；在图形结构中，元素之间的关系则是任意的，即任意两个元素之间都可能相关。

基本概念

图中的元素我们一般称之为顶点(Vertex)，在图形结构中，是不允许没有顶点的，但是没有要求边集合是非空的。

无向边：若顶点(v1)到顶点(v2)之间的边没有方向，则称该边为无向边(Edge)，用(v1, v2)来表示。如果图中的任意边都是无向边，那么该图称为无向图。在无向图中，如果任意两个顶点之间的边都存在，该该图为无向完全图。含有 $n$ 个顶点的无向完全图有 $\frac {n*(n-1)} {2}$ 条边。
有向边：若顶点(v1)到顶点(v2)之间的边是有方向的，则称该边为有向边，也称为弧(Arc)，用<v1, v2>来表示，v1称为弧尾，v2称为弧头。如果图中的任意边都是有向边，那么该图称为有向图。在有向图中，如果任意两个顶点都存在方向互为相反的两条弧，则该图称为有向完全图。含有 $n$ 个顶点的有向完全图有 ${n*(n-1)}$ 条边。
带权值的图称之为网。
路径的长度是路径上的边或者弧的数目。

图的顶点与边的关系

对于无向图 $G= (V, \{E\})$ ，如果边 $(v1,v2) \in E$ ，则称顶点 $v1$ 、 $v2$ 互为邻接点(Adjacent)，即 $v1$ 和 $v2$ 相邻接。顶点 $v$ 的度(Degree)是和 $v$ 相关联的边的数目，记为 $TD(v)$ 。
对于无向图 $G= (V, \{E\})$ ，如果边 $<v1,v2> \in E$ ，则称顶点 $v1$ 邻接到 $v2$ ，弧 $v1$ 和 $v2$ 相邻接。以顶点 $v$ 为头的弧的数目称为 $v$ 的入度(InDegree)，记为 $ID(v)$ 。以顶点 $v$ 为尾的弧的数目称为 $v$ 的出度(OutDegree)，记为 $OD(v)$ 。顶点 $v$ 的度为 $TD(v) = ID(v) + OD(v)$ 。

连通图

在无向图 $G$ 中，如果从顶点 $v1$ 到顶点 $v2$ 有路径，则称 $v1$ 、 $v2$ 是连通的。如果对于图中任意两个顶点 $(v_i,v_j) \in E$ ， $v_i$ 和 $v_j$ 都是连通的，则称 $G$ 是连通图(Connected Graph)。

一个连通图的生成树是一个极小的连通子图，它含有图中全部的 $n$ 个顶点，但只有足以构成一棵树的 $n-1$ 条边。

图的存储结构

由于图的数据结构比较复杂，单纯的使用顺序结构难以实现其结构，而使用多重链表则会造成很多存储单元的浪费。因此，对于图来说其存储是个难题，不过前辈们已经解决了，现在我们就来学习一下。

邻接矩阵

由于图是由定点和边或者弧组成。合在一起比较困难，所以我们可以分开存储。顶点是无序的，可以用一个一维数组来存储，而边和弧是顶点之间的关系，可以用一个二维数组来存储。所以，图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组来存储顶点信息，一个二维数组来存储边或者弧的信息。
设图 $G$ 有 $n$ 个顶点，则邻接矩阵是一个 $n*n$ 的方阵：

$arc[i][j] = \begin{cases} 1， & \text{$(v_i,v_j) \in E$ 或 $<v_i,v_j> \in E$ } \\ 0， & \text{反之} \end{cases}$

如下例所示：

不带权值邻接矩阵.png

通过这个矩阵我们就可以很清楚的知道图的信息了：

任意两个顶点是否有边或者弧，看arc[i][j]是否大于0
顶点的度就是顶点所在列(或者行)的元素之和
$arc[i][j] == 1$ 就是邻接点

如果加上权值，也就是网，我们就需要修改一下矩阵：
$arc[i][j] = \begin{cases} W_{ij}， & \text{$(v_i,v_j) \in E$ 或 $<v_i,v_j> \in E$ } \\ 0， & \text{i = j} \\ \infty, & \text{反之} \end{cases}$

这里的 $W_{ij}$ 表示 $(v_i,v_j)$ 或者 $<v_i,v_j>$ 的权值。

带权值邻接矩阵.png

代码实现如下：

首先我们要确定一个图里面包括一个顶点数组，一个邻接矩阵，另外还有顶点数，边数或者弧数。

#define MAX_VEX_COUNT 100
#define INT_INFINITY 65535
typedef int TStatus;
// 顶点类型
typedef char VertexType;
// 权值类型
typedef int EdgeType;

typedef struct {
    // 顶点数组
    VertexType verts[MAX_VEX_COUNT];
    // 邻接矩阵
    EdgeType arc[MAX_VEX_COUNT][MAX_VEX_COUNT];
    int vertexNum, edageNum;
} MGraph;

下面我们根据当前结构初始化一个图：

typedef struct {
    // 起点下标 终点下标
    int startIndex, endIndex;
    // 权值
    int weight;
} EdgeInfo;

void initMGraph(MGraph *graph, int vertexNum, int edageNum, VertexType vertexes[], EdgeInfo edges[]) {
    graph->vertexNum = vertexNum;
    graph->edageNum = edageNum;
    
    // 设置顶点数组
    for (int i = 0; i < vertexNum; i++) {
        if (i < MAX_VEX_COUNT) {
            graph->verts[i] = vertexes[i];
        }
    }
    
    // 初始化邻接矩阵默认值
    for (int i = 0; i < vertexNum; i++) {
        for (int j = 0; j < edageNum; j++) {
            if (i == j) {
                graph->arc[i][j] = 0;
            } else {
                graph->arc[i][j] = INT_INFINITY;
            }
        }
    }
    
    // 给邻接矩阵赋值
    for (int i = 0; i < edageNum; i++) {
        graph->arc[edges[i].startIndex][edges[i].endIndex] = edges[i].weight;
    }
}

void printMGraph(MGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("\n");
        for (int j = 0; j < graph.vertexNum; j++) {
            printf("%d ",graph.arc[i][j]);
        }
    }
    printf("\n");
}

void initEdgeInfos(int edgesNum, int starts[], int ends[], int weights[], EdgeInfo edges[]) {
    for (int i = 0; i < edgesNum; i++) {
        EdgeInfo *eInfo = (EdgeInfo *)malloc(sizeof(EdgeInfo));
        eInfo->startIndex = starts[i];
        eInfo->endIndex = ends[i];
        eInfo->weight = weights[i];
        edges[i] = *eInfo;
    }
}

void graphTest() {
    int vertexNumber = 5;
    int edgeNumber = 6;
    int starts[] = {1, 0, 1, 2, 2, 3};
    int ends[] = {0, 4, 2, 0, 3, 4};
    int weights[] = {9, 6, 3, 2, 5, 1};

    EdgeInfo *eInfos = malloc(sizeof(EdgeInfo) * edgeNumber);
    initEdgeInfos(edgeNumber, starts, ends, weights, eInfos);
    
    MGraph graph;
    VertexType vertexes[] = {'0', '1', '2', '3', '4'};
    initMGraph(&graph, vertexNumber, edgeNumber, vertexes, eInfos);
    printMGraph(graph);
}

// 控制台输出
  0   65535 65535 65535   6 
  9     0     3   65535 65535 
  2   65535   0     5   65535 
65535 65535 65535   0     1 
65535 65535 65535 65535   0

可以看出， $m$ 个顶点， $n$ 条边的图创建，时间复杂度为 $O(m+m^2+n)$ 。

邻接表

邻接表(Adjacency List)是指数组和链表相结合的存储方式。即图的顶点还是用数组存储，但是顶点数组中每个元素不只是顶点，而且还需要存储指向第一个邻接点的指针。每个顶点的所有邻接点用单链表存储。

不带权值的邻接表.png

其中边表结点由adjvex和next域组成，adjvex是邻接点域，存储某顶点的领结点在顶点表中下标。

顶点的度即为从顶点边表中结点的个数
判断顶点 $v_i$ 到 $v_j$ 是否存在边，只需要看 $v_j$ 的边表中adjvex是否存在结点 $v_j$ 的下标 $j$ 即可

带权值的图则需要在边表结点中添加一个权值域：

带权值的邻接表.png

代码实现如下：

首先我们来看看，邻接表的数据结构：

#define MAX_VEX_COUNT 100
#define INT_INFINITY 65535
typedef int TStatus;
// 顶点类型
typedef char VertexType;
// 权值类型
typedef int EdgeType;

// 单链表结点结构
typedef struct EdgeNode {
    // 邻接点域 存储邻接点对应的顶点下标
    int adjvex;
    // 权值
    int weight;
    struct EdgeNode *next;
} EdgeNode;

// 顶点数组结点结构
typedef struct VertexNode {
    VertexType data;
    // 指向边表的第一个结点
    EdgeNode *firstEdge;
} VertexNode, AdjList[MAX_VEX_COUNT];

// 图结构
typedef struct {
    // 顶点数组
    AdjList adjList;
    int vertexNum, edgeNum;
} AdjListGraph;

创建图的时候需要区分是无向图还是有向图。

void initAdjListGraph(AdjListGraph *graph, int vertexNum, int edageNum, VertexType vertexes[], EdgeInfo edges[], bool isDirected) {
    graph->vertexNum = vertexNum;
    graph->edgeNum = edageNum;
    
    // 写入顶点数组 先将firstEdge置为NULL
    for (int i = 0; i < vertexNum; i++) {
        graph->adjList[i].data = vertexes[i];
        graph->adjList[i].firstEdge = NULL;
    }
    
    EdgeNode *eNode;
    for (int i = 0; i < edageNum; i++) {
        // 先生成边的结尾结点
        eNode = (EdgeNode *)malloc(sizeof(EdgeNode));
        eNode->adjvex = edges[i].endIndex;
        eNode->weight = edges[i].weight;
        // 头插法
        eNode->next = graph->adjList[edges[i].startIndex].firstEdge;
        graph->adjList[edges[i].startIndex].firstEdge = eNode;
        
        if (!isDirected) {
            // 生成边的起始结点
            eNode = (EdgeNode *)malloc(sizeof(EdgeNode));
            eNode->adjvex = edges[i].startIndex;
            eNode->weight = edges[i].weight;
            eNode->next = graph->adjList[edges[i].endIndex].firstEdge;
            graph->adjList[edges[i].endIndex].firstEdge = eNode;
        }
    }
}

void printAdjListGraph(AdjListGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("\n");
        EdgeNode *eNode = graph.adjList[i].firstEdge;
        while (eNode) {
            printf("%c->%c ", graph.adjList[i].data, graph.adjList[eNode->adjvex].data);
            eNode = eNode->next;
        }
    }
    printf("\n");
}

void graphTest() {
    int vertexNumber = 5;
    int edgeNumber = 6;
    int starts[] = {1, 0, 1, 2, 2, 3};
    int ends[] = {0, 4, 2, 0, 3, 4};
    int weights[] = {9, 6, 3, 2, 5, 1};

    EdgeInfo *eInfos = malloc(sizeof(EdgeInfo) * edgeNumber);
    initEdgeInfos(edgeNumber, starts, ends, weights, eInfos);
    
    AdjListGraph graph;
    VertexType vertexes[] = {'0', '1', '2', '3', '4'};
    initAdjListGraph(&graph, vertexNumber, edgeNumber, vertexes, eInfos, true);
    printAdjListGraph(graph);
}

// 控制台输出：
0->4 
1->2 1->0 
2->3 2->0 
3->4

可以看出， $m$ 个顶点， $n$ 条边的图创建，时间复杂度为 $O(m+n)$ 。

十字链表

对于有向图来说，邻接表是有缺陷的，出度和入度只能处理一个，另一个则需要遍历整个图才能实现。而十字链表(OrthoginalList)则解决了该问题。

十字链表的顶点结构如下：

data	firstin	firstout
顶点元素	入边表头指针	出边表头指针

边表结构如下：

trilvex：弧起点在顶点表的下标
headvex：弧终点在顶点表的下标
headlink：入边表指针域，指向终点相同的下一条边
trilvex：出边表指针域，指向起点相同的下一条边
weight：权值

十字链表的好处就是同时处理了入度和出度的问题，这样既容易找到以 $v_i$ 为尾的弧，也容易找到以 $v_i$ 为头的弧。其时间复杂度和邻接表相同。

邻接多重表

如果我们在无向图中更多的是关注边的相关操作，那么使用邻接表就比较麻烦，我们需要在两个顶点对应的链表上进行操作。这时就需要对边表结点的结构进行改造：

ivex	jvex	ilink	jlink

其中，ivex和jvex是某条边两个顶点在顶点数组中的下标。ilink指向顶点ivex的下一条边，jlink指向顶点jvex的下一条边。这就是邻接多重表结构。可以看出，邻接多重表与邻接表的区别就是在于同一条边在邻接表中用两个结点表示，而在邻接多重表中只有一个结点。

边集数组

边集数组是由两个一位数组组成。一个存储顶点的信息，另一个存储边的信息。边数组的每个元素由一条边的起点下标、终点下标、权值组成。

图的遍历

从图的某一项顶点出发，访遍图中其余顶点，且每一个顶点只被访问一次，这个过程即为图的遍历。由于图的任意一个顶点都可能与其他所有顶点相邻接，所有我们需要把访问过的顶点打个标识，避免多次访问而不自知。比如使用一个数组来标记。

深度优先遍历

也称为深度优先搜索，Depth_First_Search(DFS)。假设我们从某一个顶点开始，访问过的都打上标识，在没有碰到重复顶点的情况下，始终向右手边走。当遇到重复顶点之后，就使用从右手起第二条路、第三条路依次类推。如果遇到的顶点都是走过的，就逐级返回，找没走的地方，直到返回我们出发的顶点。下面我们结合一个无向图例子来看看具体的代码实现。

图深度遍历.png

其实，深度遍历就是一个递归过程，类似于一棵树的前序遍历。

邻接矩阵的深度遍历代码实现如下：

// 标志顶点是否被访问过
bool visited[MAX_VEX_COUNT];

void DFS(MGraph graph, int i) {
    visited[i] = true;
    printf("%c ", graph.verts[i]);
    for (int j = 0; j < graph.vertexNum; j++) {
        if (!visited[j] && graph.arc[i][j] > 0 && graph.arc[i][j] < INT_INFINITY) {
            // 未被访问过 且顶点是相互连接的
            DFS(graph, j);
        }
    }
}

void DFSTraverse(MGraph graph) {
    int i = 0;
    for (i = 0; i < graph.vertexNum; i++) {
        visited[i] = false;
    }
    for (i = 0; i < graph.vertexNum; i++) {
        if (!visited[i]) {
            DFS(graph, i);
        }
    }
}

由于邻接表的顶点数组和邻接矩阵类似，所以DFSTraverse方法都是一样的。不同的是，DFS方法中，我们遍历的是边表的结点。代码实现如下：

void DFS(AdjListGraph graph, int i) {
    visited[i] = true;
    printf("%c ", graph.adjList[i].data);
    
    EdgeNode *eNode = graph.adjList[i].firstEdge;
    while (eNode) {
        if (!visited[eNode->adjvex]) {
            DFS(graph, eNode->adjvex);
        }
        eNode = eNode->next;
    }
}

可以看出， $m$ 个顶点， $n$ 条边的图，邻接矩阵的深度遍历时间复杂度为 $O(m^2)$ ，邻接表的深度遍历时间复杂度为 $O(m+n)$ 。

广度优先遍历

也称为广度优先搜索，Breadth_First_Search(BFS)。如果说图的深度优先遍历类似于树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。

图广度优先遍历.png

所以对图做广度遍历，我们需要构建一个队列作为遍历的辅助。

// 创建一个循环队列，队列的元素中保存顶点在顶点数组中的下标
typedef struct {
    int data[MAX_VEX_COUNT];
    int front, rear;
} SeqQueue;

void initQueue(SeqQueue *sq) {
    sq->front = 0;
    sq->rear = 0;
}

bool isEmptyQueue(SeqQueue sq) {
    return sq.rear == sq.front;
}

// 入队
TStatus enQueue(SeqQueue *sq, int e) {
    if ((sq->rear+1) % MAX_VEX_COUNT == sq->front) {
        return T_ERROR;
    }
    sq->data[sq->rear] = e;
    sq->rear = (sq->rear+1) % MAX_VEX_COUNT;
    return  T_OK;
}

// 出队
TStatus deQueue(SeqQueue *sq, int *e) {
    if (isEmptyQueue(sq)) {
        return T_ERROR;
    }
    *e = sq->data[sq->front];
    sq->front = (sq->front+1) % MAX_VEX_COUNT;
    return T_OK;
}

邻接矩阵广度优先遍历：

void BFS(MGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        visited[i] = false;
    }
    
    SeqQueue sq;
    initQueue(&sq);
    
    // 类似于树层序遍历
    for (int i = 0; i < graph.vertexNum; i++) {
        if (!visited[i]) {
            
            printf("%c ", graph.verts[i]);
            visited[i] = true;
            enQueue(&sq, i);
            
            while (!isEmptyQueue(&sq)) {
                deQueue(&sq, &i);
                for (int j = 0; j < graph.vertexNum; j++) {
                    if (!visited[j] && graph.arc[i][j] > 0 && graph.arc[i][j] < INT_INFINITY) {
                        visited[j] = true;
                        printf("%c ", graph.verts[j]);
                        enQueue(&sq, j);
                    }
                }
            }
        }
        
        printf(" 层数%d ", i);
    }
}

邻接表广度优先遍历：

void BFS(AdjListGraph graph) {
    for (int i = 0; i < graph.vertexNum; i++) {
        visited[i] = false;
    }
        
    SeqQueue sq;
    initQueue(&sq);
    EdgeNode *eNode;
    
    for (int i = 0; i < graph.vertexNum; i++) {
        printf("%c ", graph.adjList[i].data);
        visited[i] = true;
        enQueue(&sq, i);
        
        while (!isEmptyQueue(&sq)) {
            deQueue(&sq, &i);
            eNode = graph.adjList[i].firstEdge;
            while (eNode) {
                if (!visited[eNode->adjvex]) {
                    visited[eNode->adjvex] = true;
                    printf("%c ",graph.adjList[eNode->adjvex].data);
                    enQueue(&sq, eNode->adjvex);
                }
                eNode = eNode->next;
            }
        }
    }
}

从代码可以看出，图的深度优先遍历和广度优先遍历在时间复杂度上是一样的。深度优先遍历适合目标比较明确的场景，而广度则适合不断扩大范围找到最优解的情况。

参考文献：

大话数据结构