图的应用--最小生成树、最短路径、拓扑排序、关键路径

1 最小生成树(minimum spanning tree)

(1)基本概念
生成树的概念：
一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。
最小生成树的概念：
带权连通图中代价最小的生成树。

构造最小生成树的算法有许多，基本原则是：
尽可能选取权值最小的边，但不能构成回路；
选取n-1条边构成最小生成树。

(2)Prim算法
假设 G=(V，E)为一网图，其中 V 为网图中所有顶点的集合，E 为网图中所有带权边的集合。设置两个新的集合 U 和 T，其中集合 U 用于存放 G 的最小生成树中的顶点， 集合 T 存放 G 的最小生成树中的边。令集合 U 的初值为 U={v_1}(假设构造最小生成树时， 从顶点 v_1 出发)，集合 T 的初值为 T={}。

①算法思想
从所有u∈U,v∈V-U的顶点中，选取具有最小权值的边(u,v)，将顶点v加入到集合U中，将边(u,v)加入到集合T中，如此不断重复，直到U=V时，最小生成树构建完毕，这时集合T中包含了最小生成树的所有边。
Prim算法的时间复杂度为O(n^2)，与网中的边数无关，因此适用于求边稠密的网的最小生成树。

Prim算法

下图演示了从出发，一步一步把结点k拉到U中。
Prim算法 adjvex 和 lowcost 的变化

②算法实现
使用邻接矩阵(二维数组)表示图，两个顶点之间不存在边的权值为机器内允许的最大值。
为便于算法实现，设置一个一维数组closedge[n]，用来保存(V-U)集合中各顶点到U中顶点具有权值最小的边。
数组元素的定义是:

#define MAX_EDGE 30
struct {
    int adjvex;//边所依附于U中权值最小的顶点
    int lowcost;//该边的权值
} closedge[MAX_EDGE];

closedge[j].adjvex = k，表明边(v_j,v_k)是(V-U)中顶点v_j到U中权值最小的边，顶点v_k是该边所依附的U中的顶点。
closedge[j].lowcost存放该边的权值。

③算法步骤
1)从V中挑出一个顶点v_k加到U中，初始化closedge数组，记录(V-U)中每一个顶点到v_k的权值。
从closedge中选择一条权值不为0最小的边(v_j,v_k)，然后做：
closedege[j].lowcost = 0; //将v_j加入到U中
2)根据新加入的v_j更新closedge中每个元素：遍历剩余的(V-U)所有顶点v_i到顶点v_j的权值是否小于到顶点v_k的权值，如果小于则更新数组
closedge[i].adjvex = j;
closedge[i].lowcost = cost(i,j);
3)重复(1)-(2) ，就得到最小生成树。

在 Prim算法中，图采用邻接矩阵存储，所构造的最小生成树用一维数组存储其n-1条边，每条边的存储结构描述：

typedef struct MSTEdge {
    int vex1, vex2;//边所依附的图中两个顶点
    int weight;//边的权值
} MSTEdge;

算法实现：
贪心算法思想： 局部最优+调整=全局最优

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
#define INFINTY 65535//最大值

typedef enum {
    DG, AG, WDG, WAG  //{有向图，无向图，带权有向图，带权无向图}
} GraphKind;

typedef struct {
    GraphKind kind; /* 图的种类标志 */
    int verxtexNum, arcNum; /* 图的当前顶点数和弧数 */
    char vexs[MAX_VEX]; //顶点集合
    int edges[MAX_VEX][MAX_VEX];//邻接矩阵
} MGraph;/* 图的结构定义 */

typedef struct MSTEdge {
    int vex1, vex2;//边所依附的图中两个顶点
    int weight;//边的权值
} MSTEdge;//边的定义

#define MAX_EDGE 30
struct {
    int adjvex;//到U中权值最小的边所依附U的顶点
    int lowcost;//该边的权值
} closedge[MAX_EDGE];//数组下标代表V-U的顶点的编号

