数据结构 第六章 图

6.1 图的逻辑结构

图是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为： G=(V，E)
其中：G表示一个图，V是图G中顶点的集合，E是图G中顶点之间边的集合。
在线性表中，元素个数可以为零，称为空表；
在树中，结点个数可以为零，称为空树；
在图中，顶点个数不能为零，但可以没有边。

若顶点v_i和v_j之间的边没有方向，则称这条边为无向边，表示为(v_i,v_j)。
如果图的任意两个顶点之间的边都是无向边，则称该图为无向图。
若从顶点v_i到v_j的边有方向，则称这条边为有向边，表示为<v_i,v_j>。
如果图的任意两个顶点之间的边都是有向边，则称该图为有向图。
简单图：在图中，若不存在顶点到其自身的边，且同一条边不重复出现。

数据结构中讨论的都是简单图。

邻接、依附
无向图中，对于任意两个顶点v_i和顶点v_j，若存在边(v_i，v_j)，则称顶点v_i和顶点v_j互为邻接点，同时称边(v_i，v_j)依附于顶点v_i和顶点v_j。
有向图中，对于任意两个顶点v_i和顶点v_j，若存在弧<v_i，v_j>，则称顶点v_i邻接到顶点v_j，顶点v_j邻接自顶点v_i，同时称弧<v_i，v_j>依附于顶点v_i和顶点v_j 。

在线性结构中，数据元素之间仅具有线性关系；
在树结构中，结点之间具有层次关系；
在图结构中，任意两个顶点之间都可能有关系。

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。
有向完全图：在有向图中，如果任意两个顶点之间都存在方向相反的两条弧，则称该图为有向完全图。
含有n个顶点的无向完全图有n×(n-1)/2条边。
含有n个顶点的有向完全图有**n×(n-1)**条边。

稀疏图：称边数很少的图为稀疏图；
稠密图：称边数很多的图为稠密图。

顶点的度：在无向图中，顶点v的度是指依附于该顶点的边数，通常记为TD (v)。
顶点的入度：在有向图中，顶点v的入度是指以该顶点为弧头的弧的数目，记为ID (v)；
顶点的出度：在有向图中，顶点v的出度是指以该顶点为弧尾的弧的数目，记为OD (v)。

在具有n个顶点、e条边的无向图G中，各顶点的度之和与边数之和的关系？
在具有n个顶点、e条边的有向图G中，各顶点的入度之和与各顶点的出度之和的关系？与边数之和的关系？

权：是指对边赋予的有意义的数值量。
网：边上带权的图，也称网图。
路径：在无向图G=(V, E)中，从顶点v_p到顶点v_q之间的路径是一个顶点序列(v_p=v_i0,v_i1,v_i2, …, v_im=v_q)，其中，(v_ij1,v_ij)∈E（1≤j≤m）。若G是有向图，则路径也是有方向的，顶点序列满足<v_ij-1,v_ij>∈E。
回路（环）：第一个顶点和最后一个顶点相同的路径。
简单路径：序列中顶点不重复出现的路径。
简单回路（简单环）：除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路。
子图：若图G=（V，E），G’=（V’，E’），如果V’⊆V 且E’ ⊆ E ，则称图G’是G的子图。
连通图：在无向图中，如果从一个顶点v_i到另一个顶点v_j(i≠j)有路径，则称顶点v_i和v_j是连通的。如果图中任意两个顶点都是连通的，则称该图是连通图。
连通分量：非连通图的极大连通子图称为连通分量。
强连通图：在有向图中，对图中任意一对顶点v_ji和v_j (i≠j)，若从顶点v_i到顶点v_j和从顶点v_j到顶点v_i均有路径，则称该有向图是强连通图。
强连通分量：非强连通图的极大强连通子图。
生成树：n个顶点的连通图G的生成树是包含G中全部顶点的一个极小连通子图。
生成森林：在非连通图中，由每个连通分量都可以得到一棵生成树，这些连通分量的生成树就组成了一个非连通图的生成森林。

• 图的遍历操作

图的遍历是从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。

1. 在图中，如何选取遍历的起始顶点？

解决方案：从编号小的顶点开始 。
在线性表中，数据元素在表中的编号就是元素在序列中的位置，因而其编号是唯一的；
在树中，将结点按层序编号，由于树具有层次性，因而其层序编号也是唯一的；
在图中，任何两个顶点之间都可能存在边，顶点是没有确定的先后次序的，所以，顶点的编号不唯一。
为了定义操作的方便，将图中的顶点按任意顺序排列起来，比如，按顶点的存储顺序。

1. 从某个起点始可能到达不了所有其它顶点，怎么办？

解决方案：多次调用从某顶点出发遍历图的算法。

1. 因图中可能存在回路，某些顶点可能会被重复访问，那么如何避免遍历不会因回路而陷入死循环?

解决方案：附设访问标志数组visited[n] 。

1. 在图中，一个顶点可以和其它多个顶点相连，当这样的顶点访问过后，如何选取下一个要访问的顶点？

