图——存储及遍历

图的定义

定义：图G是由顶点集V和边集E组成，记为G=(V, E),其中V(G)表示图G的顶点的非空有限集，E(G)表示图中的边的集合。顶点的个数称为图的阶。

基本概念：

有向图
无向图
简单图：如果图满如下条件则图称为简单图：（1）不存在重复边；（2）不存在顶点到自身的边；则称图为简单图。
多重图：若图G中某两个节点之间的边数对于一条，又允许顶点通过同一条边和自己相关联，则称图G为多重图。
完全图（也称简单完全图）：无向图中如果任意两个顶点之间都有一条边相关联，则称图为无向完全图。在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。
子图
连通，连通图和连通分量：在无向图中，如果顶点v和w之间有路径存在，则称v和w是连通的，若图G中任意两个顶点都是连通的，则称图G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量，如果图中有n个顶点，并且有小于n-1条边，则此图必是非连通图。
强连通图和强连通分量：在有向图中如果从顶点v到顶点w和从顶点w到顶点v之间都有路径，则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。
生成树，生成森林：生成树是包含图中所有顶点的一个极小连通子图，如果图中有n个顶点，则它的生成树含有n-1条边。
顶点的度，入度和出度：在无向图中，顶点的度等于边数的二倍；在有向图中度分为入度和出度，有向图中所有顶点的入度和出度之和都等于边数。
边的权和网：边上带有权值的图称为带权图，也称为网。
稠密图，稀疏图：一般当图G满足：|E| < |V|log(|V|)时，将图看成稀疏图。
路径，路径长度和回路：第一个顶点和最后一个顶点相同的路径称为回路或者环。
简单路径和简单回路：在路径序列中，顶点不重复出现的路径称为简单路径，除第一个顶点和最后一个顶点之外，其余顶点不重复的路径成为简单回路。
距离
有向树：有一个顶点入度为0，其余顶点入度为1的树称为有向树。

图的存储及基本操作

图的存储

邻接矩阵法

用一个一位数组存储图中顶点的信息，用一个二维数组存储图中边的信息，存储顶点之间邻接关系的二维数组称为邻接矩阵。

图的邻接矩阵的数据结构定义如下：

#define MaxVertexNum 100          //顶点的最大数目
typedef char VertexType;          //顶点的数据类型
typedef int EdgeType;             //带权图上边的权值的数据类型
typedef struct {
    VertexType Vex[MaxVertexNum]  //顶点表
    EdgeType Edge[MaxVertexNum][MaxVertexNum]  //边表
    int vexnum, edgenum;          //当前顶点数和边数
}MGraph;

稠密图适合邻接矩阵法。

邻接表法

对图中的每一个节点建立一个单链表。
顶点表节点由节点域(data)和指向第一条邻接边的指针firstarc构成，边表由邻接节点域adjvex和指向下一条邻接边的指针域nextarc构成。

图的邻接表的数据结构定义如下：

#define MaxVertexNum 100
typedef struct ArcNode {         //  边表节点
    int adjvex;                  //  该弧指向的节点的顶点的位置
    struct ArcNode* nextarc;        //  指向下一条弧的指针
} ArcNode;

typedef struct VNode {           //顶点表节点。
    int data;
    struct VNode* firstarc;
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vnode;                 //  邻接表
    int vernum, arcnum;
} ALGraph;

十字链表
在十字链表中很容易找到vi为结尾的弧，和以vi为头的弧。
邻接多重表

图的基本操作

判断图G是否存在无向边<v, w>或有向边(v, w);
列出图G中与x邻接的边；
在图G中插入顶点x；
在图G中删除顶点x；
如果无向边<v, w>或有向边(v, w)不存在则插入；
如果无向边<v, w>或有向边(v, w)存在，则删除此边；
求图G中顶点x的第一个邻接点；
获取图G中无向边<v, w>或有向边(v, w)对应的权值；
设置图G中无向边<v, w>或有向边(v, w)的权值。

图的遍历

广度优先搜索BFS

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

1. 伪代码表示如下所示：

