图

Posted on | In , | |
Words count in article: 7.9k | Reading time ≈ 34

图：

线性表中的元素之间仅有前趋和后继的线性关系；树中的元素有明确的层次关系；图中的任何元素之间都有可能有关系。

图的定义：

图由非空的顶点集合和一个描述顶点之间关系的集合组成。

图的基本术语：

  1. 顶点和边：图中的结点称作顶点，第i个顶点记作vi，两个顶点vi和vj相关联的部分称作vi和vj之间的一条边，第k条边记作ek
  2. 无向图：(vi,vj) 和 (vj,vi) 是同一条边
  3. 有向图：<vi,vj>和 <vj,vi> 是两条不一样的边
  4. 完全图：在n个顶点的无向图中，若任意两个顶点之间有且只有一条边，总的边数为n(n-1)/2，这样的图称作完全图。且在n个顶点的有向图中，如果任意两个顶点之间有且只有方向相反的两条边，总的边数为n(n-1)，这样的图称作有向完全图
  5. 邻接顶点：边连起的两个顶点
  6. 顶点的度：与该顶点相关联的边的条数
  7. 路径：
  8. 权值：
  9. 路径长度：
  10. 简单路径：若一条路径除了开始结点和结束节点之外，其他顶点均不相同，则成为简单路径
  11. 子图：
  12. 连通图和连通分量：任意一对顶点都是连通的，称为连通图。非连通图的最大连通子图称作连通分量
  13. 强连通图：在有向图中，如果一对顶点，来回都存在路径，则为强连通图
  14. 强连通分量：有向图中，最大连通子图称为强连通分量

图的存储结构：

图的信息包括顶点信息和边的信息。
对于一个含有n个顶点的图，由于每一个顶点都可能和其他n-1个顶点由联系，因此，边之间关系的实质是一个n*n的矩阵问题。

邻接矩阵表示法：

用矩阵存储图中顶点的信息，1代表边存在，0代表边不存在

无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称，表示一个具有n个顶点的有向图需要n2个单元来存储，无向图只需存入上（下）三角阵，故只需n(n+1)/2个单元

无向图邻接矩阵的第i行或第i列的非零元素的个数正好是第i个顶点的度。
有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度；第i列非零元素的个数为第i个顶点的入度；第i个顶点的度为第i行和第i列非零元素个数之和。

邻接矩阵表示法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
//邻接矩阵的定义形式：
#include <stdio.h>
#include <malloc.h>
#define maximum 4 //图中结点个数
DataType Graph[maximum][maximum];//定义邻接矩阵
//邻接矩阵生成算法
int main()
{
    int Graph[maximum][maximum];//定义邻接矩阵
    int source, destination;//边的起始点和终点
    int i, j;
    for(i=0; i<maximum; i++)
        for(j=0; j<maximum; j++)
            Graph[i][j] = 0;
    printf("输入边的第一个顶点：");
    scanf("%d",&source);
    printf("\n");
    while(source!=-1)
    {
        if(source>=maximum)
        {
            printf("顶点超出范围，重新输入");
            scanf("%d",&source);
        }
        printf("输入边的第二个顶点：");
        scanf("%d",&destination);
        printf("\n");
        if(destination==source)
        {
            printf("出现循环，重新输入：");
            scanf("%d",&destination);
        }
        if(destination>=maximum)
        {
            printf("顶点超出范围，重新输入");
            scanf("%d",&destination);
        }
        Graph[source][destination] = 1;//有向图
        /*无向图
        Graph[source][destination] = 1
        Graph[destination][source] = 1
        */
        printf("输入边的第一个顶点：");
        scanf("%d",&source);
        printf("\n");
    }
    for(i=0; i<maximum; i++)//输出
        for(j=0; j<maximum; j++)
        {
            printf("%d ",Graph[i][j]);
            if(j == maximum-1)
                printf("\n");
        }
}

邻接表表示法：//一个顶点的next、next->next等都是该顶点指向的点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//邻接链表表示法：
//定义：
typedef struct Node{
    int data;
    struct Node *next;
}GraphNode;
GraphNode Graph[maximum];//顶点数组
int rear = -1;
int front = -1;
        
//构建邻接表：
void CreateAdjacentTable(int v1, int v2)//v1为起点，v2为终点
{
    GraphNode *newnode;
    newnode = (GraphNode*)malloc(sizeof(GraphNode));//分配存储空间
    newnode->data = v2; newnode->next = NULL;
    GraphNode *p;
    p = &Graph[v1];//p指向第v1个顶点
    while(p->next != NULL)//v1顶点已有邻接顶点
        p = p->next;//找到最后一个邻接顶点
    p->next = newnode;//将新顶点连接到最后一个邻接顶点的next域
}