MSTEdge *Prim_MST(MGraph *G, int u) {
    //从第u个顶点开始构造G的最小生成树
    MSTEdge *TE;//存放最小生成树n-1条边的数组指针
    int min,k;
    for (int i = 0; i < G->verxtexNum; i++) {//初始化数组closedge
        closedge[i].adjvex = u;//都依附于顶点u
        closedge[i].lowcost = G->edges[i][u];//到顶点u的权值
    }
    closedge[u].lowcost = 0;//把顶点u拉到集合U中
    TE = (MSTEdge *) malloc((G->verxtexNum - 1) * sizeof(MSTEdge));
    for (int i = 0; i < G->verxtexNum - 1; i++) {//循环n-1次，拉顶点到集合U中
        min = INFINTY;
        for (int j = 0; j < G->verxtexNum; j++) {//遍历closedge数组，找到最小权值的边及顶点
            if (closedge[j].lowcost != 0 && closedge[j].lowcost < min) {
                min = closedge[j].lowcost;
                k = j;
            }
        }
        TE[i].vex1 = closedge[k].adjvex;
        TE[i].vex2 = k;
        TE[i].weight = closedge[k].lowcost;
        closedge[k].lowcost = 0;//把顶点k拉到U中
        for (int i = 0; i < G->verxtexNum; i++) { //修改closedge中各个元素的值
            if (G->edges[i][k] < closedge[i].lowcost) {
                closedge[i].lowcost = G->edges[i][k];
                closedge[i].adjvex = k;
            }
        }
    }
    return TE;
}

(3)Kruskal算法
①算法思想
设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是其最小生成树。
初值U=V,TE={}。
对G中的边按权值大小从小到大依次选取。
选取权值最小的边(v_i,v_j)，若边(v_i,v_j)加入到TE后形成回路，则舍弃改边，否则将该边并入到TE中。
重复上面步骤，直到TE中包含n-1条边。

Kruskal算法

②算法实现
Kruskal算法实现的关键是：当一条边加入到TE的集合后，如何判断是否构成回路？
简单的解决方法是:定义一个一维数组Vset[n]，存放图T中每个顶点所在的连通分量的编号。
初值：Vset[i] = i，表示每个顶点各自组成一个连通分量，连通分量的编号简单地使用顶点在图中的位置(编号)。
当往T中增加一条边(v_i,v_j)时，先检查Vset[i]和Vset[j]的值：
若Vset[i] = Vset[j]：表明v_i和v_j处在同一个连通分量中，加入此边会形成回路；
若Vset[i] ≠ Vset[j]，则加入此边不会形成回路，将此边加入到生成树的边集中。
加入一条新边后，将两个不同的连通分量合并：将一个连通分量的编号换成另一个连通分量的编号。

MSTEdge *Kruskal_MST(MGraph *G){
    MSTEdge *TE;
    int *Vset = (int *) malloc(G->verxtexNum * sizeof(int));//Vset数组
    for (int i = 0; i < G->verxtexNum; i++) {
        Vset[i] = i;//初始化数组Vset[n]
    }
    MSTEdge * edgelist = getEdgeList(G);
    sort(edgelist);//对表权值按从小到大排序
    int j = 0, k = 0, s1, s2;
    while (j < G->arcNum && k < G->verxtexNum - 1) {
        s1 = Vset[edgelist[j].vex1];
        s2 = Vset[edgelist[j].vex2];
        if (s1 != s2) {//若边的两个顶点的连通分量编号不同，边加入到TE中
            TE[k].vex1 = edgelist[j].vex1;
            TE[k].vex2 = edgelist[j].vex2;
            TE[k].weight = edgelist[j].weight;
            k++;
            for (int i = 0; i < G->verxtexNum; i++) {
                if(Vset[i] == s2) {
                    Vset[i] = s1;//把连通分量改为较小的那一个
                }
            }
        }
        j++;
    }
    free(Vset);
    return TE;
}