解决方案：深度优先遍历和广度优先遍历。

1.深度优先遍历 （DFS：Depth First Search）
⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
2.广度优先遍历 （BFS：Broad First Search ；FIFO: First In First Out）
⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

6.2 图的存储结构及实现

基本思想：
用一个一维数组存储图中顶点的信息
用一个二维数组（称为邻接矩阵）存储图中各顶点之间的邻接关系。
假设图G＝(V，E)有n个顶点，则邻接矩阵是一个n×n的方阵，定义为：
无向图的邻接矩阵
无向图的邻接矩阵的特点：
主对角线为 0 且一定是对称矩阵。
求顶点i的度：
邻接矩阵的第i行（或第i列）非零元素的个数。
判断顶点 i 和 j 之间是否存在边：
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
求顶点 i 的所有邻接点：
将数组中第 i 行元素扫描一遍，若arc[i][j]为1，则顶点 j 为顶点 i 的邻接点。
有向图的邻接矩阵
有向图的邻接矩阵一定不对称？
不一定，例如有向完全图。
求顶点 i 的出度：
邻接矩阵的第 i 行元素之和。
求顶点 i 的入度：
邻接矩阵的第 i 列元素之和。
判断从顶点 i 到顶点 j 是否存在边：
测试邻接矩阵中相应位置的元素arc[i][j]是否为1。
网图的邻接矩阵
网图邻接矩阵可定义为的：
邻接矩阵存储无向图的类

