纸上谈兵: 图 (graph)

作者：Vamei 出处：http://www.cnblogs.com/vamei 欢迎转载，也请保留这段声明。谢谢！

图(graph)是三种比较松散的数据价值形式。它有某些节点(vertice)，在某些节点之间，由边(edge)相连。节点的概念在树中也出现过，亲们通常在节点中储存数据。边表示一两个 节点之间的地处关系。在树中，亲们用边来表示子节点和父节点的归属关系。树是三种特殊的图，但限制性更强某些。

假若的三种数据价值形式是很常见的。比如计算机网络，假若由某些节点(计算机机会路由器)以及节点之间的边(网线)构成的。城市的道路系统，也是由节点(路口)和边(道路)构成的图。地铁系统才能越来越理解为图，地铁站能越来越认为是节点。基于图有某些经典的算法，比如求图中一两个 节点的最短路径，求最小伸展树等。

图的经典研究是柯尼斯堡七桥什么的问题(Seven Bridges of Königsberg)。柯尼斯堡是现今的加里宁格勒，城市含晒 三根河流过，河含晒 一两个 小岛。有七座桥桥连接河的两岸和一两个 小岛。送信员总想知道，有越来越一两个 方式，能不重复的走过7个桥呢？

(某些什么的问题在某些奥数教材中称为"一笔画"什么的问题)

欧拉时代的柯尼斯堡地图

柯尼斯堡的能越来越看作由7个边和一两个 节点构成的一两个 图:

某些什么的问题最终被欧拉巧妙的解决。七桥什么的问题也启发了一门新的数类学科——图论(graph theory)的诞生。欧拉的基本思路是，机会某个节点都不 起点机会终点，越来越连接它的边的数目可不才能为偶数个(从一两个 桥进入，再从假若桥选择离开)。对于柯尼斯堡的七桥，机会一两个 节点都为奇数个桥，而最多越来越有一两个 节点为起点和终点，太少 太少 太少 太少 不机会一次走完。

图的定义

严格的说，图[$G = (V, E)$]是由节点的集合V和边的集合E构成的。一两个 图的所有节点构成一两个 集合[$V$]。一两个 边能越来越表示为[$(v_1, v_2)$]，其中[$v_1, v_2 \in V$]，即一两个 节点。机会[$(v_1, v_2)$]有序，即[$(v_1, v_2)$]与[$(v_2, v_1)$]不同，越来越图是有向的(directed)。有序的边能越来越理解为单行道，越来越沿一两个 方向行进。机会[$(v_1, v_2)$]无序，越来越图是无向的(undirected)。无序的边能越来越理解成双向都能越来越行进的道路。一两个 无序的边能越来越看作连接相同节点的一两个 反向的有序边，太少 太少 太少 太少 无向图能越来越理解为有向图的三种特殊状态。

(七桥什么的问题中的图是无向的。城市中的公交线路能越来越是无向的，比如地处单向环线)

图的一两个 路径(path)是图的一系列节点[$w_1, w_2, ..., w_n$]，且对于[$1 \le i < n $]，有[$ (w_i, w_{i+1}) \in E$]。也假若说，路径是一系列的边连接而成，路径的两端为一两个 节点。路径底下的总数称为路径的长度。乘坐地铁时，亲们会在选择某个路径，来从A站到达B站。假若的路径机会有不止三根，亲们往往会根据路径的长度以及沿线的拥挤状态，来选择三根最佳的路线。机会地处三根长度大于0的路径，该路径的两端为同一节点，越来越认为该图中地处环路(cycle)。很明显，上海的地铁系统中地处环路。

 

找到三根环路

机会从每个节点，到任意一两个 其它的节点，都不 三根路径搞笑的话，越来越图是连通的(connected)。对于一两个 有向图来说，假若的连通称为强连通(strongly connected)。机会一两个 有向图不满足强连通的条件，但将它的所有边都改为双向的，此时的无向图是连通的，越来越认为该有向图是弱连通(weakly connected)。