时间复杂度为O(eloge + n^2)。

2 最短路径

(1)单源点最短路径 Dijkstra算法

对于给定的有向图G=(V,E)及单个源点v_s，求v_s到G的其即余各顶点的最短路径。
Dijkstra提出了一种按路径长度递增次序产生最短路径的算法， Dijkstra算法。

基本思想：
从图中的给定源点到其它各个顶点之间客观上应存在一条最短路径，从这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径长度。
即按长度递增的次序生成各顶点的最短路径，即先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，以此类推，直到求出长度最长的最短路径。

算法思想说明：
设给定源点V_s，S为已求得最短路径的终点集，开始时令S={V_s}。当求得第一条最短路径(V_s,V_i)后，S为{V_s,V_i}。根据以下结论可求下一条最短路径。
设下一条最短路径终点为V_j，则V_j只有以下某一种情况：
1.源点到终点有直接的弧<V_s,V_j>;
2.从 V_s出发到V_j的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是S内某个顶点链接到S外的顶点V_j。
若定义一个数组dist[n]，其每个dist[i]分量保存从V_s出发中间只经过集合S中的顶点而到达V_i的所有路径中长度最小的路径长度值，则下一条最短路径的终点V_j必定是不在S中且值最小的顶点，即：
dist[i] = min{dist[k] | V_k ∈ V-S}

算法设计：
如何存放最短路径长度：
用一维数组dist[j]存储，源点V_s默认，dist[j]表示V_j到V_s的路径长度。
如何存放最短路径：
从源点到其它顶点的最短路径有n-1条，一条最短路径用一个一维数组表示，如从顶点0到5的最短路径为为0、2、3、5，表示为path[5]={0,2,3,5}，所有n-1条最短路径可以用二维数组path[][]存储。

算法步骤
①令S={V_s}，用带权的邻接矩阵表示有向图，对图中每个顶点V_i按以下原则置初值：
dist[i] = 0 , i=s
dist[i] = W_{si} ， i≠s且<V_s,V_i>有路径
dist[i] = ， i≠s且<V_s,V_i>没有路径
②选择一个顶点V_j，使得：
dist[j] = min{dist[k] } V_k ∈ V-S}
，V_j就是求得的下一条最短路径终点，将V_j并入到S中。
③对V-S中的每个顶点V_k，修改dist[k],方法是：
若dist[j] + W_{jk} < dist[k],则修改为：dist[k] = dist[j] + W_{jk}
④ 重复②，③，直到S=V为止。

算法实现：
用带权的邻接矩阵表示有向图，对Prim算法略加改动就成了Dijkstra算法，将Prim算法中求每个顶点V_k的lowcost值用dist[k]代替即可。
设数组path[n]保存从V_s到其它顶点的最短路径。若path[i]=k，表示从V_s到V_i的最短路径中V_i的前一个顶点为V_k。
设数组final[n]，标识一个顶点是否已加入S中。

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
#define INFINITY 25535
typedef enum {
    DG, AG, WDG, WAG  //{有向图，无向图，带权有向图，带权无向图}
} GraphKind;
typedef struct {
    GraphKind kind; /* 图的种类标志 */
    int verxtexNum, arcNum; /* 图的当前顶点数和弧数 */
    char vexs[MAX_VEX]; //顶点集合
    int edges[MAX_VEX][MAX_VEX];//邻接矩阵
} MGraph;/* 图的结构定义 */

typedef enum {
    TRUE, FALSE
} boolean;

boolean final[MAX_VEX];
int path[MAX_VEX], dist[MAX_VEX];

