前言：数据结构一般就四种关系：集合、线性、树、图。这篇文章打算对图这类数据结构做一个概览。先介绍图的一些术语（复制粘贴：））；然后讲解一下图的各种存储形式；最后把图的应用记录一下，具体应用算法放在算法分类里面。

一、图的一些术语

二、图存储

邻接矩阵

:::info 创建无向网 :::

#include<bits/stdc++.h>
using namespace std;
#define MVNum 100
#define MaxInt 32767
typedef char VerTexType;
typedef int ArcType;
/**
 * 邻接矩阵存储形式
 */
typedef struct {
    /* data */
    VerTexType vexs[MVNum]; //顶点表
    ArcType arcs[MVNum][MVNum]; //邻接矩阵
    int vexnum, arcnum; //图的当前顶点和边数
}AMGraph;
/**
 * 确定v在G中的位置，即顶点数组的下标
 */
int LocateVex(AMGraph &G, char v) {
    for (int i = 0; i < G.vexnum;i++) {
        if (v == G.vexs[i]){
            return i;
        }
    }
}
/**
 * 创建无向网
 * 如果创建无向图   
 */
void CreateUDN(AMGraph &G) {
    // 采用邻接矩阵表示法，创建无向图G
    cout << "请输入顶点数和边数：" << endl;
    cin >> G.vexnum >> G.arcnum; //输入顶点数和边数
    // 初始化顶点
    for (int i = 0; i < G.vexnum;i++){
        cout << "请输入第" << i << "个顶点值" << endl;
        cin >> G.vexs[i];
    }
    // 初始化邻接矩阵的边的权值为最大值
    for (int i = 0; i < G.vexnum;i++) {
        for (int j = 0; j < G.vexnum;j++) {
            G.arcs[i][j] = MaxInt;
        }
    }
    // 构造邻接矩阵
    for (int k = 0; k < G.arcnum;k++) {
        cout << "请输入每条边所依附的顶点和权值：" << endl;
        char v1, v2;
        int w; //一条边所依附的顶点和权值
        cin >> v1 >> v2 >> w;
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        G.arcs[i][j] = w;
        G.arcs[j][i] = w;
    }
}
void Display(AMGraph &G) {
    for (int i = 0; i < G.vexnum;i++) {
        for (int j = 0; j < G.vexnum;j++) {
            cout << G.arcs[i][j] << " ";
        }
        cout << endl;
    }
}
int main() {
    AMGraph test;
    // CreateUDN(test);
    Display(test);
}

:::tips 创建无向图 ::: 对CreateUDN 进行处理：

• G.arcs[i][j] = MaxInt;改为G.arcs[i][j] = 0;
• 将w改为常量1即可

:::tips 创建有向网 ::: 对CreateUDN 进行处理：

• 删除G.arcs[j][i] = w;

:::tips 创建有向图 ::: 对CreateUDN 进行处理：

• 删除G.arcs[j][i] = w;

  邻接表

  ```cpp

  include

  using namespace std;

define MVNum 100

define MaxInt 32767

typedef char VerTexType; typedef int OtherInfo;

/**

• 邻接表存储 */

/**

• 存储结构 / typedef struct ArcNode { //边结点
  int adjvex; //该边所指向的结点的位置 struct ArcNode nextarc; //指向下一条边的指针 OtherInfo info; //和边相关的其他信息 }ArcNode;

typedef struct VNode { //顶点信息 VerTexType data; //数据域，存放顶点vi的名称或其他有关信息 ArcNode *firstarc; //指向第一条依附该顶点的边的指针 }VNode, AdjList[MVNum]; //AdjList表示邻接表的类型

typedef struct { AdjList vertices; int vexnum, arcnum; //图当前的顶点数和边数 }ALGragh; //邻接表（Adjacency List）

/**

• 找到v顶点在图中的位置 */ int LocateVex(ALGragh &G, char v) { for (int i = 0; i < G.vexnum;i++) {

   if (v == G.vertices[i].data) {
       return i;
   }

  } }

/**

• 邻接表创建无向图 */ void CreateUDG(ALGragh &G) { cin >> G.vexnum >> G.arcnum; // 邻接表的顶点数和边数 for (int i = 0; i < G.vexnum;i++) {

   cin >> G.vertices[i].data;
   G.vertices[i].firstarc = NULL;

  }

  for (int k = 0; k < G.arcnum;k++) {

   char v1, v2;
   cin >> v1 >> v2;
   int i = LocateVex(G, v1);
   int j = LocateVex(G, v2);
   ArcNode *p1 = new ArcNode;
   p1->adjvex = j;
   p1->nextarc = G.vertices[i].firstarc;
   G.vertices[i].firstarc = p1;
   ArcNode *p2 = new ArcNode;
   p2->adjvex = i;
   p2->nextarc = G.vertices[j].firstarc;
   G.vertices[j].firstarc = p1;

  } } ```

  有向图：十字链表存储

  ```cpp

  include

  using namespace std; typedef int Status;

  define OK 1;

//——有向图的十字链表储存表示——

define MAX_VERTEX_NUM 20

typedef char VerTexType; typedef int InfoType; typedef struct ArcBox { int tailvex, headvex; //该弧的头尾和头顶点的位置 struct ArcBox hlink, tlink; //分别为弧头相同和弧尾相同的链域 InfoType *info; //该弧相关信息的指针 }ArcBox;

typedef struct VexNode { VerTexType data; ArcBox firstin, firstout; //分别指向该顶点的第一项入弧和出弧 }VexNode;

typedef struct { VexNode xlist[MAX_VERTEX_NUM]; //表头向量 int vexnum, arcnum; //有向图的当前顶点数和弧数 }OLGraph; //十字链表（Orthogonal List）

<a name="vsryl"></a>
### 无向图：邻接多重表存储
```cpp
#include <bits/stdc++.h>
using namespace std;
typedef int Status;
#define OK 1;
//----无向图的邻接多重表储存表示----
#define MAX_VERTEX_NUM 20
typedef char VerTexType;
typedef int InfoType;
typedef enum
{
    unvisited, visited                     //枚举unvisited是0，visited是1，注意没有分号
}VisitIf;
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, arcnum;                     //无向图当前的顶点数和边数
}AMLGraph;                                  //邻接多重表(Adjacency Multilist)

其他：边集数组

其他：链式前向星

三、图的应用

• 最小生成树
• 最短路径
• 环路
• 关键路径

具体这几类问题都是算法中的贪心算法所属，故将其放到算法分类里面了。