【数据结构与算法】图

表示方法

数组表示方法（邻接矩阵）

用两个数组分别存储数据元素（顶点）和数据元素之间的关系（边或弧）的信息。

无向图的邻接矩阵一定是对称矩阵，而有向图的邻接矩阵则不一定为非对称矩阵。

结构体定义如下：

//-------图的数组（邻接矩阵）存储表示--------
#define INFINITY INF_MAX    //最大值∞
#define MAX_VERTEX_NUM 20     //最大顶点个数
Typedef enum{DG,DN,UDG,UDN} GraphKind;//{有向图、有向网、无向图、无向网}

typedef struct ArcCell { // 弧的定义
    VRType adj;    // VRType是顶点关系类型。对无权图，用1或0表示相邻否；对带权图，则为权值类型。
    InfoType *info;  // 该弧相关信息的指针
} ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct { // 图的定义
    VertexType vexs[MAX_VERTEX_NUM];   // 顶点向量
    AdjMatrix arcs;            // 邻接矩阵                     
    int vexnum, arcnum;   // 图的当前顶点数和弧数      
    GraphKind kind;     // 图的种类标志             
}MGraph;

邻接表

结构体定义如下：

typedef struct ArcNode {//弧的定义
    int adjvex;   // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向同一起点下一条弧的指针
    InfoType *info;   // 该弧相关信息的指针
}ArcNode;

typedef struct VNode {  // 顶点定义
    VertexType  data;   // 顶点信息
    ArcNode  *firstarc; // 指向第一条依附该顶点的弧
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {        //图的结构定义
    AdjList vertices;
    int vexnum, arcnum; //图的当前顶点数和弧数 
    int kind;           // 图的种类标志
} ALGraph;

无向图和有向图的示例如下：

十字链表

弧的结点结构包括：弧头弧尾顶点位置、hlink（指向下一个有相同弧尾的结点）、tlink（指向下一个有相同弧头的结点）、弧的相关信息。

结构体定义如下：

typedef struct ArcBox { // 弧的结构表示
    int tailvex, headvex;  //该弧尾和头顶点的位置 
    struct ArcBox *hlink, *tlink;//含义见上面框内
    InfoType *info;  //该弧相关信息的指针 
} VexNode;

typedef struct VexNode { // 顶点的结构表示
    VertexType data;
    ArcBox *firstin, *firstout;  //分别指向该顶点第一条入弧和出弧 
} VexNode;

typedef struct { // 有向图的定义
    VexNode xlist[MAX_VERTEX_NUM]; // 顶点结点(表头向量) 
    int vexnum, arcnum;            //有向图的当前顶点数和弧数
} OLGraph;

示例如下：

邻接多重表

是无向图的另一种链式存储结构。

结构体定义如下：

typedef struct Ebox {  // 边的结构
    VisitIf mark;      // 访问标记
    int ivex, jvex;     //该边依附的两个顶点的位置
    struct EBox *ilink, *jlink; //分别指向依附这两个顶点的下一条边
    InfoType *info;          // 该边信息指针
} EBox;

typedef struct VexBox {// 顶点
    VertexType  data;
    EBox  *firstedge; // 指向第一条依附该顶点的边
} VexBox;

typedef struct {  // 邻接多重表
    VexBox adjmulist[MAX_VERTEX_NUM];
    int vexnum, edgenum; //无向图的当前顶点数和边数   
} AMLGraph;

示例如下：

拓扑排序

对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。

次序关系指的是：若有弧vi->vj，那么在序列中vi必须排在vj之前。

拓扑排序步骤：

• 从有向图中选取一个没有前驱的顶点，并将其输出
• 从有向图中删除此顶点以及所有以它为尾的弧
• 重复以上两步，直到图为空，或者图不空但找不到无前驱的点为止（图中有环）

简化的算法描述如下：

先找到一个入度为0的结点，然后对其所有邻居入度-1，再搜索下一个入度为0的点。m用来记录已经排过序的点数，最终m和n应该相等。

取入度为零的顶点v;
while (v<>0) {
     printf(v);  ++m;
     w:=FirstAdj(v);
     while (w<>0) {
        inDegree[w]--;
        w:=nextAdj(v,w);
     }
     取下一个入度为零的顶点v;
}
if m<n  printf(“图中有回路”);

为了避免每次搜索入度为0的顶点，可以用一个栈来保存所有入度为0的点。

CountInDegree(G,indegree);//对各顶点求入度
InitStack(S);
for ( i = 0; i < G.vexnum; ++ i)
	if (!indegree[i])  Push(S, i);//入度为零的顶点入栈
count=0;           //对输出顶点计数
while (!EmptyStack(S)) {
    Pop(S, v);  ++ count;  printf(v);
    for (w = FirstAdj(v); w;  w = NextAdj(G,v,w)){
    	-- indegree(w);  // 弧头顶点的入度减一
    	if (!indegree[w])  Push(S, w);  //新产生的入度为零的顶点入栈
    }
}
if (count < G.vexnum) printf(“图中有回路”)

关键路径算法

关键活动指的是：该弧上的权值增加，将使得有向图上的最长路径的长度增加。

路径长度最长的路径叫做关键路径。

迪杰斯特拉算法