期末复习之数据结构 第7章 图

ADT Graph {
数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。
数据关系R：R={VR}；VR={<v,w>|v,w∈V 且 P(v,w), 
                   <v,w>表示从v到w的弧，
                   谓词P(v,w)定义了弧<v,w>的意义或信息}
基本操作P：
           CreatGraph ( &G, V,VR);
     初始条件：V是图的顶点集，VR是图中弧的集合。
     操作结果：按V和VR的定义构造图G。
          InsertVex ( &G, v);
     初始条件：图G存在，v和图中顶点有相同特征。
     操作结果：在图G中添加新顶点。
     ………………（参见P156-257）
}

Typedef   struct   ArcCell  {       //弧（边）结点的定义
     VRType     adj;    // VRType可以是int类型    
                  //顶点间关系，无权图取1或0；有权图取权值类型
    InfoType  *info;
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
Typedef  enum {DG,DN,UDG,UDN} GraphKind


 Typedef struct {                             //图的定义
      VertexType   vexs [MAX_VERTEX_NUM ] ; //顶点表
	// VertexType 可以是char类型
      AdjMatrix    arcs;                     //邻接矩阵
      int   Vernum,   arcnum;      //顶点总数，弧（边）总数
      GraphKind      kind;                //图的种类标志
} Mgraph;       

Typedef   struct  VNode{                 //头结点结构-顶点结构
     VertexType   data;              //顶点信息
     ArcNode   * firstarc;         //指向依附该顶点的第一条弧的指针
} VNode, AdjList[  MAX_VERTEX_NUM ];  

Typedef  struct  ArcNode {             //表结点结构-边结构
      int  adjvex;                              //该弧所指向的顶点位置
      struct  ArcNode *nextarcs;   //指向下一条弧的指针
      InfoArc    *info;                     //该弧相关信息的指针
} ArcNode；

Typedef   struct {                 //图结构
     AdjList   vertics ;           //应包含邻接表
      int  vexnum, arcnum;  //应包含顶点总数和弧总数
      int  kind;                       //还应说明图的种类（用标志）
}  ALGraph;             

Boolean  visited [MAX];          // 访问标志数组
Status (*VisitFunc) (int v);        //函数指针变量
Void DFSTraverse( Graph  G, Status (*Visit) (int v))
{         // 对图G做深度优先遍历
   VisitFunc = Visit;    
                  // 使用全局变量VisitFunc,使DFS不必设函数指针参数
    for (v=0; v<G.vexnum; ++v)  visited[v] = FALSE;
                                                            // 访问标志数组初始化
    for (v=0; v<G.vexnum; ++v) //对于连通图从某一个结点出发就可以访问到所有结点，如果是非连通图需要从多个结点出发才能访问所有结点。
         if (!visited[v])   DFS(G,v);  // 对尚未访问的顶点调用DFS
 }

Void DFS (Graph G, int v)
{  // 从第v个顶点出发递归地深度优先遍历图G
   visited [v] = TRUE;   VisitFunc (v); 
                                            //访问第v个顶点
   for ( w = FirstAdjVex (G, v);  w>=0;
           w = NextAdjVex (G, v, w) )
        if (!visited[w])   DFS(G,w);  
                                // 对v的尚未访问的邻接点w递归调用DFS
 }

Status FirstAdjVex(MGraph G,int v)
{	int i;
	for(i=0;i<G.vexnum;i++)
		if(G.arcs[v][i].adj!=INFINITY)
			return i;
	return OVERFLOW;}

Status NextAdjVex(MGraph G,int v,int w)
{	int i;
	for(i=w+1;i<G.vexnum;i++)
		if(G.arcs[v][i].adj!=INFINITY)
			return i;
	return OVERFLOW;}

Void BFSTraverse ( Graph G, Status (* Visit) (int  v) )
{   for ( v=0; v<G.vexnum; ++v )   visited[v] = FALSE ;
    InitQuene(Q);         // 置空的辅助队列Q
    for ( v=0; v<G.vexnum; ++v )
        if (!visited[v] )           // v尚未访问
      {  visited[v] = TRUE; Visit(v);
          EnQuene (Q,v);           // v入队列
          while (!QueneEmpty(Q))
        {  DeQuene (Q, u);            // 队头元素出队并置为u
            for (w=FirstAdjVex(G,u); w>=0; w=NextAdjVex(G,u,w))
                if (! Visited [w] )         // w为u的尚未访问的邻接顶点
             {  Visited [w] = TRUE;  Visit(w);
                 EnQuene (Q,w);
              } //if 
          } //while
       } // if 
}  // BFSTraverse

void MiniSpanTree_P ( MGraph G, VertexType u) 
{  //用普里姆算法从顶点u出发构造网G的最小生成树
   k = LocateVex ( G, u ); 
   for ( j=0; j<G.vexnum; ++j )  // 辅助数组初始化
      if (j!=k)  
          closedge[j] = { u, G.arcs[k][j].adj };  
   closedge[k].lowcost = 0;      // 初始，U＝{u}
   for (i=0; i<G.vexnum; ++i) //选择其余G.vexnum-1个顶点
  {    k = minimum(closedge);  
                  // 求出T的下一个结点：第k顶点
    printf (closedge[k].adjvex, G.vexs[k]); 
                    // 输出生成树上一条边和对应的顶点
  closedge[k].lowcost = 0;    // 第k顶点并入U集
  for (j=0; j<G.vexnum; ++j)  //修改其它顶点的最小边
    if (G.arcs[k][j].adj < closedge[j].lowcost)
           //新顶点并入U后重新选择最小边
      closedge[j] = { G.vexs[k], G.arcs[k][j].adj }; 
  }//for
}// MiniSpanTree

（1）设A[n][n]为有向网的带权邻接矩阵，
    A[i][j]表示弧（vi，vj )的权值，
    S为已找到从源点v0出发的最短路径的终点集合,初始状态为{v0}.
       辅助数组dist[n]为各终点当前找到的最短路径的长度，初始值为： dist[i]＝A[v0 ,i]  
                       //即邻接矩阵中第v0行的权值
（2）选择u，使得
    dist[u]＝min{ dist[w] | w∈V-S }   
      // w是S集之外的顶点,dist[u]是从源点v0到S集外所有顶点
        的弧中最短的一条
    S= S ∪{u}   //将u加入S集
（3）对于所有不在S中的终点w，若
        dist[u]+ A[u,w]< dist[w]      
                       // 即(v0,u)＋(u,w)<(v0,w)
    则修改dist[w]为： dist[w]＝ dist[u]+ A[u,w]
（4）重复操作（2）、（3）共n-1次，由此求得从v0到各终点的最短路径。