图

[TOC]

图

图的定义和基本术语

  1. 完全图

    有n个点每个点都与n-1个点有边，但是注意如果是无向的边则应该是n*(n-1)/2。如果是有向的边，则应该是n*(n-1)

  2. 稀疏图(e<nlogn)

    带箭头的边称为狐

    有很少的边或狐的图

  3. 稠密图

    有较多的边或狐的图

  4. 网

    边/狐带权（有意义，如：20km等）的图

  5. 邻接

    有边/狐相连的两个顶点之间的关系

    根据离散的知识(Vi,Vj)这是不分先后的（小括号括起来），则说Vi,Vj互称为邻接点

    <Vi,Vj>则则是有序的，对应有向的图Vi邻接到Vj，Vj邻接于Vi

  6. 关联（依附）

    边或者狐与顶点的关系

  7. 顶点的度

    该顶点相关联的边的条数

    在有向图当中，顶点的度等于该顶点的出度和入度之和

    • 入度：是以该顶点为终点的有向边
    • 出度：是以该顶点为起点的有向边

    有向树

  8. 路径

    按续的边构成的点的顶点序列

  9. 路径长度

    路径上边或者狐的数目（权值）之和

  10. 环（回路）

    第一个顶点和最后一个顶点相同的路径

  11. 简单的路径

    除了路径的起点和终点可以相同，其他的都不同

  12. 简单的回路（简单的环）：除路径和终点相同，其他的顶点都不相同（注意区别简单路径和简单的回路）

  13. 连通图

    就是图中任意的两个点都能够连接起来

  14. 权

    图中的边或则弧线具有的相关的数被称为权。表明从一个顶点到另一个顶点的距离和消耗

  15. 网

    带权的图

  16. 子图

    如果一个图是；另一个图的一部分就说明是子图

  17. 连通分量

    无向图的最大联通的子图就称为G 的连通分量

  18. 强连通分量

  19. 极小连通子图

    就是连通子图，如果再删除一条边，就不连通则说明是极小的连同子图

  20. 生成树

    包含无向图的的所有的顶点的绩极小的联通子图

  21. 图和树的不同

    • 树是一种特殊的图，但是没有环，也就是说树的两个结点只有唯一路径
    • 树的每一个节点有且仅有1或者0个前驱。但是树可以有多个前驱
    • 树的每一个结点只会存在一种关系，即父子关系。但是图可以有多种关系。比如：有向边和无向边
    • 树一般用于分层存储和处理数据，如文件系统等；而图则更加灵活，可以用于表示各种复杂关系和网络结构，如社交网络、电脑网络、交通网络等等。

  22. 相同点

    树和图是两种基本的非线性数据结构

图的存储结构

数组表示法（邻接矩阵）

使用矩阵的方式，如果两个点存在一个则对应的数组的值为1，反之为0

无向图的邻接矩阵表示法

  1. 临界矩阵的特点

    • 对角线值为0
    • 矩阵是对称的

  2. 矩阵度的计算

    定点i的度，就是第i行1的个数

    特别的完全图的邻接矩阵中，对角线元素为0，其余为1

有向图的邻接矩阵表示法

  1. 同理，有箭头的则是1，也就是从该点指出去

  2. 第i行的含义

    以节点vi为结尾的弧（出度）

  3. 第i列的含义

    以节点vi为头的弧（入度）

  4. 有向图的度

    是出度和入度的和

邻接矩阵的实现

1
2
3
4
5
6
7
8
9
10
11
12
#define MaxInt 32767   //有向表的正无穷
#define MVNum 100	   //最大定点数
typedef char VerTexType;   //定点的类型
typedef int ArcType;      //权值


typedef struct AMGraph {
    VerTexType vexs[MVNum];   //定点表
    ArcType arcs[MVNum][MVNum];   //邻接矩阵
    int vexnum, arcnum;//图的当前点数和边的数目
}AMGraph;

网的表示法

  1. 将有连接的转变成权值而不是1
  2. 没有连接的为0