void dijkstraPath(MGraph *G, int v) {  //从图G中的顶点v出发到其余各顶点的最短路径
    int m,min;
    for (int i = 0; i < G->verxtexNum; i++) {//各数组的初始化
        path[i] = v;
        final[i] = FALSE;
        dist[i] = G->edges[v][i];
    }
    //设置S={v}
    dist[v] = 0;
    final[v] = TRUE;
    for (int i = 0; i < G->verxtexNum - 1; i++) {//其余n-1个顶点
        while(final[m] == TRUE) {//找不在S中的顶点
            m++;
        }
        min = INFINITY;
        for (int i = 0; i < G->verxtexNum; i++) {//求出当前最小的dist[i]值
            if (final[i] == FALSE && dist[m] < min) {
                min = dist[m];
                m = i;
            }
        }
        final[m] = TRUE;
        for (int i = 0; i < G->verxtexNum; i++) {//修改dist和path数组的值
            if (final[i] == FALSE && dist[m] + G->edges[m][i] < dist[i]) {
                dist[i] = dist[m] + G->edges[m][i];
                path[i] = m;
            }
        }
    }
}

从 Vo 到其余各顶点的最短路径， 以及运算过程中dist数组的变化状况，如下所示:


时间复杂度O(n^2)。

(2)每一对顶点间的最短路径 Floyd算法

用Dijkstra算法重复对每一个顶点求最短路径，时间复杂度O(n^3)。Floyd提出了另一种算法，形式步骤更为简单，时间复杂度仍是O(n^3)。

算法思想：
设顶点集S(初值为空)，用数组A的每个元素A[i][j]保存从V_i只经过S中的顶点到达V_j的最短路径长度，其思想是：
①初始时令S={}，A[i][j]的赋初值方式是
A[i][j] = 0 , i = j时
A[i][j] = W_{ij} , i ≠ j且V_i,V_j有路径
A[i][j] = , i ≠ j时且V_i,V_j没有路径
②将图中一个顶点且V_k加入到S中，修正A[i][j]的值，因为从V_i只经过S中的顶点V_k到达V_j的路径长度可能比原来不经过V_k的路径更短，修改方法是：
A[i][j] = min{A[i][j],(A[i][k] + A[k][j])}
③重复②，直到G的所有顶点都加入到S中为止。

算法实现：
※定义二维数组Path[n][n]，元素Path[i][j]保存从V_i到V_j的最短路径所经过的顶点。
※若Path[i][j] = k，从V_i到V_j经过V_k，最短路径序列是(V_i,\cdots,V_k,\cdots,V_j)，则路径子序列：(V_i,\cdots,V_k)和(V_k,\cdots,V_j)一定是从V_i到V_k和从V_k到V_j的最短路径。从而可以根据Path[i][k]和Path[k][j]的值再找到该路径上所经过的其它顶点，依此类推。
※初始化为Path[i][j] = -1，表示从V_i到V_j不经过任何S中的顶点。当某个顶点V_k加入到S中后使A[i][j]变小时，令Path[i][j] = k。

下面是 Floyd 算法的一个例子，给出算法过程
初始A中为权值，Path中全为-1，S为{}
先把V_0拉到S中，观察其余结点有没有经过V_0使路径更短。从V_2到V_1经过V_0路径为7，更改A[2][1] = 7，Path[2][1] = 0。
以此类推。

Floyd算法过程

V0到V1 :路径是{ 0, 1 } ，长度是2 ;
V0到V2 :路径是{ 0, 1, 2 } ，长度是6 ;
V1到V0 :路径是{ 1, 2, 0 } ，长度是9 ;
V1到V2 :路径是{ 1, 2 } ，路径长度是4 ;
V2到V0 :路径是{ 2, 0 } ，路径长度是5 ;
V2 到 V1 :路径是{ 2, 0,1}，路径长度是 7 ;

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
typedef struct {
    int verxtexNum, arcNum; /* 图的当前顶点数和弧数 */
    char vexs[MAX_VEX]; //顶点集合
    int edges[MAX_VEX][MAX_VEX];//邻接矩阵
} MGraph;/* 图的结构定义 */

