数据结构与算法之“图”

　　其实所有的数据结构都是“图”。图其实就是一系列的顶点和边的集合。如果边有指向性就叫做有向图，否则就是无向图，边也可以有权值。任意两点间都有路径连接的图叫做连通图，顶点连接的边数叫做这个顶点的度。

　　没有圈的连通图就是所谓的树，没有圈的非连通图就是森林。

1、图的表示

　　(1)邻接矩阵

　　使用|V|*|V|的二维数组来表示：graph[V][V]。graph[i][j]表示顶点i和顶点j的关系，在无权图中，graph[i][j]=1表示i,j之间有边，=0表示无边。无向图中，这是一个堆成矩阵；若是带权图，则graph[i][j]表示顶点i到顶点j的边的权值，无边时graph[i][j]=INF。

　　用邻接矩阵可以在o(1)时间内判断两点间是否有边存在，可是代价是花费o(|V|²)的空间。在无向图中由于是对称矩阵，至少浪费了一般的空间；当一个图的边很少时，空间利用率更低。

　　(2)邻接表

　　每个顶点都有一个邻接表（包含邻接于该顶点的所有顶点）。邻接表只需要占用o(|V|+|E|)的空间，极大地提高了空间的利用率。邻接表也有两种表示方式，用链表来表示，则为邻接链表；用数组表示，则为邻接数组。无论是邻接链表还是邻接数组，它们的空间复杂度都渐近相等，但在图的很多算法中，邻接数组的用时比邻接矩阵要少。

　　这里采用的是邻接表的表示方法：

vector<int> G[MAX_V];//MAX_V为顶点数

　　其中，G[i]表示顶点i的邻接表。　　

　　判断边(i,j)是否存在于图G中：

bool existsEdge(int i,int j){
    vector<int>::iterator it;
    for(it=G[i].begin(); it!=G[i].end(); it++)
        if(j == *it)
            return true;
    return false;
}

　　向G中插入边(i,j)：

void insertEdge(int i,int j){
    if(existsEdge(i,j))
        return ;
    G[i].push_back(j);
    G[j].push_back(i);
}

　　从G中删除边(i,j)：

void eraseEdge(int i,int j){
    for(it=G[i].begin(); it!=G[i].end(); it++)
        if(j == *it)
            G[i].erase(it);
    for(it=G[j].begin(); it!=G[j].end(); it++)
        if(i == *it)
            G[j].erase(it);
}

　　顶点i的度：

int degree(int i){
    return G[i].size();
}

2、图的遍历

　　其中，flag数组用来记录已经搜索过的顶点。这里的G[MAX_V]为无向图，通过遍历打印出所有的边。

　　(1)深度优先遍历（DFS）

　　从一个顶点v开始，选择一个邻接于v并且未到达的顶点u，如果u存在,则从u开始新的DFS，否则，u存在，结束搜索返回。

void dfs(int v){
    static int flag[MAX_V] = {0};
    flag[v] = 1;
    for(int i=0; i<G[v].size(); i++){
        if(0 == flag[G[v][i]]){
            dfs(G[v][i]);
            printf("%d <--> %d
",v,G[v][i]);
        }
    }
}

　　(2)广度优先遍历（BFS）

　　其实BFS就跟树的层序遍历一样，从一个顶点开始，访问它的所有邻接顶点，并把访问过的邻接顶点放入队列里，每次访问完所有的邻接顶点后，就从队列里取出一个顶点，然后，继续前面操作，直到队列里的元素个数为0。

void bfs(int v){
    queue<int> que;
    bool flag[MAX_V];
    fill(flag,flag+MAX_V,false);
    que.push(v);
    flag[v] = true;
    while(!que.empty()){
        int vi = que.front();
        que.pop();
        vector<int> it;
        for(it=G[vi].begin(); it!=G[vi].end(); it++){
            if(!flag[*it]){
                printf("%d <--> %d
",vi,*it);
                que.push(*it);
                flag[*it] = true;
            }
        }
    }
}

　　图作为最高级的一种数据结构，所有适用于图的算法，都可以适用于树，线性表。DFS和BFS是图中最常用的两个算法，很多其他图的算法包括最小生成树，最短路径算法，都是用的DFS和BFS的思想。

　　代码详见：https://github.com/whc2uestc/DataStructure-Algorithm/tree/master/graph