机会将有火车站的城市认为是节点，铁路是连接城市的边，假若的图机会是不连通的。比如北京和费城，北京有铁路通往上海，费城有铁路通往纽约，但北京和费城之间越来越路径相连。

图的实现

三种简单的实现图的方式是使用二维数组。让数组a的每一行为一两个 节点，该行的不同元素表示该节点与某些节点的连接关系。机会[$(u, v) \in E$]，越来越a[u][v]记为1，过后为0。比如下面的一两个 含晒 一两个 节点的图:

 

能越来越简单表示为

a	1	2	3
1	0	1	1
2	0	0	0
3	0	1	0

某些实现方式所地处的空间为[$O(|V|^2)$]，[$|V|$]为节点总数。所需内存随着节点增加而很慢增多。机会边都不 很密集，越来越太少 太少 太少 太少 数组元素记为0，越来越稀疏的某些数组元素记为1，太少 太少 太少 太少 并都不 很经济。

更经济的实现方式是使用邻接表(adjacency list)，即记录每个节点所有的相邻节点。对于节点m，亲们建立一两个 链表。对于任意节点k，机会有[$(m, k) \in E$]，就将该节点倒入到对应节点m的链表中。邻接表是实现图的标准方式。比如下面的图，

 

能越来越用如下的数据价值形式实现：

 

左侧为一两个 数组，每个数组元素代表一两个 节点，且指向一两个 链表。该链表含晒 晒 该数组元素所有的相邻元素。

总体上看，邻接表能越来越分为两主次。邻接表所地处的总空间为[$O(|V| + |E|)$]。数组主次储存节点信息，地处[$|V|$])的空间，即节点的总数。链表存储边的信息，地处[$|E|$]的空间，即边的总数。在某些冗杂的什么的问题中，定点和边还机会有某些的附加信息，亲们能越来越将什么附加信息储地处相应的节点机会边的位置。

下面为具体的C代码:

/* By Vamei */
#include <stdio.h>
#include <stdlib.h>

#define NUM_V 5

typedef struct node *position;

/* node */
struct node {
    int element;
    position next;
};

/* 
 * operations (stereotype)
 */
void insert_edge(position, int, int);
void print_graph(position graph, int nv);

/* for testing purpose */
void main()
{
    struct node graph[NUM_V];
    int i;

    // initialize the vertices
    for(i=1; i<NUM_V; i++) {
        (graph+i)->element = i;
        (graph+i)->next    = NULL;
    }

    // insert edges
    insert_edge(graph,1,2);
    insert_edge(graph,1,4);
    insert_edge(graph,3,2);
    insert_edge(graph,4,2);
    insert_edge(graph,4,3);

    print_graph(graph,NUM_V);
}

/* print the graph */
void print_graph(position graph, int nv) {
    int i;
    position p;
    for(i=1; i<nv; i++) {
        p = (graph + i)->next;
        printf("From %3d: ", i);
        while(p != NULL) {
            printf("%d->%d; ", i, p->element);
            p = p->next;
        }
        printf("\n");
    }
}

/*
 * insert an edge
 */
void insert_edge(position graph,int from, int to)
{
    position np;
    position nodeAddr;

    np = graph + from;

    nodeAddr = (position) malloc(sizeof(struct node));
    nodeAddr->element = to;
    nodeAddr->next    = np->next;
    np->next = nodeAddr;
}

运行结果:

From   1: 1->4; 1->2;

From   2:

From   3: 3->2;

From   4: 4->3; 4->2;

底下的实现主要基于链表，可参考纸上谈兵: 表 (list) 。

总结

图是三种很简单的数据价值形式。图的组织方式比较松散，自由度比较大，但也造成比较高的算法冗杂度。我将在以前介绍某些图的经典算法。

欢迎继续阅读“纸上谈兵: 算法与数据价值形式”系列