第六章总结-蒲公英云

第六章我们学习到的是图，一种比树还要复杂一点的数据结构。

首先是图的定义：图G有两个集合V和E组成，记为G=（V,E），其中V是顶点的有穷非空集合，E为V中顶点偶对的有穷集合，

这些顶点偶对成为边。V（G）和E（G）通常分为表图G的顶点集合和边集合，E（G）可以为空集。若E（G）为空，则图G

只有顶点而没有边；若边集E（G）为有向边的集合，则称该图有向图；若边集E（G）为无向边的集合，则称该图为无向图。

然后介绍一下比较重要的图的遍历

图的遍历

图的遍历和树的遍历类似，希望从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫图的遍历。

对于图的遍历来说，如何避免因回路陷入死循环，就需要科学地设计遍历方案，通过有两种遍历次序方案：深度优先遍历和广度优先遍历。

1.深度优先遍历

深度优先遍历，也有称为深度优先搜索，简称DFS。其实，就像是一棵树的前序遍历。

它从图中某个结点v出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中的所有顶点都被访问到为止。

邻接矩阵表示图代码：

void DFS_AM (AMGraph G,int v)
{
     //图G为邻接矩阵类型，从第v个顶点出发深度优先搜索遍历图G
   cout<<v; visited[v]=true;//访问第v个顶点，并置访问的标志数组相应的分量值为true
   for(w=0;w<G.vexnum;w++)//依次检查邻接矩阵v所在的行
       if((G.arcs[v][w]!=0)&&(!visited[w])) DFS_AM(G,w);//G.arcs[v][w]表示w是v的邻接点，如果w未访问，则递归调用DFS_AM
}

邻接表表示图代码：

void DFS(GraphList g, int i)
{
    EdgeNode *p;
    visited[i] = TRUE;
    cout<<g->adjList[i].data;   //打印顶点，也可以其他操作
    p = g->adjList[i].firstedge;
    while(p)
    {
        if(!visited[p->adjvex])
        {
            DFS(g, p->adjvex);           //对访问的邻接顶点递归调用
        }
        p = p->next;
    }
}

2. 广度优先遍历

广度优先遍历，又称为广度优先搜索，简称BFS。图的广度优先遍历就类似于树的层序遍历了。

代码如下：

//广度优先遍历
void BFS(AGraph* G,int v) {
    ANode *p;
    queue<int> qu;
    vector<int> flag(G->n);
    int w;
    cout<<v<<" ";
    flag[v]=1;
    qu.push(v);
    while(!qu.empty()) {
        w = qu.front();
        qu.pop();
        p = G->adjlist[w]->firstarc;
        while(p) {
            if(!flag[p->adjvex]) {
                cout<<p->adjvex<<" ";
                flag[p->adjvex] = 1;
                qu.push(p->adjvex);
            }
            p = p->nextarc;
        }
    }
    cout<<endl;
}

然后就是图的应用

1.最小生成树

a.普里姆算法

Prim算法
Prim算法是用来解决最小生成树问题的。
基本思想：对图G（V,E）设置集合S，存放已经被访问的顶点，然后每次从集合V-S中选择与集合S的最短距离最小的一个顶点（记为u），访问并加入集合S。之后，令顶点u为中介点，优化所有从u能到达的顶点v与集合S之间的最短距离。这样的操作执行n次（n为顶点个数），直到集合S已包含所有顶点。

核心代码如下：

void prim(Graph G,int vcount,int father[])
{
    int i,j,k;
    int lowcost[max_vertexes];
int closeset[max_vertexes],used[max_vertexes];
int min;
    for (i=0;i<vcount;i++)
        {
/* 最短距离初始化为其他节点到1号节点的距离 */
        lowcost[i]=G[0][i];
    /* 标记所有节点的依附点皆为默认的1号节点 */
        closeset[i]=0; 
        used[i]=0;
        father[i]=-1; 
        }
    used[0]=1;  /*第一个节点是在U集合里的*/
/* vcount个节点至少需要vcount-1条边构成最小生成树 */
    for (i=1;i<=vcount-1;i++)
        {
        j=0;
    min = infinity;
       /* 找满足条件的最小权值边的节点k */
        for (k=1;k<vcount;k++)
         /* 边权值较小且不在生成树中 */
            if ((!used[k])&&(lowcost[k]<min)) 
          {
              min =  lowcost[k];
              j=k;
           }
        father[j]=closeset[j]; 
        used[j]=1;;//把第j个顶点并入了U中
        for (k=1;k<vcount;k++)
         /* 发现更小的权值 */
            if (!used[k]&&(G[j][k]<lowcost[k]))
                { 
                  lowcost[k]=G[j][k];/*更新最小权值*/
                  closeset[k]=j;;/*记录新的依附点*/
                 }
        }
}

b.kruskal算法

kruskal算法

基本思想：假设连通网N＝（V，{E}）。则令最小生成树的初始状态为只有n个顶点而无边的非连通图T＝（V，{}），图中每个顶点自成一个连通分量。在E中选择最小代价的边，若该边依附的顶点落在T中不同的连通分量中，则将该边加入到T中，否则舍去此边而选择下一条代价最小的边，依次类推，直到T中所有顶点都在同一连通分量上为止。

核心代码：

void MiniSpanTree_Kruskal(MGraph G)
{
    int i, j, n , m;
    int k = 0;
    int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */
    Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */
    /* 此处省略将邻接矩阵G转换为边集数组edges并按权由小到大排列的代码*/
    for (i = 0; i < G.numVertexes; i++)
        parent[i] = 0;
    cout << "打印最小生成树：" << endl;
    for (i = 0; i < G.numEdges; i++)/* 循环每一条边 */
    {
        n = Find(parent, edges[i].begin);
        m = Find(parent, edges[i].end);
        if (n != m)/* 假如n与m不等，说明此边没有与现有的生成树形成环路 */
        {
            parent[n] = m;/* 将此边的结尾顶点放入下标为起点的parent中。 */
            /* 表示此顶点已经在生成树集合中 */
            cout << "(" << edges[i].begin << ", " << edges[i].end << ") "
                 << edges[i].weight << endl;
        }
    }