bool visited[MAX_VERTEX_NUM];
void BFSTraverse(Graph G) {
    for(int i = 0; i < G.vexnum, i++)
        visited[i] = false;

    for(int i = 0; i < G.vexnum, i++)
        if(!visited[i])
            BFS(G, i);
}

void BFS(Graph G, int v) {
    //  从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
    visit(v);
    visited[v] = true;
    InitQueue(Q);
    EnQueue(Q, v);
    while(!isEmpty(Q)) {
        DeQueue(Q, u);
        for(int w = FirstNeighbor(G, u); w >= 0; 
            w = NextNeighbor(G, u, w)) {
                //  w = NextNeighbor(G, u, w)这个函数的意思
                //  是返回除w以外的顶点u的下一个邻接顶点
            if(!visited[w]) {
                visit(w);
                visited[w] = true;
                EnQueue(Q, w);
            }
        }
    }
}

2. 算法性能分析

（1）如果图的存储方式是邻接矩阵存储的话，那么在广度优先遍历的时候每个顶点都需要搜索一次（入队一次），故而时间复杂度是O(|V|)，在搜索任意一个定点的邻接顶点的时候每一条边都会至少搜索一次，所以时间复杂度为O(|E|)，算法总的时间复杂度为O(|V|+|E|)；
（2）如果图的存储方式是矩阵存储的话，查找每个顶点需要O(|V|)的是时间复杂度，所以算法的总的时间复杂度是O(|V|^2).

3. BFS算法求解单源最短路径问题

使用BFS，可以求解一个非带权图的单源最短路径。
伪代码表示如下所示：

void BFS(Graph G, int u) {
     //  从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
     //  d[i]表示从u到i的最短路径的长度。
     for (int i = 0; i < G.vexnum, i++)
         d[i] = MAX_INT;
     visited[u] = true;
     d[u] = 0;
     InitQueue(Q);
     EnQueue(Q, u);
     while(!isEmpty(Q)) {
         DeQueue(Q, u);
         for(int w = FirstNeighbor(G, u); w >= 0; 
             w = NextNeighbor(G, u, w)) {
                 //  w = NextNeighbor(G, u, w)这个函数的意思
                 //  是返回除w以外的顶点u的下一个邻接顶点
             if(!visited[w]) {
                 d[w] = d[u] + 1;
                 visited[w] = true;
                 EnQueue(Q, w);
             }
         }
     }
 }

4. 广度优先生成树
在广度优先遍历的过程中，可以得到一棵遍历树，称为广度优先遍历树，树的邻接矩阵的存储是唯一的，所以邻接矩阵存储方式下得到的优先树也是唯一的，树的邻接矩阵存储不是唯一的，所以广度优先树也是不唯一的。

深度优先搜索DFS

深度优先搜索基本思想：首先访问图中的某一个顶点u，然后访问与u邻接且未被访问的任一顶点v，在访问与v邻接的任一未被访问的顶点w….依次下去直到不能再往下走了，然后返回到最近未被访问的顶点，若它还有邻接顶点未被访问过，则从改点开始继续上述的搜索过程，直到图中所有顶点都被访问过为止。
1. 算法的伪代码表示如下所示：

bool visited[MAX_VERTEX_NUM];
void DFSTraverse(Graph G) {
    for(int i = 0; i < G.vexnum, i++)
        visited[i] = false;
    for(int i = 0; i < G.vexnum, i++)
        if(!visited[i])
            DFS(G, i);
}
void DFS(Graph G, int u) {
    //  采用递归的思路实现广度优先搜索。
    visit(u);
    visited[u] = true;
    for(int w = FirstNeighbor(G, u); w >= 0; 
                w = NextNeighbor(G, u, w))
        if(!visited[w])
            DFS(G, w);
}

2. 算法性能分析

这个算法采用递归的思路，需要借助递归工作栈，所以它的空间复杂度为O(|V|),邻接矩阵存储时算法时间复杂度为O(|V|^2)，使用邻接矩阵存储时，算法的时间复杂度为O(|V| + |E|)。

3. 深度优先树和生成森林
对连通图DFS产生深度优先生成树，否则产生的将是深度优先生成树林。

图的遍历与连通性