无向图的创建

  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
    #include"stdio.h"
    #include"stdlib.h"
    #define MaxInt 32767   //有向表的正无穷
    #define MVNum 100	   //最大定点数
    typedef char VerTexType;   //定点的类型
    typedef int ArcType;      //权值
    typedef int statue;
       
    typedef struct AMGraph {
        VerTexType vexs[MVNum];   //定点表
        ArcType arcs[MVNum][MVNum];   //邻接矩阵
        int vexnum, arcnum;//图的当前点数和边的数目
    }AMGraph,*pAMGraph;
       
       
    //查找对应的下标
    //int LocateVex(pAMGraph G,char ch) {
    //	for (int i = 0; i < G->vexnum; i++)
    //	{
    //		if (ch == G->vexs[i]) {
    //			return i;
    //		}
    //	}
    //	return -1;
    }
    }
    //}
       
    statu ue CreatUDN(pAMGraph *G) {
        int x, y;//模拟二维数组的x,y;
        char aPoint,bPoint;//
        scanf("%d%d", &(*G)->vexnum, &(*G)->arcnum);
        //创建节点
        for (int i = 0; i < (*G)->vexnum; i++)
        {
            (*G)->vexs[i] = 'A' + i;
        }
       
        //初始化表
        for (int i = 0; i < (*G)->arcnum; i++)
        {
            for (int j = 0; j < (*G)->arcnum; j++)
            {
                (*G)->arcs[i][j] = MaxInt;
            }
        }
        //赋予权值
        for (int i = 0; i < (*G)->arcnum; i++)
        {
            for (int j = 0; j < (*G)->arcnum; j++)
            {
                (*G)->arcs[i][j] = MaxInt;
            }
        } 
       
        ////对每一条边进行赋值
        //scanf("%c%c", &aPoint,&bPoint);//对a->b的边进行赋权
        //x = LocateVex(G, aPoint);
        //y = LocateVex(G, bPoint);
        //for (int i = 0; i < (*G)->vexnum; ++i) {
        //	scanf("%d", &(*G)->arcs[x][y]);
        //	(*G)->arcs[x][y] = (*G)->arcs[y][x];//无向网，所以邻接矩阵是对称的
       
        //}
    }
       
    int main() {
        pAMGraph G = (pAMGraph)malloc(sizeof(AMGraph));
        CreatUDN(&G);
        return 0;
    }

邻接矩阵构建有向图

使用邻接矩阵的优点

  1. 直观简单

  2. 方便查看某个图的节点

  3. 方便查找任意节点的邻接点

  4. 方便计算出某个节点的度

使用邻接矩阵的缺点

