尼采般地抒情

尼采般地抒情

尼采般地抒情

音乐盒

站点信息

文章总数目: 311
已运行时间: 1518

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

一、图的一些术语

二、图存储

邻接矩阵

创建无向网


#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 &lt;&lt; &quot;请输入第&quot; &lt;&lt; i &lt;&lt; &quot;个顶点值&quot; &lt;&lt; endl;
      cin &gt;&gt; G.vexs[i];
    
    }
    // 初始化邻接矩阵的边的权值为最大值
    for (int i = 0; i < G.vexnum;i++) {
      for (int j = 0; j &lt; G.vexnum;j++) {
          G.arcs[i][j] = MaxInt;
      }
    
    }
    // 构造邻接矩阵
    for (int k = 0; k < G.arcnum;k++) {
      cout &lt;&lt; &quot;请输入每条边所依附的顶点和权值:&quot; &lt;&lt; endl;
      char v1, v2;
      int w; //一条边所依附的顶点和权值
      cin &gt;&gt; v1 &gt;&gt; v2 &gt;&gt; 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);
}


创建无向图

CreateUDN 进行处理:

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


创建有向网

CreateUDN 进行处理:

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


创建有向图

CreateUDN 进行处理:

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

邻接表

#include <bits/stdc++.h>
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 &gt;&gt; G.vertices[i].data;
      G.vertices[i].firstarc = NULL;
    
    } for (int k = 0; k < G.arcnum;k++) {
      char v1, v2;
      cin &gt;&gt; v1 &gt;&gt; v2;
      int i = LocateVex(G, v1);
      int j = LocateVex(G, v2);
      ArcNode *p1 = new ArcNode;
      p1-&gt;adjvex = j;
      p1-&gt;nextarc = G.vertices[i].firstarc;
      G.vertices[i].firstarc = p1;
      ArcNode *p2 = new ArcNode;
      p2-&gt;adjvex = i;
      p2-&gt;nextarc = G.vertices[j].firstarc;
      G.vertices[j].firstarc = p1;
    
    }
    }

有向图:十字链表存储

#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 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)

无向图:邻接多重表存储

#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)

其他:边集数组


其他:链式前向星


三、图的应用

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


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






评论区