int A[MAX_VEX][MAX_VEX];
int Path[MAX_VEX][MAX_VEX];
void floydPath (MGraph *G) {
    for (int i = 0; i < G->verxtexNum; i++) {//各数组的初始化
        for (int j = 0; j < G->verxtexNum; j++) {
            A[i][j] = G->edges[i][j];
            Path[i][j] = -1;
        }
    }
    for (int i = 0; i < G->verxtexNum; i++) {//如果i到k经过j距离更短的话，更改A和Path
        for (int j = 0; j < G->verxtexNum; j++) {
            for (int k = 0; k < G->verxtexNum; k++) {
                if (A[i][j] + A[j][k] < A[i][k]) {
                    A[i][k] = A[i][j] + A[j][k];
                    Path[i][k] = j;
                }
            }
        }
    }
}

3 拓扑排序

一个工程都可分为若干个称为活动的子工程，各个子工程受到一定的条件约束：
某个子工程必须开始于另一个子工程完成之后；
整个工程有一个起点和一个重点。
对工程的活动加以抽象：图中顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为AOV网(Activity On Vertex Network)。
在AOV网中，若有有向边<i,j>，则i是j的直接前驱，j是i的直接后继。
AOV网不能有环。
检查方法：对有向图的顶点进行拓扑排序，若所有顶点都在其拓扑有序序列中，则无环。

有向图的拓扑排序：
构造AOV网中顶点的一个拓扑线性序列(v_1,v_2,\cdots,v_n)，使得该线性序列不仅保持原来有向图中顶点之间的优先关系，而且对原图中没有优先关系的顶点之间也建立一种人为的优先关系。

算法思想：
①在AOV网中选择一个没有前驱的顶点且输出；
②在AOV网中删除该顶点以及从该顶点出发的所有有向边；
③重复①、②，直到图中全部顶点都已输出(图中无环)或图中不存在无前驱的顶点(图中必有环)。


拓扑排序过程

算法实现说明
采用正邻接链表作为AOV网的存储结构；
设立堆栈，用来暂存入度为0的顶点；
删除顶点以它为尾的弧，弧头顶点的入度减1。

算法实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_VEX 30
typedef enum {
    DG, AG, WDG, WAG
} GraphKind;

typedef struct LinkNode {
    int adjvex;//邻接点在头结点数组中的位置(下标)
    int weight;//权值
    struct LinkNode *nextarc;//指向下一个表结点
} LinkNode;/*表结点类型定义 */

typedef struct VexNode {
    char data; // 顶点信息
    int indegree; //入度
    LinkNode *firstarc; // 指向第一个表结点
} VexNode;/* 顶点结点类型定义 */

typedef struct {
    GraphKind kind;/*图的种类标志 */
    int vexnum;//顶点数
    VexNode AdjList[MAX_VEX];//邻接表
} ALGraph;/* 图的结构定义 */

void countIndegree(ALGraph *G) {
    LinkNode *p;
    for (int i = 0; i < G->vexnum; i++) {//顶点入度初始化
        G->AdjList[i].indegree = 0;
    }
    for (int i = 0; i < G->vexnum; i++) {
        p = G->AdjList[i].firstarc;
        while (p != NULL) {//顶点入度统计
            G->AdjList[p->adjvex].indegree++;
            p = p->nextarc;
        }
    }
}

int topologicSort(ALGraph *G, int topol[]) {
    //顶点的拓扑序列保存在一维数组topol中
    int stack[MAX_VEX];
    int top = -1, count = 0, boolean, no,vexNo;
    LinkNode *p;
    countIndegree(G);
    for (int i = 0; i < G->vexnum; i++) {
        if (G->AdjList[i].indegree == 0) {
            stack[++top] = G->AdjList[i].data;
        }
    }
    do {
        if (top == -1) {
            boolean = 0;
        } else {
            no = stack[top--];//栈顶元素出栈
            topol[count++] = no;//记录顶点序列
            p = G->AdjList[no].firstarc;
            while (p != NULL) {//删除以顶点为尾的弧
                vexNo = p->adjvex;
                G->AdjList[vexNo].indegree--;
                if (G->AdjList[vexNo].indegree == 0) {
                    stack[++top] = vexNo;
                }
                p = p->nextarc;
            }
        }
    } while (boolean == 0);
    if(count < G->vexnum) {
        return -1;
    } else {
        return 1;
    }
}