十字链表

对于有向图来说,邻接表是有缺陷的。关心了出度问题,想了解入度就必须要遍历整个图才可以,反之,逆邻接表解决了入度却不了解出度的情况。有没有可能把邻接表与逆邻接表结合起来呢? 答案是肯定的,就是把 它 们整合在一起。这就是我们现在要讲的有向图的 一种存储方法: 十字链表

十字链表的形式可以理解成每一行是一个链表，而每一列又是一个链表

与邻接表不同，十字链表法仅适用于存储有向图和有向网。不仅如此，十字链表法还改善了邻接表计算图中顶点入度的问题。

十字链表存储有向图（网）的方式与邻接表有一些相同，都以图（网）中各顶点为首元节点建立多条链表，同时为了便于管理，还将所有链表的首元节点存储到同一数组（或链表）中。

其中，建立各个链表中用于存储顶点的首元节点结构

1

首元节点中有一个数据域和两个指针域（分别用 firstin 和 firstout 表示）：

  1. firstin 指针用于连接以当前顶点为弧头的其他顶点构成的链表；
  2. firstout 指针用于连接以当前顶点为弧尾的其他顶点构成的链表；
  3. data 用于存储该顶点中的数据；

十字链表实质上就是为每个顶点建立两个链表，分别存储以该顶点为弧头的所有顶点和以该顶点为弧尾的所有顶点。

注意，存储图的十字链表中，各链表中首元节点与其他节点的结构并不相同

1

十字链表中普通节点的存储分为 5 部分内容，它们各自的作用是：

  1. tailvex 用于存储以首元节点为弧尾的顶点位于数组中的位置下标；
  2. headvex 用于存储以首元节点为弧头的顶点位于数组中的位置下标；
  3. hlink 指针：用于链接下一个存储以首元节点为弧头的顶点的节点；
  4. tlink 指针：用于链接下一个存储以首元节点为弧尾的顶点的节点；
  5. info 指针：用于存储与该顶点相关的信息，例如量顶点之间的权值；

1

拿顶点 V1 来说，通过构建好的十字链表得知，以该顶点为弧头的顶点只有存储在数组中第 3 位置的 V4（因此该顶点的入度为 1），而以该顶点为弧尾的顶点有两个，分别为存储数组第 1 位置的 V2 和第 2 位置的 V3（因此该顶点的出度为 2）。

对于各个链表中节点来说，由于表示的都是该顶点的出度或者入度，因此没有先后次序之分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#define  MAX_VERTEX_NUM 20

#define  InfoType int //图中弧包含信息的数据类型

#define  VertexType int

typedef struct ArcBox{
    int tailvex,headvex;//弧尾、弧头对应顶点在数组中的位置下标
    struct ArcBox *hlik,*tlink;//分别指向弧头相同和弧尾相同的下一个弧
    InfoType *info;//存储弧相关信息的指针
}ArcBox;
typedef struct VexNode{
    VertexType data;//顶点的数据域
    ArcBox *firstin,*firstout;//指向以该顶点为弧头和弧尾的链表首个结点
}VexNode;
typedef struct {
    VexNode xlist[MAX_VERTEX_NUM];//存储顶点的一维数组
    int vexnum,arcnum;//记录图的顶点数和弧数
}OLGraph;
int LocateVex(OLGraph * G,VertexType v){
    int i=0;
    //遍历一维数组，找到变量v
    for (; i<G->vexnum; i++) {
        if (G->xlist[i].data==v) {
            break;
        }
    }
    //如果找不到，输出提示语句，返回 -1
    if (i>G->vexnum) {
        printf("no such vertex.\n");
        return -1;
    }
    return i;
}
//构建十字链表函数
void CreateDG(OLGraph *G){
    //输入有向图的顶点数和弧数
    scanf("%d,%d",&(G->vexnum),&(G->arcnum));
    //使用一维数组存储顶点数据，初始化指针域为NULL
    for (int i=0; i<G->vexnum; i++) {
        scanf("%d",&(G->xlist[i].data));
        G->xlist[i].firstin=NULL;
        G->xlist[i].firstout=NULL;
    }
    //构建十字链表
    for (int k=0;k<G->arcnum; k++) {
        int v1,v2;
        scanf("%d,%d",&v1,&v2);
        //确定v1、v2在数组中的位置下标
        int i=LocateVex(G, v1);
        int j=LocateVex(G, v2);
        //建立弧的结点
        ArcBox * p=(ArcBox*)malloc(sizeof(ArcBox));
        p->tailvex=i;
        p->headvex=j;
        //采用头插法插入新的p结点
        p->hlik=G->xlist[j].firstin;
        p->tlink=G->xlist[i].firstout;
        G->xlist[j].firstin=G->xlist[i].firstout=p;
    }
}