空间复杂度是O(n^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
          #define MaxInt 32767   //有向表的正无穷
      #define MVNum 100       //最大定点数
      typedef char VerTexType;   //定点的类型
      typedef int ArcType;      //权值
           
           
      typedef struct AMGraph {
          VerTexType vexs[MVNum];   //顶点表
          ArcType arcs[MVNum][MVNum];   //邻接矩阵
          int vexnum, arcnum;//图的当前点数和边的数目
      } AMGraph;
           
      typedef struct node // 边表节点
      {
          VerTexType adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
          struct node *next; // 指向顶点的下一个邻接点
      } EdgeNode;
           
           
      typedef struct vnode       // 顶点结构
      {
          VerTexType vex;      // 存储顶点名
          EdgeNode *firstedge; // 边表头指针，指向顶点第一个邻接点
      } VertexNode, AdjList[MVNum];
           
      void creatGraph(AMGraph **amGraph) {
          *amGraph = (AMGraph *) malloc(sizeof(AMGraph));
          (*amGraph)->vexnum = 0;
          (*amGraph)->arcnum = 0;
          for (int i = 0; i < 6; ++i) {
              (*amGraph)->vexs[i] = 'A' + i;
              (*amGraph)->vexnum++;
           
          }
          //创建邻接矩阵
          for (int i = 0; i < 6; ++i) {
              for (int j = 0; j < 6; ++j) {
                  scanf("%d", &(*amGraph)->arcs[i][j]);
                  if ((*amGraph)->arcs[i][j] == 1) {
                      (*amGraph)->arcnum++;
                  }
              }
          }
          (*amGraph)->arcnum /= 2;
           
      }
           
      void creatAdjacencyList(AMGraph *amGraph, AdjList adjList) {
          for (int i = 0; i < amGraph->vexnum; ++i) {
              adjList[i].vex = amGraph->vexs[i];
              adjList[i].firstedge = NULL;
              EdgeNode *moveNode = NULL;
              for (int j = 0; j < amGraph->vexnum; ++j) {
                  //下面就是创建链表的过程，只是在第一个的时候相当于创建头节点
                  if (amGraph->arcs[i][j] == 1) {//=1说明连同
                      if (adjList[i].firstedge == NULL) {
                          adjList[i].firstedge=(EdgeNode *)malloc(sizeof (struct node));
                          adjList[i].firstedge->adjvex = amGraph->vexs[j];
                          adjList[i].firstedge->next=NULL;
                          moveNode = adjList[i].firstedge;
                      } else {
                          EdgeNode *tem=(EdgeNode*)malloc(sizeof(EdgeNode));
                          tem->adjvex=amGraph->vexs[j];
                          tem->next=NULL;
                          moveNode->next=tem;
                          moveNode=moveNode->next;
                      }
                  }
              }
          }
      }
           
      int main() {
          AMGraph *amGraph;//邻接表
          AdjList adjList={0};//邻接表的点集合，全部初始化
          int ints[6] = {0};//在搜索中，记录是否别查看
          creatGraph(&amGraph);//创建邻接矩阵
          creatAdjacencyList(amGraph,adjList);//创建邻接表
          return 0;
      }

    有向图

  2. 邻接多重表

    每个数字后面的空格都是，存放指针，用于连接

    • 连接顺序不唯一

  3. 十字链表

    给顶点结点加一个指向出度边的指针

    给狐结点添一个把该节点当成头节点的狐的数据域和指针域

    优点：有利于找到出度和入度，通过head可以找到整个入度的边

图的遍历

  • 遍历的实质

  • 怎么防止重复访问？

    图中含有回路，而且每一个顶点都与其他顶点相通，所以可能通过某一个过程又回到了原来的点

    设置一个辅助的数组，用来标记每一个被访问的顶点，初始状态为0

    被访问了，就应该改变状态

深度优先搜索（DFS）

邻接矩阵

  • 采取递归的方法

  • 防止循环遍历，我们应该建立一个visit存放所有的结点，然后我们把遍历过的结点标识为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
        #define MaxInt 32767   //有向表的正无穷
    #define MVNum 100       //最大定点数
    typedef char VerTexType;   //定点的类型
    typedef int ArcType;      //权值
      
      
    typedef struct AMGraph {
        VerTexType vexs[MVNum];   //顶点表
        ArcType arcs[MVNum][MVNum];   //邻接矩阵
        int vexnum, arcnum;//图的当前点数和边的数目
    } AMGraph;
      
      
      
    void creatGraph(AMGraph **amGraph) {
        *amGraph = (AMGraph *) malloc(sizeof(AMGraph));
        (*amGraph)->vexnum = 0;
        (*amGraph)->arcnum = 0;
        for (int i = 0; i < 6; ++i) {
            (*amGraph)->vexs[i] = 'A' + i;
            (*amGraph)->vexnum++;
      
        }
        //创建邻接矩阵
        for (int i = 0; i < 6; ++i) {
            for (int j = 0; j < 6; ++j) {
                scanf("%d", &(*amGraph)->arcs[i][j]);
                if ((*amGraph)->arcs[i][j] == 1) {
                    (*amGraph)->arcnum++;
                }
            }
        }
        (*amGraph)->arcnum /= 2;//无向边
      
    }
      
    //邻接矩阵
    void DFS(AMGraph *amGraph, int visited[],int sub) {
        printf("%c",amGraph->vexs[sub]);
        visited[sub]=1;
        for (int i = 0; i < amGraph->vexnum; ++i) {
            if (amGraph->arcs[sub][i]!=0&&visited[i]==0){
                DFS(amGraph,visited,i);
            }
        }
    }
      
    int main() {
        AMGraph *amGraph;//邻接表
        int ints[6] = {0};//在搜索中，记录是否别查看
        creatGraph(&amGraph);//创建邻接矩阵
        DFS(amGraph,ints,1);
        return 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
    107
    108
    109
        #include <stdlib.h>
    #include <stdio.h>
      
    #define MaxInt 32767   //有向表的正无穷
    #define MVNum 100       //最大定点数
    typedef char VerTexType;   //定点的类型
    typedef int ArcType;      //权值
      
      
    typedef struct AMGraph {
        VerTexType vexs[MVNum];   //顶点表
        ArcType arcs[MVNum][MVNum];   //邻接矩阵
        int vexnum, arcnum;//图的当前点数和边的数目
    } AMGraph;
      
    typedef struct node // 边表节点
    {
        int adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
        struct node *next; // 指向顶点的下一个邻接点
    } EdgeNode;
      
      
    typedef struct vnode       // 顶点结构
    {
        VerTexType vex;      // 存储顶点名
        EdgeNode *firstedge; // 边表头指针，指向顶点第一个邻接点
    } VertexNode, AdjList[MVNum];
      
    void creatGraph(AMGraph **amGraph) {
        *amGraph = (AMGraph *) malloc(sizeof(AMGraph));
        (*amGraph)->vexnum = 0;
        (*amGraph)->arcnum = 0;
        for (int i = 0; i < 6; ++i) {
            (*amGraph)->vexs[i] = 'A' + i;
            (*amGraph)->vexnum++;
      
        }
        //创建邻接矩阵
        for (int i = 0; i < 6; ++i) {
            for (int j = 0; j < 6; ++j) {
                scanf("%d", &(*amGraph)->arcs[i][j]);
                if ((*amGraph)->arcs[i][j] == 1) {
                    (*amGraph)->arcnum++;
                }
            }
        }
        (*amGraph)->arcnum /= 2;
      
    }
      
    void creatAdjacencyList(AMGraph *amGraph, AdjList adjList) {
        for (int i = 0; i < amGraph->vexnum; ++i) {
            adjList[i].vex = amGraph->vexs[i];
            adjList[i].firstedge = NULL;
            EdgeNode *moveNode = NULL;
            for (int j = 0; j < amGraph->vexnum; ++j) {
                //下面就是创建链表的过程，只是在第一个的时候相当于创建头节点
                if (amGraph->arcs[i][j] == 1) {//=1说明连同
                    if (adjList[i].firstedge == NULL) {
                        adjList[i].firstedge=(EdgeNode *)malloc(sizeof (struct node));
                        adjList[i].firstedge->adjvex = j;
                        adjList[i].firstedge->next=NULL;
                        moveNode = adjList[i].firstedge;
                    } else {
                        EdgeNode *tem=(EdgeNode*)malloc(sizeof(EdgeNode));
                        tem->adjvex=j;
                        tem->next=NULL;
                        moveNode->next=tem;
                        moveNode=moveNode->next;
                    }
                }
            }
        }
    }
      
    //邻接矩阵
    /*void DFS(AMGraph *amGraph, int visited[],int sub) {
        printf("%c",amGraph->vexs[sub]);
        visited[sub]=1;
        for (int i = 0; i < amGraph->vexnum; ++i) {
            if (amGraph->arcs[sub][i]!=0&&visited[i]==0){
                DFS(amGraph,visited,i);
            }
        }
    }*/
      
      
    //邻接表
    void DFS(AdjList adjList,int ints[],int sub){
        printf("%c",adjList[sub].vex);
        ints[sub]=1;
        EdgeNode *moveNode=adjList[sub].firstedge;
        while(moveNode!=NULL){
            if(ints[moveNode->adjvex]==0){
                DFS(adjList,ints,moveNode->adjvex);
            }
            moveNode=moveNode->next;
        }
    }
    int main() {
        AMGraph *amGraph;//邻接表
        AdjList adjList={0};//邻接表的点集合，全部初始化
        int ints[6] = {0};//在搜索中，记录是否别查看
        creatGraph(&amGraph);//创建邻接矩阵
        creatAdjacencyList(amGraph,adjList);//创建邻接表
        DFS(adjList,ints,1);
        return 0;
    }

总结

稠密图适用于邻接矩阵上进行深度遍历

稀疏图适用于在邻接表上深度遍历

非连通图

  1. 可以想象成两个图，然后增加一个虚拟节点，将图穿起来
  2. 如果图的数量不是2个，那就只能在非第一次遍历的图中再选一个图的随机的一个节点开始遍历

广度优先搜索（BFS）

邻接矩阵

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
using namespace std;

#define MaxInt 32767   //有向表的正无穷
#define MVNum 100       //最大定点数
typedef char VerTexType;   //定点的类型
typedef int ArcType;      //权值

typedef struct AMGraph {
    VerTexType vexs[MVNum];   //顶点表
    ArcType arcs[MVNum][MVNum];   //邻接矩阵
    int vexnum, arcnum;//图的当前点数和边的数目
} AMGraph, *pAMGraph;

void creatGraph(pAMGraph &amGraph, int num) {
    amGraph = new AMGraph;
    amGraph->arcnum = 0;
    for (int i = 0; i < num; ++i) {
        amGraph->vexs[i] = 'A' + i;
    }
    amGraph->vexnum = num;
    for (int i = 0; i < num; ++i) {
        for (int j = 0; j < num; ++j) {
            cin >> amGraph->arcs[i][j];
            if (amGraph->arcs[i][j] != 0) {
                amGraph->arcnum++;//计算边数
            }
        }
    }
    amGraph->arcnum /= 2;
}

void BFS(pAMGraph amGraph, int ints[], int sub) {
    queue<int> queue;
    queue.push(sub);//先push，进入循环，但是记得在ints里面标记被push
    ints[sub]=1;
    while (!queue.empty()) {
        for (int i = 0; i < amGraph->vexnum; ++i) {
            if (amGraph->arcs[queue.front()][i] == 1&&ints[i]==0) {
                queue.push(i);
                ints[i]=1;
            }
        }
        cout<<amGraph->vexs[queue.front()];
        queue.pop();
    }
}

int main() {
    pAMGraph amGraph = nullptr;
    int num;
    cin >> num;//输入节点数
    creatGraph(amGraph, num);
    int *ints=new int[num];
    for (int i = 0; i < num; ++i) {
        *(ints+i)=0;
    }//将被查看表全部设为0
    BFS(amGraph, ints, 0);
    delete[] ints;
    return 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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
    #include <stdlib.h>
#include <stdio.h>

#define MaxInt 32767   //有向表的正无穷
#define MVNum 100       //最大定点数
typedef char VerTexType;   //定点的类型
typedef int ArcType;      //权值


typedef struct AMGraph {
    VerTexType vexs[MVNum];   //顶点表
    ArcType arcs[MVNum][MVNum];   //邻接矩阵
    int vexnum, arcnum;//图的当前点数和边的数目
} AMGraph;

typedef struct node // 边表节点
{
    int adjvex; // 与顶点相连的邻接点下标(adjoin：邻接)
    struct node *next; // 指向顶点的下一个邻接点
} EdgeNode;


typedef struct vnode       // 顶点结构
{
    VerTexType vex;      // 存储顶点名
    EdgeNode *firstedge; // 边表头指针，指向顶点第一个邻接点
} VertexNode, AdjList[MVNum];

void creatGraph(AMGraph **amGraph,int num) {
    *amGraph = (AMGraph *) malloc(sizeof(AMGraph));
    (*amGraph)->vexnum = 0;
    (*amGraph)->arcnum = 0;
    for (int i = 0; i < num; ++i) {
        (*amGraph)->vexs[i] = 'A' + i;
        (*amGraph)->vexnum++;

    }
    //创建邻接矩阵
    for (int i = 0; i < num; ++i) {
        for (int j = 0; j < num; ++j) {
            scanf("%d", &(*amGraph)->arcs[i][j]);
            if ((*amGraph)->arcs[i][j] == 1) {
                (*amGraph)->arcnum++;
            }
        }
    }
    (*amGraph)->arcnum /= 2;

}

void creatAdjacencyList(AMGraph *amGraph, AdjList adjList) {
    for (int i = 0; i < amGraph->vexnum; ++i) {
        adjList[i].vex = amGraph->vexs[i];
        adjList[i].firstedge = NULL;
        EdgeNode *moveNode = NULL;
        for (int j = 0; j < amGraph->vexnum; ++j) {
            //下面就是创建链表的过程，只是在第一个的时候相当于创建头节点
            if (amGraph->arcs[i][j] == 1) {//=1说明连同
                if (adjList[i].firstedge == NULL) {
                    adjList[i].firstedge=(EdgeNode *)malloc(sizeof (struct node));
                    adjList[i].firstedge->adjvex = j;
                    adjList[i].firstedge->next=NULL;
                    moveNode = adjList[i].firstedge;
                } else {
                    EdgeNode *tem=(EdgeNode*)malloc(sizeof(EdgeNode));
                    tem->adjvex=j;
                    tem->next=NULL;
                    moveNode->next=tem;
                    moveNode=moveNode->next;
                }
            }
        }
    }
}

//邻接矩阵
/*void DFS(AMGraph *amGraph, int visited[],int sub) {
    printf("%c",amGraph->vexs[sub]);
    visited[sub]=1;
    for (int i = 0; i < amGraph->vexnum; ++i) {
        if (amGraph->arcs[sub][i]!=0&&visited[i]==0){
            DFS(amGraph,visited,i);
        }
    }
}*/


//邻接表
void BFS(AdjList adjList,int ints[],int sub){
    if(adjList[sub].vex==0){
        return;
    }
    if(ints[sub]==0){
        printf("%c",adjList[sub].vex);
        ints[sub]=1;
    }
    EdgeNode *moveNode=adjList[sub].firstedge;
    while(moveNode!=NULL){
        if(ints[moveNode->adjvex]==0){
            printf("%c",adjList[moveNode->adjvex].vex);
            ints[moveNode->adjvex]=1;
        }
        moveNode=moveNode->next;
    }
    BFS(adjList,ints,sub+1);
}
int main() {
    AMGraph *amGraph;//邻接表
    AdjList adjList={0};//邻接表的点集合，全部初始化
    int num;
    printf("input the number of node: ");
    scanf("%d",&num);
    int* ints = (int*)malloc(sizeof (int)*num);//在搜索中，记录是否别查看
    for (int i = 0; i < num; ++i) {
        *(ints+i)=0;
    }
    creatGraph(&amGraph,num);//创建邻接矩阵
    creatAdjacencyList(amGraph,adjList);//创建邻接表
    BFS(adjList,ints,0);
    return 0;
}



总结

两种算法的比较

图的应用

最小生成树

  1. 概念回顾

    • 生成树

      所有的顶点，均有边连接起来，不存在回路；也就是全部顶点，部分边

  2. 最小生成树

  3. 构造最小数生成树

    • MST性质：设N=(V,E)是一个连通的网，存在一个U是顶点集V的非空子集。若边（u,v）是一条具有最小权值的边，其中u包含于U,v包含于V，则一定存在一个最小生成树，包含边（u,v）

    • 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
      #include <iostream>
            
      #define MaxInt 32767   //有向表的正无穷
      #define MVNum 100       //最大定点数
      typedef char VerTexType;   //定点的类型
      typedef int ArcType;      //权值
            
            
      struct AMGraph {
          VerTexType vexs[MVNum];   //顶点表
          ArcType arcs[MVNum][MVNum];   //邻接矩阵
          int vexnum, arcnum;//图的当前点数和边的数目
          AMGraph(int vex, int arc) : vexnum(vex), arcnum(arc) {}
            
          AMGraph() : vexnum(0), arcnum(0) {}
      };
            
            
      void CreatGraph(AMGraph &amGraph, int num) {
          amGraph.vexnum = num;
          //给节点赋值
          for (int i = 0; i < num; ++i) {
              amGraph.vexs[i] = i + 'A';
          }
          //初始化，获得邻接矩阵
          for (int i = 0; i < num; ++i) {
              for (int j = 0; j < num; ++j) {
                  std::cin >> amGraph.arcs[i][j];
                  if (amGraph.arcs[i][j] != MaxInt && amGraph.arcs[i][j] != 0) {
                      amGraph.arcnum++;
                  }
              }
          }
      }
            
      void CreatemMinimalSpanningTree(AMGraph &amGraph) {
          //初始化
          int minSub = 0;
          int minWeight;
          int weight[MVNum]{0};
          int i = 0, j = 0;
          int correlativeSub[MVNum]{0};
            
          //将第一个点的相关的权值记录下来
          for (i = 0; i < amGraph.vexnum; ++i) {
              weight[i] = amGraph.arcs[minSub][i];
          }
          std::cout << "the begin point is: " << amGraph.vexs[minSub] << std::endl;
            
          //最小生成树
          for (i = 1; i < amGraph.vexnum; ++i) {
              minWeight = MaxInt;
            
              //找到最小的值和权值，记录这个点,更新minWeight
              for (j = 1; j < amGraph.vexnum; ++j) {
                  if (weight[j] < minWeight && weight[j] != 0) {
                      minWeight = weight[j];
                      minSub = j;
                  }
              }
            
            
              std::cout << "( " << amGraph.vexs[correlativeSub[minSub]] << "  " << amGraph.vexs[minSub] << " )   point is： "
                        << amGraph.vexs[minSub] << "   weight is: " << minWeight << std::endl;
              weight[minSub] = 0;//防止再次调用
            
              //更新weight[]
              for (j = 1; j < amGraph.vexnum; ++j) {
                  if (weight[j] > amGraph.arcs[i][j] && weight[j] != 0) {
                      weight[j] = amGraph.arcs[i][j];
                      correlativeSub[j] = minSub;
                  }
              }
          }
      }
            
      int main() {
          int nodeNum;
          std::cout << "input your nodeNum: ";
          std::cin >> nodeNum;
          AMGraph amGraph{0, 0};
          CreatGraph(amGraph, nodeNum);
          //实现最小生树
          CreatemMinimalSpanningTree(amGraph);
          return 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
      #include <iostream>
      #include <vector>
      #include <algorithm>
            
      #define MaxInt 32767   //有向表的正无穷
      #define MVNum 100       //最大定点数
      typedef char VerTexType;   //定点的类型
      typedef int ArcType;      //权值
            
            
      struct AMGraph {
          VerTexType vexs[MVNum];   //顶点表
          ArcType arcs[MVNum][MVNum];   //邻接矩阵
          int vexnum, arcnum;//图的当前点数和边的数目
          AMGraph(int vex, int arc) : vexnum(vex), arcnum(arc) {}
            
          AMGraph() : vexnum(0), arcnum(0) {}
      };
            
      struct Edge {
          int begin;
          int end;
          int weight;
      };
            
      void CreatGraph(AMGraph &amGraph, int num) {
          amGraph.vexnum = num;
          //给节点赋值
          for (int i = 0; i < num; ++i) {
              amGraph.vexs[i] = i + 'A';
          }
          //初始化，获得邻接矩阵
          for (int i = 0; i < num; ++i) {
              for (int j = 0; j < num; ++j) {
                  std::cin >> amGraph.arcs[i][j];
                  if (amGraph.arcs[i][j] != MaxInt && amGraph.arcs[i][j] != 0) {
                      amGraph.arcnum++;
                  }
              }
          }
      }
            
      void GetEdges(AMGraph &amGraph, std::vector<Edge> &edges) {
          for (int i = 0; i < amGraph.vexnum; ++i) {
              for (int j = i + 1; j < amGraph.vexnum; ++j) {
                  Edge edge;
                  edge.begin = i;
                  edge.end = j;
                  edge.weight = amGraph.arcs[i][j];
                  edges.emplace_back(edge);
              }
          }
            
          std::sort(edges.begin(), edges.end(), [](Edge a, Edge b) {
              return a.weight < b.weight;
          });
      }
            
      int find(std::vector<int> &sub, int begin) {
          while (sub[begin] > 0) {
              begin = sub[begin];//找到是否连成了闭环
          }
          return begin;
      }
            
      void CreateMinimalSpanningTree(AMGraph &amGraph) {
          std::vector<Edge> edges;
          GetEdges(amGraph, edges);
          std::vector<int> sub(amGraph.vexnum, 0);
            
          int beginSub, endSub;
          for (const auto &item: edges) {
              beginSub = find(sub, item.begin);
              endSub = find(sub, item.end);
              if (beginSub != endSub) {
                  sub[beginSub]=endSub;
                  std::cout << "( " << beginSub << "  " << endSub << " )   " << amGraph.vexs[beginSub] << " --> "
                            << amGraph.vexs[endSub] << "  weight: "<<item.weight<< std::endl;
              }
          }
      }
            
             
      int main() {
          int nodeNum;
          std::cout << "input your nodeNum: ";
          std::cin >> nodeNum;
          AMGraph amGraph{0, 0};
          CreatGraph(amGraph, nodeNum);
          //实现最小生树
          CreateMinimalSpanningTree(amGraph);
          return 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
    #include <iostream>
    #include <vector>
    #include <algorithm>
      
    #define MaxInt 32767   //有向表的正无穷
    #define MVNum 100       //最大定点数
    typedef char VerTexType;   //定点的类型
    typedef int ArcType;      //权值
      
    struct AMGraph {
        VerTexType vexs[MVNum];   //顶点表
        ArcType arcs[MVNum][MVNum];   //邻接矩阵
        int vexnum, arcnum;//图的当前点数和边的数目
        AMGraph(int vex, int arc) : vexnum(vex), arcnum(arc) {}
      
        AMGraph() : vexnum(0), arcnum(0) {}
    };
      
      
    void CreatGraph(AMGraph &amGraph, int &num) {
        amGraph.vexnum = num;
        //给节点赋值
        for (int i = 0; i < num; ++i) {
            amGraph.vexs[i] = i + 'A';
        }
        //初始化，获得邻接矩阵
        for (int i = 0; i < num; ++i) {
            for (int j = 0; j < num; ++j) {
                std::cin >> amGraph.arcs[i][j];
                if (amGraph.arcs[i][j] != MaxInt && amGraph.arcs[i][j] != 0) {
                    amGraph.arcnum++;
                }
            }
        }
    }
      
    void CreatePairShortPath(AMGraph amGraph) {
        std::vector<int> sub(amGraph.vexnum);    //该点对应最短路径的前驱
        std::vector<int> weight(amGraph.vexnum); //从最开始的点到各个点的路径
        std::vector<bool> final(amGraph.vexnum);  //存放是否遍历
      
        //初始化
        for (int i = 0; i < amGraph.vexnum; ++i) {
            weight[i] = amGraph.arcs[0][i];;
            sub[i] = 0;
            final[i] = false;
        }
        //针对第一个点
        weight[0] = 0;
        final[0] = true;
      
        int min = MaxInt;
        int minSub = 0;//存放临时的最小的路径
        //最短路径
        for (int i = 0; i < amGraph.vexnum; ++i) {
            min = MaxInt;
            //找到到旁边一个点最近的路径
            for (int j = 0; j < amGraph.vexnum; ++j) {
                if (min > weight[j] && !final[j]) {
                    min = weight[j];
                    minSub = j;
                }
            }
      
            final[minSub] = true;
      
            //测试3个节点的关系
            for (int j = 0; j < amGraph.vexnum; ++j) {
                if (min + amGraph.arcs[minSub][j] < weight[j] && !final[j]) {
                    weight[j] = min + amGraph.arcs[minSub][j];
                    sub[j] = minSub;
                }
            }
      
        }
      
      
        std::sort(sub.begin(), sub.end(), [](int a, int b) {
            return a < b;
        });
      
        std::cout<<"\n\nthe shortest path:"<<std::endl;
        for (int i = 1; i < amGraph.vexnum; ++i) {
            std::cout << amGraph.vexs[sub[i]] << " --> " << amGraph.vexs[i] << "   now, the weight is: " << weight[i]<<std::endl;
        }
      
    }
      
    int main() {
        AMGraph amGraph;
        int size;
        std::cout << "please input size: ";
        std::cin >> size;
        CreatGraph(amGraph, size);
        CreatePairShortPath(amGraph);
        return 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
    #include <iostream>
    #include <vector>
    #include <algorithm>
        
    #define MaxInt 32767   //有向表的正无穷
    #define MVNum 100       //最大定点数
    typedef char VerTexType;   //定点的类型
    typedef int ArcType;      //权值
        
    struct AMGraph {
        VerTexType vexs[MVNum];   //顶点表
        ArcType arcs[MVNum][MVNum];   //邻接矩阵
        int vexnum, arcnum;//图的当前点数和边的数目
        AMGraph(int vex, int arc) : vexnum(vex), arcnum(arc) {}
        
        AMGraph() : vexnum(0), arcnum(0) {}
    };
        
        
    void CreatGraph(AMGraph &amGraph, int &num) {
        amGraph.vexnum = num;
        //给节点赋值
        for (int i = 0; i < num; ++i) {
            amGraph.vexs[i] = i + 'A';
        }
        //初始化，获得邻接矩阵
        for (int i = 0; i < num; ++i) {
            for (int j = 0; j < num; ++j) {
                std::cin >> amGraph.arcs[i][j];
                if (amGraph.arcs[i][j] != MaxInt && amGraph.arcs[i][j] != 0) {
                    amGraph.arcnum++;
                }
            }
        }
    }
        
    void CreatePairShortPath(AMGraph amGraph) {
        std::vector<std::vector<int>> weight;
        std::vector<std::vector<int>> sub;
        //初始化
        for (int i = 0; i < amGraph.vexnum; ++i) {
            std::vector<int> temSub;
            std::vector<int> temWei;
            for (int j = 0; j < amGraph.vexnum; ++j) {
                temWei.emplace_back(amGraph.arcs[i][j]);
                temSub.emplace_back(j);
            }
            weight.emplace_back(temWei);
            sub.emplace_back(temSub);
        }
        
        //核心代码
        //i:中间点
        //j:出发点
        //k:终点
        for (int i = 0; i < amGraph.vexnum; ++i) {
            for (int j = 0; j < amGraph.vexnum; ++j) {
                for (int k = 0; k < amGraph.vexnum; ++k) {
                    if (weight[j][k] > weight[j][i] + weight[i][k]) {
                        weight[j][k] = weight[j][i] + weight[i][k];
                        sub[j][k] = sub[j][i];
                    }
                }
            }
        }
        
        //A->D
        int beginSub = 0, endSub = 3;
        std::cout << "path: " << amGraph.vexs[beginSub] << "  ->  " << amGraph.vexs[endSub] << std::endl
                  << " and the weight is " << weight[beginSub][endSub] << std::endl;
        int kSub=sub[beginSub][endSub];
        std::cout<<amGraph.vexs[beginSub];
        while (kSub != endSub) {
            std::cout<<" -> "<<amGraph.vexs[kSub];
            kSub=sub[kSub][endSub];
        }
        std::cout<<" -> "<<amGraph.vexs[endSub]<<std::endl;
    }
        
    int main() {
        AMGraph amGraph;
        int size;
        std::cout << "please input size: ";
        std::cin >> size;
        CreatGraph(amGraph, size);
        CreatePairShortPath(amGraph);
        return 0;
    }

有向无环图

  1. AOV网 -> 拓扑排序问题

    使用一个有向图表示一个工程。定点表示活动 。使用弧长表示不同活动的先后关系

  2. AOE网 -> 关键路径问题

    使用弧表示活动，使用定点表示活动开始或者结束的事件

拓扑排序

  1. 用处：

    所有的顶点都在拓扑序列当中则说明是没有环，反之有环

  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
    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
    #include <iostream>
    #include <vector>
    #include <algorithm>
    #include <memory>
    #include <list>
    #include <stack>

    #define MaxInt 32767   //有向表的正无穷
    typedef char VerTexType;   //定点的类型
    typedef int ArcType;      //权值

    struct AMGraph {
        std::vector<VerTexType> vexs; //顶点表
        std::vector<std::vector<int>> arcs; //邻接矩阵
        int vexnum, arcnum;//图的当前点数和边的数目
        AMGraph(int vex, int arc) : vexnum(vex), arcnum(arc) {}

        AMGraph() : vexnum(0), arcnum(0) {}
    };

    struct Edge {
        VerTexType nextValue;
        int sub;
    };

    struct AdjacencyList {
        std::list<std::shared_ptr<Edge>> nextPoint;
        VerTexType vex;
        int in;
        AdjacencyList():vex('0'),in(0){}
    };


    void CreatGraph(AMGraph &amGraph, int &num) {
        amGraph.vexnum = num;
        //给节点赋值
        for (int i = 0; i < num; ++i) {
            amGraph.vexs.emplace_back(i + 'A');
        }
        for (int i = 0; i < num; ++i) {
            std::vector<int> vec;
            amGraph.arcs.emplace_back(vec);
            for (int j = 0; j < num; ++j) {
                int tem;
                std::cin >> tem;
                amGraph.arcs[i].emplace_back(tem);
                if(tem!=0&&tem!=MaxInt){
                    amGraph.arcnum++;
                }
            }
        }
    }


    void CreateAdjacencyList(const AMGraph &amGraph, std::vector<AdjacencyList>& adjacencyList) {
        for (int i = 0; i < amGraph.vexnum; ++i) {
            AdjacencyList tem;
            tem.vex=amGraph.vexs[i];
            adjacencyList.emplace_back(tem);
            for (int j = 0; j < amGraph.vexnum; ++j) {
                if(amGraph.arcs[i][j]!=0&&amGraph.arcs[i][j]!=MaxInt){
                    std::shared_ptr<Edge> pEdge(new Edge);
                    pEdge->sub=j;
                    pEdge->nextValue=amGraph.vexs[j];
                    adjacencyList[i].nextPoint.push_back(pEdge);
                }
            }
        }

        for (int i = 0; i < amGraph.vexnum; ++i) {
            for (int j = 0; j < amGraph.vexnum; ++j) {
                if(amGraph.arcs[i][j]!=0){  
                    adjacencyList[j].in++;
                }
            }
        }

    }

    bool SopologicalSort(std::vector<AdjacencyList>& adjacencyLists){
        std::stack<AdjacencyList> stack;
        for (int i = 0; i < adjacencyLists.size(); ++i) {
            if(adjacencyLists[i].in==0){
                stack.push(adjacencyLists[i]);
            }
        }
        int i=0;
        while(!stack.empty()){
            auto tem=stack.top();
            std::cout<<tem.vex<<"  ";
            i++;
            stack.pop();

            for(const auto &item:tem.nextPoint){
                if(!--adjacencyLists[item->sub].in){
                    stack.push(adjacencyLists[item->sub]);
                }
            }
        }

        std::cout<<std::endl<<"size: "<<i<<std::endl;
        if(i==adjacencyLists.size()){
            return true;
        }else {
            return false;
        }
    }


    int main() {
        AMGraph amGraph;  //图，以及邻接矩阵
        std::vector<AdjacencyList> adjacencyList;
        int size;
        std::cout<<"input size: "<<std::endl;
        std::cin >> size;
        CreatGraph(amGraph, size);
        CreateAdjacencyList(amGraph,adjacencyList);
        std::cout<<SopologicalSort(adjacencyList);
        return 0;
    }


关键路径

  1. 结点

    ve(i,j)表示事件i,j最早发生的时间

    vl(v,j)表示事情最迟的发生时间

  2. 边

    e(a3)表示活动最早的开始时间

    l(a3)表示活动最迟的开始时间

    l(a3)-e(a3)表示完成 a3的时间余量

    若e()==i()则说明是路径上关键活动

  3. 部分公式

    活动i发生的最早时间，等于时间j的最晚发生时间

    活动i最晚发生时间，等于k的最晚发生时间

  4. 求关键路径

#数据结构和算法
图
https://tsy244.github.io/2023/04/20/算法/数据结构/图/
Author
August Rosenberg
Posted on
April 20, 2023
Licensed under