算法分析：
设 AOV 网有 n 个顶点，e 条边，则算法的主要执行是:
统计各顶点的入度:时间复杂度是 O(n+e) ;
入度为 0 的顶点入栈:时间复杂度是 O(n) ;
拓扑排序过程:顶点入栈和出栈操作执行 n 次，入度减 1 的操作共执行 e 次，时间复杂度是 O(n+e) ;
因此，整个算法的时间复杂度是 O(n+e) 。

4 关键路径

AOE(Activity On Edge)是边表示活动的有向无环图。顶点表示事件(Event)，每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。
由于 AOE 网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为源点到终点的最大路径长度。
具有最大路径长度的路径称为关键路径。关键路径上的活动称为关键活动。关键路径长度是整个工程所需的最短工期。

利用AOE 网进行工程管理时要需解决的主要问题是:
①计算完成整个工程的最短路径。
②确定关键路径，以找出哪些活动是影响工程进度的关键。

设v_0是起点，从v_0到v_i的最长路径长度称为事件v_i的最早发生时间，即是以v_i为尾的所有活动的最早发生时间。若活动a_i是弧<j, k>，持续时间是 dut(<j, k>)
e(i):表示活动a_i的最早开始时间；
l(i):在不影响进度的前提下，表示活动a_i的开始时间；
则l(i) - e(i)表示活动a_i的时间余量，若l(i) - e(i) = 0，表示活动a_i是关键活动。
ve(i):表示事件v_i的最早发生时间，即从起点到顶点v_i的最长路径长度；
vl(i):表示事件v_i的最晚发生时间。
则有以下关系：

最早发生时间 ve(j)的计算:
源点事件的最早发生时间设为 0;除源点外，只有进入顶点 vj 的所有弧所代表的活动全部结束后，事件 vj 才能发生。即只有 vj 的所有前驱事件 vi 的最早发生时间 ve(i)计算出来后，才能计算 ve(j) 。
方法是:对所有事件进行拓扑排序，然后依次按拓扑顺序计算每个事件的最早发生时间。

最晚发生时间 vl(j)的计算:
只有 vj 的所有后继事件 vk 的最晚发生时间 vl(k)计算出来后，才能计算 vl(j) 。
方法是:按拓扑排序的逆顺序，依次计算每个事件的最晚发生时间。


求 AOE 中关键路径和关键活动
算法思想
1 利用拓扑排序求出 AOE 网的一个拓扑序列;
2 从拓扑排序的序列的第一个顶点(源点)开始，按拓扑顺序依次计算每个事件的最早发生时间 ve(i) ;
3 从拓扑排序的序列的最后一个顶点(汇点)开始，按逆拓扑顺序依次计算每个事件的最晚发生时间 vl(i) ;

AOE网

拓 扑 排 序 的 序 列 :( v 0 , v 1 , v 2 , v 3 , v 4 , v 5 , v 6 , v 7 , v 8 )
计算各个事件的 ve(i)和 vl(i)值:



其次计算e和l


根据关键路径的定义，知该 AOE 网的关键路径是: (v0, v2, v4, v7 , v8) 和(v0, v2,v5 , v7,v8) 。
关键路径活动是:<v0, v2>，<v2, v4>，<v2, v5>，<v4, v7>，<v5, v7>，<v5, v8> 。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,530评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,403评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,120评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,770评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,758评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,649评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,021评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,675评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,931评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,751评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,410评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,004评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,969评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,042评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,493评论 2赞 343

推荐阅读更多精彩内容