邻接多重表

无向图的存储可以使用邻接表，但在实际使用时，如果想对图中某顶点进行实操（修改或删除），由于邻接表中存储该顶点的节点有两个，因此需要操作两个节点。

为了提高在无向图中操作顶点的效率，本节学习一种新的适用于存储无向图的方法——邻接多重表。

注意，邻接多重表仅适用于存储无向图或无向网。

邻接多重表存储无向图的方式，可看作是邻接表和十字链表的结合。同邻接表和十字链表存储图的方法相同，都是独自为图中各顶点建立一张链表，存储各顶点的节点作为各链表的首元节点，同时为了便于管理将各个首元节点存储到一个数组中。各首元节点结构如图

1

各区域及其功能为：

  1. data：存储此顶点的数据；
  2. firstedge：指针域，用于指向同该顶点有直接关联的存储其他顶点的节点。

可以看到，邻接多重表采用与邻接表相同的首元节点结构。但各链表中其他节点的结构与十字链表中相同

1

节点中各区域及功能如下：

  1. mark：标志域，用于标记此节点是否被操作过，例如在对图中顶点做遍历操作时，为了防止多次操作同一节点，mark 域为 0 表示还未被遍历；mark 为 1 表示该节点已被遍历；
  2. ivex 和 jvex：数据域，分别存储图中各边两端的顶点所在数组中的位置下标；
  3. ilink：指针域，指向下一个存储与 ivex 有直接关联顶点的节点；
  4. jlink：指针域，指向下一个存储与 jvex 有直接关联顶点的节点；
  5. info：指针域，用于存储与该顶点有关的其他信息，比如无向网中各边的权；

综合以上信息，如果我们想使用邻接多重表存储图 3a) 中的无向图，则与之对应的邻接多重表如图 3b) 所示：

1

从图中，可直接找到与各顶点有直接关联的其他顶点。比如说，与顶点 V1 有关联的顶点为存储在数组下标 1 处的 V2 和数组下标 3 处的 V4，而与顶点 V2 有关联的顶点有 3 个，分别是 V1、V3 和 V5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define MAX_VERTEX_NUM 20                   //图中顶点的最大个数

#define InfoType int                        //边含有的信息域的数据类型

#define VertexType int                      //图顶点的数据类型

typedef enum {unvisited,visited}VisitIf;    //边标志域
typedef struct EBox{
    VisitIf mark;                           //标志域
    int ivex,jvex;                          //边两边顶点在数组中的位置下标
    struct EBox * ilink,*jlink;             //分别指向与ivex、jvex相关的下一个边
    InfoType *info;                         //边包含的其它的信息域的指针
}EBox;
typedef struct VexBox{
    VertexType data;                        //顶点数据域
    EBox * firstedge;                       //顶点相关的第一条边的指针域
}VexBox;
typedef struct {
    VexBox adjmulist[MAX_VERTEX_NUM];//存储图中顶点的数组
    int vexnum,degenum;//记录途中顶点个数和边个数的变量
}AMLGraph;

图的遍历方式：

深度优先遍历和广度优先遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//深度优先遍历：
void DFS(int *visited, int v)//visited数组存储顶点的遍历情况
{
    GraphNode *p;
    visited[v] = 1;//已访问的顶点，visited[v]设置为1
    printf("%d->",v);
    p = Graph[v].next;//p指向第v个顶点的第一个邻接点
    while(p!=NULL)
    {
        if(visited[p->data]==0)
            DFS(visited, p->data);//递归调用
        p = p->next;
    }
}//采用邻接表结构

广度优先遍历（Breath First Search）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//广度优先遍历：
void BFS(int *visited, int v, int *Queue)
{
    GraphNode *p;
    AddQueue(Queue, v);//初始顶点入队
    visited[v] = 1;//已访问的顶点
    printf("%d->",v);
    while(front!= rear)//队列不为空
    {
        v = Delqueue(Queue);//取出队头元素
        p = Graph[v].next;//邻接顶点
        while(p!=NULL)//有邻接顶点
        {
            if(visited[p->data] == 0)//没有遍历过
            {
                AddQueue(Queue, p->data);//v的邻接顶点入队
                visited[p->data] = 1;
                printf("%d->",p->data);
            }
            p = p->next;//访问下一个邻接顶点
        }
    }
}