对于无向图，如果无向图是连通的，那么遍历一次就能够访问图中的所有节点，若无向图是非连通的，那么每一次遍历只能遍历一个连通分量的所有顶点；对于有向图来说，如果从顶点开始到图的每一个顶点都有路径，则能够访问到图中的所有顶点，否则不能。

算法演练

写出从图的邻接表表示转换成邻接矩阵表示的算法。

void Convert(ALGraph& G, int arc[M][M]) {
    VNode* p = NULL;
    for(int i = 0; i < M; i++) {
        p = (G -> vnode[i]).firstarc;   //  取出顶点i的第一条边
        while(p) {                      //  遍历链表
            arc[i][p -> adjvex] = 1;
            p = p -> nextarc;
        }
    }
}

设计一个算法，判断一个无向图G是否是一颗树，如果是返回true，否则返回false

//  算法思路：无向连通图的判断条件是无回路的连通图或者有n-1条边的连通图。这里使用有n-1条边的连通图来作为判断条件
bool IsTree(Graph G) {
    bool visited[MAX_VERTES_NUM];
    for(int i = 0; i < G.vernum; i++)
        visited[i] = false;
    int vnum = 0, enum = 0;
    DFS(G, 0, vnum, enum, visited);
    
    if(vnum == G.vernum && enum == (G.vernum - 1))
        return true;
    return false;
}

void DFS(Graph G, int v, int vnum, int enum, bool visited[]) {
    visited[v] = true;
    vnum++;
    int w = FirstNeighbor(G, v);
    while(w != -1) {
        enum++;
        if(!visited[w])
            DFS(G, w, vnum, enum, visited);
        w = NextNeighbor(G, v, w);
    }
}

图G采用邻接表形式存储，请写出图遍历的非递归深度优先搜索算法。
首先看一下图的邻接表形式存储的数据结构：

#define MaxVertexNum 100
typedef struct VNode {           //顶点表节点。
    int data;
    struct VNode* nextarc;
} VNode, AdjList[MaxVertexNum];

typedef struct {
    AdjList vnode;                 //  邻接表
    int vernum, arcnum;
} ALGraph;

算法如下：借助栈来实现回退
bool visited[MAX_VERTEX_NUM];

void NRur_DFS(Graph G, int u) {
InitStack(sta);
for(int i = 0; i < G.vernum; i++)
visited[i] = false;
Push(sta, u);
visited[u] = true;
while(!isEmpty(sta)) {
Pop(sta, p);
visit(p);
for(int w = FirstNeighbor(G, p); w >= 0;
w = NextNeighbor(G, p, w)) {
if(!visited[w]) {
Push(sta, w);
visted[w] = true;
}
}
}
}

1. 分别使用深度优先搜索和广度优先搜索遍历算法，判别以邻接表方式存储的有向图中是否存在由定点u到定点v的路径。   
邻接表形式的图的数据结构如下：
 ```C++
    #define MaxVertexNum 100
    typedef struct VNode {           //顶点表节点。
        int data;
        struct VNode* nextarc;
    } VNode, AdjList[MaxVertexNum];

    typedef struct {
        AdjList vnode;                 //  邻接表
        int vernum, arcnum;
    } ALGraph;

BFS:

bool visited[MaxVertexNum];
void BFSPath(Graph G, int u, int v) {
    for(int i = 0; i < G.vernum; i++)
        visited[i] = false;
    return BFS_Path(G, u, v);
}

bool  BFS_Path(Graph G, int u, int v) {
    visited[u] = true;
    InitQueue(Q);
    EnQueue(Q, u);
    while(!isEmpty(Q)) {
        DeQueue(Q, u);
        for(int w = FirstNeighbor(G, u); w >= 0; 
                w = NextNeighbor(G, u, w)) {
            if(!visited[w]) {
                visited[w] = true;
                EnQueue(Q, u);
                if(w == v)
                    return true;
            }
        }
    }
    return false;
}

DFS:
bool visited[MaxVertexNum];
void DFSPath(Graph G, int u, int v) {
for(int i = 0; i < G.vernum; i++)
visited[i] = false;
return DFS_Path(G, u, v);
}