const int MaxSize=10; 
template <class T>
class Mgraph{
   public:
      MGraph(T a[ ], int n, int e );   
       ~MGraph( )
       void DFSTraverse(int v); 
       void BFSTraverse(int v);
        ……
   private:
       T vertex[MaxSize]; 
       int arc[MaxSize][MaxSize]; 
       int vertexNum, arcNum; 
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

• 构造函数MGraph(T a[ ], int n, int e );

1、确定图的顶点个数和边的个数；
2、输入顶点信息存储在一维数组vertex中；
3、初始化邻接矩阵；
4、依次输入每条边存储在邻接矩阵arc中；
4.1 输入边依附的两个顶点的序号i, j；
4.2 将邻接矩阵的第i行第j列的元素值置为1；
4.3 将邻接矩阵的第j行第i列的元素值置为1；

template <class T>
MGraph::MGraph(T a[ ], int n, int e) {
    vertexNum=n; arcNum=e;
    for (i=0; i<vertexNum; i++) 
        vertex[i]=a[i];
    for (i=0; i<vertexNum; i++)    //初始化邻接矩阵
       for (j=0; j<vertexNum; j++)
           arc[i][j]=0;             
    for (k=0; k<arcNum; k++) {
        cin>>i>>j;     //边依附的两个顶点的序号
        arc[i][j]=1;  arc[j][i]=1;  //置有边标志    
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

• 深度优先遍历

⑴ 访问顶点v；
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步，直至图中所有和v有路径相通的顶点都被访问到。
递归定义

int visited[MaxSize];
template <class T>
void MGraph::DFSTraverse(int v)  
{
     cout<<vertex[v]; visited [v]=1;
     for (j=0; j<vertexNum; j++)
         if (arc[v][j]==1 && visited[j]==0)
           DFSTraverse( j );
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9

• 广度优先遍历

⑴ 访问顶点v；
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1，v2，…，vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问。直至图中所有与顶点v有路径相通的顶点都被访问到。

int visited[MaxSize];
template <class T>
void MGraph::BFSTraverse(int v){     
    front=rear=-1;   //假设采用顺序队列且不会发生溢出
   int Q[MaxSize]; cout<<vertex[v]; visited[v]=1;  Q[++rear]=v; 
    while (front!=rear)    {
         v=Q[++front];   
         for (j=0; j<vertexNum; j++)
            if (arc[v][j]==1 && visited[j]==0 ) {
                  cout<<vertex[j]; visited[j]=1; Q[++rear]=j;
            }
      }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13

邻接表
邻接表存储的基本思想：
对于图的每个顶点v_i，将所有邻接于v_i的顶点链成一个单链表，称为顶点v_i的边表（对于有向图则称为出边表）
所有边表的头指针和存储顶点信息的一维数组构成了顶点表。
邻接表有两种结点结构：顶点表结点和边表结点。
vertex：数据域，存放顶点信息。
firstedge：指针域，指向边表中第一个结点。
adjvex：邻接点域，边的终点在顶点表中的下标。
next：指针域，指向边表中的下一个结点。

定义邻接表的结点 :

struct ArcNode
{   
      int adjvex; 
      ArcNode *next;
};
template <class T>
struct VertexNode 
{
      T vertex;
      ArcNode *firstedge;
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11

• 无向图的邻接表

边表中的结点表示：
每个结点对应图中的一条边，
邻接表的空间复杂度为O(n+e)。
求顶点 i 的度：
顶点i的边表中结点的个数。
判断顶点 i 和顶点 j之间是否存在边：
测试顶点 i 的边表中是否存在终点为 j 的结点。

• 有向图的邻接表（出边表）

求顶点 i 的出度：
顶点 i 的出边表中结点的个数。
求顶点 i 的入度：
各顶点的出边表中以顶点 i 为终点的结点个数。
求顶点 i 的所有邻接点：
遍历顶点 i 的边表，该边表中的所有终点都是顶点 i 的邻接点。

• 邻接表存储有向图的类

const int MaxSize=10;    //图的最大顶点数
template <class T>
class ALGraph
{    
   public:
       ALGraph(T a[ ], int n, int e);   
       ~ALGraph;    
       void DFSTraverse(int v);      
       void BFSTraverse(int v);      
   ………
  private:
       VertexNode adjlist[MaxSize];   
       int vertexNum, arcNum;       
};

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14

• 构造函数
• 确定图的顶点个数和边的个数；
• 输入顶点信息，初始化该顶点的边表；
• 依次输入边的信息并存储在边表中；
  3.1 输入边所依附的两个顶点的序号i和j；
  3.2 生成邻接点序号为j的边表结点s；
  3.3 将结点s插入到第i个边表的头部；

template <class T>
ALGraph::ALGraph(T a[ ], int n, int e)
{   
    vertexNum=n; arcNum=e; 
    for (i=0; i<vertexNum; i++)   
    {
       adjlist[i].vertex=a[i];
       adjlist[i].firstedge=NULL;      
    } 
    for (k=0; k<arcNum; k++)   
    {
         cin>>i>>j;    
         s=new ArcNode;s->adjvex=j;              
         s->next=adjlist[i].firstedge;    
         adjlist[i].firstedge=s;
     }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17

• 深度优先遍历

template <class T>
void ALGraph::DFSTraverse(int v){        
    cout<<adjlist[v].vertex;  visited[v]=1;
    p=adjlist[v].firstedge;    
    while (p!=NULL)     {
        j=p->adjvex;
        if (visited[j]==0) DFSTraverse(j);
    p=p->next;           
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10

• 广度优先遍历

template <class T>
void ALGraph::BFSTraverse(int v){
   front=rear=-1;   
   cout<<adjlist[v].vertex;    visited[v]=1;   Q[++rear]=v;   
   while (front!=rear)  {
       v=Q[++front];    p=adjlist[v].firstedge;    
       while (p!=NULL)  {
            j= p->adjvex;
            if (visited[j]==0) {
                cout<<adjlist[j].vertex;  visited[j]=1; Q[++rear]=j;
            }
            p=p->next;
       }
    }
}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

• 十字链表：有向图的链式存储结构
  
• 邻接多重表 ：无向图的存储结构
  
• 边集数组

利用两个一维数组
一个数组存储顶点信息，另外一个数组存储边及其权
其中，数组分量包含三个域：边所依附的两个顶点，权值
各边在数组中的次序可以任意。

Void prime(MGraph G){
    for(int i=1;i<G.vertexNu;i++){
        lowcost[i]=G.arc[0][i];  adjvex[i]=0;
    }
    lowcost[0]=0;
    for(i=1;i<G.vertexNum;i+++){
        k=MinEdge(lowcost,G.vertexNum)
        cout<<K<<adjvex[k]<<lowcost[k];
        lowcost[k]=0;
        for(j=1;j<G.vertexNum;j++)
         if((G.arc[k][j]<lowcost[j]){
              lowcost[j]=G.arc[k][j];
              arcvex[j]=k;
           }
    }
}

const int MAX=1000;
void  Dijkstra(MGraph g, int v){
       for ( i =0; i<g.vexnum ; i++){
     dist[i]=g.arcs[v][i];  
               if ( dist[i]!= MAX) 
                      path [i]=g.vertex[v]+g.vertex[i];
               else
                      path[i]=“”;
       }
       S[0]=g.vertex[v]; 
       num=1;  
While (num<g.vextexNum){
    k=0;
    for(i=0;i<G.vertexNum;i++)
           if((dist[i]<dist[k])   k=i
    cout<<dist[k]<<path[k];
    s[num++]=G.vertex[k];                
    for(i=0;i<G.vertexNum;i++)
             if(dist[k]+g.arc[k][i]<dist[i] {
         dist[i]=dist[k]+g.arc[k][i];
                       path[i]=path[k]+g.vertex[i];
               }
}
}

void Floyd(MGraph G)
{
    for (i=0; i<G.vertexNum; i++)        
       for (j=0; j<G.vertexNum; j++)
       {
          dist[i][j]=G.arc[i][j];
          if (dist[i][j]!=∞) 
               path[i][j]=G.vertex[i]+G.vertex[j];
          else path[i][j]=""; 
       }
     for (k=0; k<G.vertexNum; k++)         
        for (i=0; i<G.vertexNum; i++)       
           for (j=0; j<G.vertexNum; j++)
               if (dist[i][k]+dist[k][j]<dist[i][j]) {
                    dist[i][j]=dist[i][k]+dist[k][j];
                    path[i][j]=path[i][k]+path[k][j];
              }
}