最小生成树：

生成树的概念：

如果是一个有n个顶点的连通图，经由这两种遍历DFS、BFS算法遍历的结果，会得到用最好的边来连接所有的顶点，而且不会形成回路，这样的子图是一种树形结构，也就是任意两个顶点之间的路径是唯一的。

这种可连接所有顶点且路径唯一的树形结构称作生成树（spanning tree）或扩展树。

最小生成树：

生成树在实际应用中不仅仅是找出顶点和边，如果一个连通图的边加上权值来表示边的成本、距离等实际问题，则我们希望所产生的生成树的所有边的权值总和最小，具有这样的性质的生成树被称作最小生成树。

Kruskal算法：

该算法每次选取权值最小的边，不用从某顶点出发，然后检查是否形成回路，形成回路的边需要放弃，最终构成最小成本生成树MST。

算法步骤：

  1. 边的权值首先从小到大排序
  2. 从所有的未遍历的边中取出最小权值的边，记录此遍历并检查是否形成回路。形成回路的话，此边不能加入到MST中，重新从未被遍历的边中选择；如果未形成回路，则将此边加入到MST中。判断边数是否达到n-1，达到的话，查找结束，反之重复（2）。

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//Kruskal算法：
struct Edge{
    int vertex1;//边的第一个顶点
    int vertex2;//边的第二个顶点
    int w;//边的权值
    struct Edge *next;
};
void Kruskal(Edge *h, int *visited)
{//h链表中的结点是按照权值由小到大连接在一起的，因此需要在生成边的过程中排序
    int edgenum = 0;//统计生成树中边的个数
    int weight = 0;
    Edge *p = h;
    while(edgenum != maximum)//当生成树中边的数目等于顶点个数减1时，生成过程结束
    {
        if(visited[p->vertex1]==0 || visited[p->vertex2] == 0)//边的某顶点未被访问，避免形成回路（||用得好）
        {
            printf("(%d %d %d)->",p->vertex1,p->vertex2,p->w);
            weight = weight+p->w;//总权值累加
            visited[p->vertex1] = 1;
            visited[p->vertex2] = 1;
            edgenum++;
        }
        p = p->next;
        if(p == NULL)//已无边
        {
            break;
        }
    }
    printf("\n%d\n",wegiht);
}
//边结点链表生成算法（有序）：
//手动输入各边的头尾顶点，在输入的过程中，需要判断顶点是否超出范围，每输入一个边结点，都和已有的边结点比较权值大小，按照权值递增的顺序连接各结点
Edge* Create_Edge(int source, int destination, int weight)
{
    Edge *h;//指向边结点
    Edge *node;
    Edge *p;
    int i;
    h = (Edge*)malloc(sizeof(Edge));//为第一个边结点分配存储空间
    h->vertex1 = source;
    h->vertex2 = destination;
    h->w = weight;
    h->next = NULL;
    while(1)//输入边结点
    {
        scanf("%d",&source);
        if(source == -1)//停止输入顶点，跳出循环
            break;
        if(source >= maximum)//边首顶点超出范围
        {
            printf("顶点超出范围，重新输入：");
            scanf("%d",&source);
        }
        scanf("%d",&destination);//输入边尾结点
        if(destination == source);
        {
            printf("出现循环,重新输入：");
            scanf("%d",&destination);
        }
        if(destination >= maximum)//边尾顶点超出范围
        {
            printf("顶点超出范围，重新输入：");
            scanf("%d",&destination);
        }
        scanf("%d",&weight);
        node = (Edge*)malloc(sizeof(Edge));//新的边结点
        node->vertex1 = source;
        node->vertex2 = destination;
        node->w = weight;
        node->next = NULL;
        p = h;
        while(1)
        {
            if(node->w < h->w)
            {
                node->next = h;
                h = node;
                break;
            }
            if(p->next != NULL)
            {
                if(node->w >= p->w && node->w < p->next->w)
                {
                    node->next = p->next;
                    p->next = node;
                    break;
                }
            }
            else
            {
                node->next = p->next;
                p->next = node;
                break;
            }
            p = p->next;
        }
    }
    return h;
}//第一个结点从外部函数输入；在插入结点的过程中，不断比较权值，所以当结点插入完成时，链表是有序的。

Prim算法：

Kruskal算法中需要检查所有加入的边是否会形成回路，针对这个问题，Prim提出了Prim算法来避免回路的检查，方法是从某个顶点vi出发，列出顶点所有邻接点的边，选择最小的边加入到MST中，然后删除该边，再加入顶点vj除了和vi相连边之外的所有边，再找出最小的边，依次类推，直到找到n-1条边为止。

算法步骤：

  1. 选择从某顶点vi开始。
  2. 将vi的所有边加入。

1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//Prim算法：
#include <stdio.h>
#include <malloc.h>
#define maximum 6
struct Edge{
    int vertex1;
    int vertex2;
    int w;
    int marked;//表示此边是否已加入到生成树中
    struct Edge* next;
};
void Prims(Edge *h, int *visited, int index)//h为边结点构成的链表，index表示开始顶点
{
    Edge *p;
    Edge *min; //最小权值边顶点
    min = (Edge*)malloc(sizeof(Edge));//分配结点空间
    int i;
    int edgenum = 0;//已连接边的条数
    int weightsum = 0; // 总的权值
    int vertex;
    /* 第一条边 */
    min->w = 100;//将最小权值的初始值设为100
    p=h;
    while(p != NULL)
    {
        if(p->vertex1 == index)//同一个点所连接的边
            if(p->w < min->w)//选择那个点所连接的最小的边
                min = p;//找到权值最小的边，记录起来
        p = p->next;
    }
    min->marked = 1;//此边已访问
    visited[min->vertex1] = 1;
    visited[min->vertex2] = 1;//两个顶点访问过
    edgenum++;
    weightsum = min->w;
    printf("最小生成树：\n");
    printf("(%d %d %d)->",min->vertex1,min->vertex2, min->w);
    /* 其余边 */
    while(edgenum < maximum-1)//最小生成树完全产生
    {
        min->w = 100;//初始化最小权值，以后比较
        p = h;
        while(p != NULL)
        {
            if(p->marked == 0)//没有加入的   //一个点在生成树集合中，另一个点不在，不会形成回路
                if((visited[p->vertex1]==1&&visited[p->vertex2]==0)||(visited[p->vertex1]==0&&visited[p->vertex2]==1))
                    if(p->w < min->w)
                        min = p;
            p = p->next;
        }
        min->marked = 1;//此边已访问
        visited[min->vertex1] = 1;
        visited[min->vertex2] = 1;
        printf("(%d %d %d)->",min->vertex1, min->vertex2, min->w);
        edgenum++;
        weightsum+=min->w;
    }
    printf("\n");
    printf("总权值：%d",weightsum);
    printf("\n");
}//最小生成树生成的过程中，不能形成回路，因此在加入新边的时候，必须满足该边的一个顶点在生成树集合中，另一个顶点不在此集合中，否则会形成回路。

最短路径：

单源点最短路径问题：

从有向带权图中一个确定的顶点到其余各个顶点的最短路径问题。
Dijkastra提出了一个按路径长度递增的顺序逐步产生最短路径的构造算法。

算法思想：

设置两个顶点集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还没找到最短路径的顶点，初始状态时，集合S中只包含源点，设为v0，然后从集合T中选择到源点路径最短的顶点vm加入到S中，集合S中每加入一个顶点vm，都要修改源点vo到集合T中剩余顶点的最短路径值，集合T中各顶点的新的最短路径值为原来的最短路径长度值与从源点过顶点vm到达该顶点的路径长度中的较小者。不断重复此过程，直到集合T中的顶点全部加入到集合S中为止。(l(vm) = min{l(vm),l(vk)+w(vk,vm)})

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//Dijkstra算法：//Graph存储点与点之间的权值（只有两点直接相连的有，不直接相连的点 权值设为无穷）
void Dijkstra(int Graph[maximum][maximum], int index, int *visited, int *Dis)
{//从index顶点开始，Dis数组存储从index到所有顶点的最短距离
    Dis[index] = 0;
    int j;
    int min;//距离最小边
    int vertex; //距离最小边的顶点
    int edgenum = 0;//已得出的最小边个数
    visited[index] = 1;
    for(j = 1; j < maximum; j++)
        Dis[j] = Graph[index][j];//index到各点的初始距离//数值小于min的说明直接相连，数值为无穷的说明不直接相连
    while(edgenum < maximum)
    {
        min = 100;//设为最大值
        for(j=1; j<maximum; j++)//寻找和index直接连通的最小路径
        {
            if(visited[j]==0 && Dis[j] < min)
            {
                vertex = j;
                min = Dis[j];
            }
        }
        visited[vertex] = 1;
        edgenum++;
        for(j=1; j<maximum; j++)
        {
            if(visited[j] == 0 && (Dis[vertex] + Graph[vertex][j] < Dis[j]))
                Dis[j] = Dis[vertex] + Graph[vertex][j];//利用已找到的点查找其他点的最短距离
        }
    }
}

1

过程：

  1. 1
  2. 1->3 1->2
  3. 3->2; 3->5
  4. 2->4; 2->5
  5. 5->6; (5->4失败）
  6. 4->6 (4->5失败）
  7. 最终：1->3->2->4->6 ; 1->3->2->5

所有顶点对最短路径问题：

在邻接矩阵上做n次迭代，第n次迭代后，邻接矩阵上第i行第j列的元素即为i到j的最短路径。

假设求顶点i到顶点j的最短路径，1<= i, j <= n。

首先，考虑从i到j是否有中间点顶点1，路径：i->1->j，若有则路径长度取(i, j)和(i, 1, j)的较小值

其次，考虑有无中间点为顶点2的情况

再次，顶点3的情况

······

Floyed算法：

设min矩阵存储最短距离，其初始值为图的邻接矩阵，依次以每个顶点为中间点，重新计算各对顶点之间的最短距离

1
2
3
4
5
6
7
8
9
10
11
//Floyed算法：
void Floyed(int min[maximum][maximum])
{
    int i, j, k;//起点，终点，中间点
    for(k=0; k<maximum; k++)//中间点
        for(i=0; i<maximum; i++)//起点
            for(j=0; j<maximum; j++)//终点
                if(min[i][j] > min[i][k]+min[k][j])
                    min[i][j] = min[i][k] + min[k][j];
                //经过中间点k的距离小于由i到j的直接距离，此时，用经由k的距离作为新的最短距离
}

拓扑排序：

在一个较大的工程通常被划分为若干个子工程，我们把这些工程称为活动，在整个工程中，有些活动必须在其他活动完成之后才能进行，还有一些活动可以安排在任何时间开始。

为了形象地反映出整个工程中各个活动，图中的有向边代表活动的先后关系，即有向边的起点活动是终点活动的前序活动，只有起点活动完成之后，其终点活动才能进行。这种顶点表示活动、边表示活动间先后关系的有向图称作顶点活动图（Activity on Vertex Network ,AOV)

AOV网中不允许有回路，这就意味着某项活动不能以自己为先决条件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//拓扑排序
//先统计每个顶点的入度，然后依次将入度为0的顶点入队，直到所有顶点都入队为止，最后再使这些元素出队即可
void TopoSort(int *visited, int *Queue)//visited数组存储每个顶点的入度
{
    int i;
    int topnum = 0;
    GraphNode *p;
    for(i=0; i<maximum; i++)
    {
        p = (&Graph[i])->next;//p指向第i个顶点
        while(p != NULL)
        {
            visited[p->data]++;//p->data指哪个顶点，visited用来记录度数
            p = p->next;
        }
    }
    while(topnum != maximum)
    {
        for(i=0; i<maximum; i++)
        {
            if(visited[i] == 0)
            {
                AddQueue(Queue, i);
                p = (&Graph[i])->next;
                while(p!=NULL)
                {
                    visited[p->data]--;
                    p = p->next;
                }
                visited[i] = -1;
            }
        }
        topnum++;
    }
    for(i=0; i<maximum; i++)
        printf("%d ",Delqueue(Queue));
}

关键路径：

在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。 关键路径的工期决定了整个项目的工期。 任何关键路径上的终端元素的延迟将直接影响项目的预期完成时间（例如在关键路径上没有浮动时间）。 一个项目可以有多个，并行的关键路径。

练习：

1.遍历算法：

图的深度优先遍历和广度优先遍历算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
//对图进行深度优先遍历和广度优先遍历：
typedef struct Node{
    int data;//第一个邻接顶点
    struct Node *next;//下一个邻接顶点指针
}GraphNode;
GraphNode Graph[maximum];//顶点数组
int rear = -1;//队尾指针
int front = -1;//队头指针
//出队/入队操作：
void AddQueue(int *h, int x)
{
    if(rear == maximum-1)
    {
        printf("队列已满\n");
        return ;
    }
    rear++;
    h[rear] = x;
    return;
}
int Delqueue(int *h)
{
    int e;
    if(rear == front)
    {
        printf("Queue is empty\n");
        return -1;
    }
    front++;
    e = h[front];
    h[front] = 0;
    return e;
}
//建立邻接表：
void CreateAdjacentTable(int v1, int v2)
{
    GraphNode* newnode;
    newnode = (GraphNode*)malloc(sizeof(GraphNode));
    newnode->data = v2; newnode->next = NULL;
    GraphNode* p;
    p = &Graph[v1];
    while(p->next != NULL)
        p = p->next;
    p->next = newnode;
}
//深度优先遍历： 
void DFS(int *visited, int v)
{
    GraphNode* p;
    visited[v] = 1;
    printf("%d->",v);
    p = Graph[v].next;
    while(p != NULL)
    {
        if(visited[p->data] == 0)
            DFS(visited, p->data);//递归！
        p = p->next;
    }
}
//广度优先遍历：
void BFS(int *visited, int v, int *Queue)
{
    GraphNode* p;
    AddQueue(Queue, v);
    visited[v] = 1;
    printf("%d->",v);
    while(front != rear)//队列！
    {
        v = Delqueue(Queue);
        p = Graph[v].next;
        while(p != NULL)
        {
            if(visited[p->data] == 0)
            {
                AddQueue(Queue, p->data);
                visited[p->data] = 1;
                printf("%d->",p->data);
            }
            p = p->next;
        }
    }
}
//显示邻接表：
void DisplayGraph(GraphNode* h)
{
    GraphNode* p;
    p = h->next;
    while(p != NULL)
    {
        printf("%d->",p->data);
        p = p->next;
    }
    printf("\n");
}
//主函数：
int main()
{
    int souce, destination;
    int i;
    for(i=0; i<maximum; i++)//顶点初始化
    {
        Graph[i].data = i;
        Graph[i].next = NULL;
    }
    printf("输入图的邻接表\n");
    while(1)
    {
        scanf("%d",&souce);
        if(souce == -1)
            break;
        if(souce >= maximum)
        {
            printf("顶点超出范围，重新输入:\n");
            scanf("%d",&souce);
        }
        scanf("%d",&destination);
        if(destination == souce)
        {
            printf("出现循环，重新输入:\n");   
            scanf("%d", &destination);
        }
        if(destination >= maximum)
        {
            printf("顶点超出范围，重新输入:\n");
            scanf("%d",&destination);
        }
        CreateAdjacentTable(souce, destination);
    }
    printf("图的邻接表：\n");
    for(i=0; i<maximum; i++)
    {
        printf("Vertex %d :->",i);
        DisplayGraph(&Graph[i]);
    }
    int visited[maximum];
    for(i = 0; i < maximum; i++)
        visited[i] = 0;
    printf("深度优先遍历：");
    DFS(visited, 0);
    printf("\n");
    for(i = 0; i < maximum; i++)
        visited[i] = 0;
    printf("广度优先遍历：");
    int Queue[maximum];
    BFS(visited, 0, Queue);
    printf("\n");
}

2.Prim算法：

先构造边结点链表，然后找出最小生成树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
//Prim算法：
#include <stdio.h>
#include <malloc.h>
#define maximum 6
struct Edge{
    int vertex1;
    int vertex2;
    int w;
    int marked;
    struct Edge* next;
}
void Prims(Edge *h, int *visited, int index)
{
    Edge *p;
    Edge *min;
    min = (Edge*)malloc(sizeof(Edge));
    int i;
    int edgenum = 0;
    int weightsum = 0;
    int vertex;
    min->w = 100;
    p = h;
    while(p != NULL)
    {
        if(p->vertex1 == index)
            if(p->w < min->w)
                min = p;
        p = p->next;
    }
    min->marked = 1;
    visited[min->vertex1] = 1;
    visited[min->vertex2] = 1;
    edgenum++;
    weightsum = min->w;
    printf("最小生成树：\n");
    printf("(%d %d %d)->",min->vertex1, min->vertex2, min->w);
    while(edgenum < maximum-1)
    {
        min->w = 100;
        p = h;
        while(p != NULL)
        {
            if(p->marked == 0)
                if((visited[p->vertex1] == 1 && visited[p->vertex2] == 0) || (visited[p->vertex1] == 0 && visited[p->vertex2] == 1))
                    if(p->w < min->w)
                        min = p;
            p = p->next;
        }
        min->marked = 1;
        visited[min->vertex1] = 1;
        visited[min->vertex2] = 1;
        printf("(%d %d %d)->",min->vertex1, min->vertex2, min->w);
        edgenum++;
        weightsum += min->w;
    }
    printf("\n");
    printf("总权值：%d",weightsum);
    printf("\n");
}
//建立图：
Edge *Create_Edge(int souce, int destination, int wegiht)
{
    Edge *h;
    Edge *node;
    Edge *p;
    int i;
    int num = 0;
    h = (Edge*)malloc(sizeof(Edge));
    h->vertex1 = souce;
    h->vertex2 = destination;
    h->w = weight;
    h->next = NULL;
    p = h;
    while(1)
    {
        scanf("%d",souce);
        if(souce == -1)
            break;
        if(souce >= maximum)
        {
            printf("顶点超出范围，重新输入:\n");
            scanf("%d",&souce);
        }
        scanf("%d",&destination);
        if(destination == souce)
        {
            printf("出现循环，重新输入:\n");   
            scanf("%d", &destination);
        }
        if(destination >= maximum)
        {
            printf("顶点超出范围，重新输入:\n");
            scanf("%d",&destination);
        }
        scanf("%d", &weight);
        node = (Edge*)malloc(sizeof(Edge));
        node->vertex1 = souce;
        node->vertex2 = destination;
        node->w = weight;
        node->marked = 0;
        node->next = NULL;
        p->next = node;
        p = node;
    }
    return h;
}
//显示图
void DisplayEdge(Edge *h)
{
    Edge *p = h;
    while(p != NULL)
    {
        printf("(%d %d %d)->",p->vertex1, p->vertex2, p->w);
        p = p->next;
    }
    printf("\n");
}
//主函数：
int main()
{
    Edge *head;
    int visited[maximum];
    for(int i=0; i<maximum; i++)
        visited[i] = 0;
    printf("输入图：\n");
    head = Create_Edge(0, 1, 4);
    printf("边结点：\n");
    DisplayEdge(head);
    int index = 0;
    visited[index] = 1;
    Prims(head, visited, 0);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
private:
	int v_num;
	int e_num;
	vector<vector<int>> map;
public:
	Graph(): v_num(0), e_num(0) {}
	~Graph(){}
	Graph(int n): v_num(n), e_num(0) {
		map.resize(n);
		for(int i=0; i<n; i++)
			map[i].resize(n);
	}
	void push(int from, int to){
		if(map[from][to] == 1)
			return;
		map[from][to] = 1;
		map[to][from] = 1;
		e_num++;
	}
	void remove(int from, int to){
		if(map[from][to] == 0)
			return;
		map[from][to] = 0;
		map[to][from] = 0;
		e_num--;
	}
	int get_v_num(){ return v_num; }
	int get_e_num() { return e_num; } 
	void print_map() {
		for(int i=0; i<v_num; i++)
		{
			for(int j=0; j<v_num; j++)
				cout << map[i][j] << " ";
			cout << endl;
		}
	}
	void bfs( int start , int* visited){
		queue<int> Q;
		Q.push(start);
		visited[start] = 1;
		while(!Q.empty()){
			int tmp = Q.front();
			Q.pop();
			cout << tmp << " ";
			for(int i=0; i<v_num; i++)
			{
				if(map[tmp][i] == 1 && visited[i] == 0)
				{
					Q.push(i);
					visited[i] = 1;
				}
			}
		}
	}
	void dfs( int start , int* visited ){
		visited[start] = 1;
		cout << start << " ";
		for(int i=0; i<v_num; i++)
		{
			if(map[start][i] == 1 && visited[i] == 0)
			{
				dfs( i , visited);
			}
		}
	}
};


int main(){
	Graph test(10);
	cout << "get_v_num : " << endl;
	cout << test.get_v_num() << endl;
	cout << "get_e_num : " << endl;
	cout << test.get_e_num() << endl;
	cout << "print_map : " << endl;
	test.print_map();
	test.push(1,2);
	test.push(2,3);
	test.push(2,4);
	test.push(1,4);
	test.push(1,5);
	test.push(5,4);
	test.push(4,6);
	cout << "print_map : " << endl;
	test.print_map();
	cout << "get_e_num : " << endl;
	cout << test.get_e_num() << endl;
	cout << "dfs : " << endl;
	int visited[test.get_v_num()] = {0};
	test.dfs(1, visited);
	for(int i=0; i<test.get_v_num(); i++)
		visited[i] = 0;
	cout << endl;
	cout << "bfs : " << endl;
	test.bfs(1, visited);
	for(int i=0; i<test.get_v_num(); i++)
		visited[i] = 0;
	cout << endl;
	return 0;
}
Donate? comment?