图

线性结构----一对一，每个结点至多有一个前驱和一个后驱

树形结构----一对多，每个结点最多有一个前驱，可以有多个后继

图形结构----多对多，每个结点可以有多个前驱和多个后继

图 G=(V,E)【Graph(Vertex,Edge)】

V：顶点的集合，是有穷且非空，如果没有顶点可以认为是空图

E：边的有穷集合

图里边可以只有点，没有边

###有向图和无向图

图中有方向的图称为有向图

图中没有方向的图称为无向图

边也称为弧，因此有很少边或者很少弧的图称为稀疏图，即达到$ E<nlogn$,其中，n是顶点的个数

与稀疏图相对应的是稠密图

边或者弧带有权值的图称为网

边/弧与顶点之间的关系关联(依附)

度

**顶点的度:**与该顶点相关联的边的数目，记为$td(v)$

在有向图中，又分为入度和出度，有向图的度=入度+出度

顶点v的入度是指以v为终点的有向边的条数(到达v的)

顶点v的出度是指以v为起点的有向边的条数(v发出的)

邻接

如果两个顶点有边/弧相连，那么这两个点是邻接的

存在$(v_i,v_j)$则代表$v_i$和$v_j$是互为邻接点()代表是无向图之间的关系

存在$<v_i,v_j>$则代表$v_i$邻接到$v_j$以及表$v_j$邻接与$v_i$<>代表有向图之间的关系

完全图

图中任意两个顶点都有边相连的图称为完全图

完全图又分为有向完全图和无向完全图

当有向图仅一个顶点的入度为0，其余结点入度均为1，出度的个数没有限制，此时该图的形状为树

路径

若干条连续的边构成顶点的序列（就是写出从一个点到另一个点所经过的点）

路径长度：路径上的所有的边/弧的数目或者权值之和

回路（环）：第一个顶点和最后一个顶点路径相同

简单路径：除了终点起点可以相同，其他点都不同

简单回路（简单环）：除了终点起点相同，其他点都不同

连通图（强连通图）

在一个无(有)向图中，所有的路径都是连在一块（即从一点，可以到达图上任意一点）则该图为连通图（强连通图）

强联通图里必须有进有出才算连通的

权和网

图中的线/弧中的数字叫做权

带权的图称为网

子图

一个图属于另一个的一部分，那么这个图是另一个图的子图

连通分量(强连通分量)

图（该图不一定是完全图）的极大联通子图叫做联通分量

极大联通子图：顶点数已经最大了，再加入子图不再连通

极小连通子图

从该子图删除一条边后，子图不再连通

生成树

包含了所有顶点的极小连通子图

图的存储结构

ADT

createGraph()//创建图，生成一个空图
getVex()//求顶点的值
DFS()//若图存在，对图进行深度优先搜索遍历
BFS()//若图存在，则对图进行广度优先搜索遍历

使用二维数组存储

使用二维数组存储的方法叫做数组表示法或者邻接矩阵法

也可用链表来存储，但不知道有几个前驱结点和后继结点，因此表示起来没有那么方便

存储方式

建立一个顶点表vexs（记录各个顶点信息，一维数组）和一个邻接矩阵arcs（表示各个顶点的关系）相当于边，可以理解为两个顶点的关系

设一个有n个结点的图，顶点表是大小为n的一维数组，邻接矩阵是大小为n行n列的二维数组

所以有$$arcs[i][j]=
\begin

0& \text{两点不存在}
\end1& \text{<i,j>存在或者(i,j)存在，即两个点有连线}\$$

邻接矩阵左对角线上都为0，自己和自己的关系，无向图的矩阵是对称的（以左对角线为基准）

某个点的度可以看改点一行中矩阵为1的个数

完全图的邻接矩阵除了左对角线，其余的都是1

有向图的邻接矩阵每一行的1代表这个节点的出度边个数，每一列代表入度边的个数

网的邻接矩阵

$arcs[i][j]=
\begin

无穷& \text{两点不存在}
\end数值& \text{存在或者<i,j>存在，即两个点有连线,记录权值}\$

无穷可以用limits.h中的各个类型的最大值表示

邻接矩阵建立

定义邻接矩阵

typedef struct
{
    elementType vexs[maxSize];//顶点表
    arcType arcs[maxSize][maxSize];//权值类型，可以用bool等
    int vexNum,arcNum;//记录点数和边数
}graph;

无向网的建立

1. 输入总的顶点数和边数
2. 输入顶点的信息，存入顶点表
3. 初始化无向矩阵，使每个值都初始化为最大值
4. 构造邻接矩阵，有边的地方设置权值，无边的地方无需设置

int posG(graph *g,int n)//查找顶点位置
{
    for(int i=0;i<g->vexNum;i++)
    {
        if(g->vexs[i]==n)
            return i;
    }
    return -1;
}
void create(graph *g)
{
    scanf("%d%d",&g->vexNum,&g->arcNum);//输入总顶点数和总边数
    for(int i=0;i<g->vexNum;i++)
        scanf("%d",&g->vexs[i]);//输入每个顶点信息
    for(int i=0;i<vexs;i++)
        for(int j=0;j<vexs;j++)
            arcs[i][j]=INT_MAX;//所有元素赋值为无穷大
    int v1,v2,w;
    for(int k=0;k<vexs;k++)
    {
        scanf("%d%d%d",&v1,&v2,&w);//输入顶点，权值
        int i=posG(g,v1);//获取位置
        int j=posG(g,v2);
        g->arcs[i][j]=g->arcs[j][i]=w;//无向网也是关于左对角线对称的，因此只用一句给两个边赋值
    }
}

无向图使用邻接矩阵初始化时置为0

有向望构造时只建立一条（24行需要修改为g->arcs[i][j]=w）

优缺点

优点：

1. 直观、简单、好理解
2. 方便检查任意两点是否有边
3. 方便找任意一点的邻接点
4. 计算度比较方便
5. 适合存稠密图

缺点：

1. 不便于增加删除结点
2. 若边的个数非常少，空间复杂度为O($n^2$)
3. 如果存储的是稀疏图的话，会有大量的无效元素

邻接表表示法（链式）

图的链式存储结构又称为邻接表

结构定义

typedef struct
{
    int pos;//存放边指向元素的下标
    elementType info;//如果该图为网，则再增加一个权值的域
    struct arc *nextArc;//指向下一条边
}arc;
typedef struct
{
    elementType data;
    arc *firstArc;//存放第一条边的首地址
}vex;//定义数据存放结构
typedef struct
{
    vex g[maxSize];
    int vexNum,arcNum;//点数和边数
}graph;

特点

1. 邻接表不唯一，在存储边时，边的位置的顺序是可变的
2. 适宜存储稀疏图
3. 对于无向图 求度时，只需要求表结点的个数
4. 对于无向图，不方便求度
5. 对于两个节点是否存在着边，查找时比较麻烦
6. 有向图的邻接表存储时只存储发出的边（出度）或者进入的边（入度），当存储入度边时，该邻接表称为逆邻接表
7. 有向图的邻接表计算入度需要遍历整个邻接表，所以不是很方便，出度为该顶点出度的个数

邻接表的操作

1. 输入总的顶点数和边数

2. 建立顶点表

   • 依次将输入的信息存入到顶点表中
   • 使每个表头指针初始化为NULL

3. 创建邻接表

   • 依次输入两个顶点
   • 确定下标i和j，建立边结点
   • 分别将结点插入到头部

int findPos(int n,graph g)
{
    for(int i=0;i<g->vexNum;i++)
        if(g->vex[i]==n)
            return i;
    return -1;
}
create(graph *g)
{
    scanf("%d%d",&g->vexNum,&g->arcNum);//输入顶点数和边数
    for(int i=0;i<g->vexNum;i++)
    {
        scanf("%d",&g->g[i].data);//输入顶点
        g->g[i].firstArc=NULL;
    }
    for(int k=0;k<g->arcNum;k++)
    {
        int v1,v2;
        scanf("%d%d",&v1,&v2);
        int i=findPos(v1);
        int j=findPos(v2);
        
        //插入i的一端
        arc *e=malloc(sizeof(arc));
        e->pos=j;//存储坐标
        e->nextArc=g->g[i].firstArc;//头插法
        g->g[i].first=e;
        
        //插入到j的一端
        *e=malloc(sizeof(arc));
        e->pos=i;//存储坐标
        e->nextArc=g->g[j].firstArc;//头插法
        g->g[j].first=e;
        
    }
}

邻接表(数组)

首先需要3个数组，第一个数组存储每个节点的头，第二个数组存储每个节点的值，第三个数组存储每个节点的next指针

头指针数组是单独存在的一个数组，存储着指向的第一条边的值，为-1时就代表没有边与此点相连，第一条边的指针域中存储着与该点相连的第二条边，以此类推，即将所有与该点相连的点串成一个串，例如下标为1的头指针就代表下标为1的元素指向的第一条边

存储结构为$$\begin



\end头指针数组，保存着指向的第一条边\边的下一个指向的值，因为要串成串\值，该值用一个游标存储\游标，作用是存储下标处的值、该处的指向的下一个下标、头节点指向的该处$$

其中的2、3可以放在一起，一个是数据域，一个是指针域

以上结构等价于

struct
{
	element data,*next
}vex
struct
{
	vex[maxSize]
	idx-游标
}g

插入时采用头插法，需要更改头指针的后续元素，因为头指针是一个特殊的元素

插入过程

add(int v1,int v2)
{
	g.vex[g.idx].data=v2;
	g.vex[g.idx].next=head[v1];
	g.head[v1]=g.idx++;
}

遍历过程

void dfs(int next)
{
	visited[i]=1;
	for(int i=g.head[next];i!=-1;i=g.vex[i].next)
	{
		int pos=g.vex[i].pos;
		if(!visited[pos])
		{
			dfs(pos);
		}
	}
}

十字链表法

在邻接表中，只能存储入度或者是出度，在这种方法中求度比较困难，因此，可以同时存储出度和入度以达到效果（将邻接表和逆邻接表结合起来），这种方法称为十字链表

typedef struct
{
    int posTail;//出度顶点（发出的，弧尾
    int posHead;//入度顶点（到达的，弧头
    struct arc *nextTailArc;//存储弧尾相同的
    struct arc *nextHeadArc;//存储弧头相同的
}arc;//边

typedef struct
{
    int data;
    arc *firstHead;
    arc *firstTail;
}vex;//顶点

typedef struct 
{
    vex g[maxSize];
    int arcNum,vexNum;
}

邻接多重表

在邻接表中存储无向图时，每条边要存储两次，比较浪费空间，可以值存储一次，该方式是邻接多重表，解决的是每条边存储两次的问题

两条边只记录一遍

typedef struct
{
    mark
}arc;
typedef struct
{
    int data;
    arc *firstArc;
}vex;

图的遍历

从给定的连通图的一个顶点出发，沿着一些边访问所有的顶点，且每个顶点只能被访问一次，就称为图的遍历，是图的基本运算。

遍历的实质是找邻接点进行访问

图中可能存在回路，任意一个顶点都可能与其他顶点相通，访问完某个顶点后可能又回到曾经访问过的顶点

可以设置一个数组visited[N]，用来标记每个顶点是否被访问过了

• 初始化状态为0
• 访问过后置为1，避免多次访问

深度优先搜索(Depth First Serach-DFS)

步骤

1. 若前方有未访问过的顶点，则一直往前走
2. 如果无路可走(前方的都访问过了)，就直接返回上一顶点，继续执行步骤1
3. 如果返回到了起始顶点，代表访问结束

有点类似树的先序遍历

邻接矩阵

设置一个辅助数组visited[N]

void dfs(int pos, graph *g)
{
    visit(g->data[pos]);//访问
    visited[pos] = 1;
    for (int j = 0; j < g->arcNum; j++)
    {
        if (g->arcs[pos][j] == 1 && !visited[j])//将邻接表和辅助数组结合起来进行判断，如果为真，就代表该点与顶点pos相连且没有被访问过
            dfs(j, g);
    }
}

//如果该图不是连通图，则还可以加一个函数

void dfsT(graph *g)
{
    for(int i=0;i<g->vexNum;i++)
        if(!visited[i])
        	dfs(i,g);//若为为连通图，该语句只执行一次
}

完整代码

#include<stdio.h>

#define N 100
typedef struct
{
    int data[N];
    int arcs[N][N];
    int arcNum, vexNum;
} graph;

int visited[N];

void visit(int p)
{
    printf(" %d ", p);
}

void dfs(int pos, graph *g)
{
    visit(g->data[pos]);
    visited[pos] = 1;
    for (int j = 0; j < g->arcNum; j++)
    {
        if (g->arcs[pos][j] == 1 && !visited[j])
            dfs(j, g);
    }
}

int findPos(int n, graph *g)
{
    for (int i = 0; i < g->arcNum; i++)
        if (g->data[i] == n)
            return i;
    return -1;
}

void create(graph *g)
{
    printf("Please enter the number of vertices:");
    scanf("%d", &g->vexNum);
    printf("Please enter the number of sides:");
    scanf("%d", &g->arcNum);
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("Please enter the %d vertex:", i + 1);
        scanf("%d", &g->data[i]);
        visited[i]=0;
    }
    for (int i = 0; i < g->arcNum; i++)
    {
        int v1, v2;
        printf("Please enter the two vertices connected by edge %d:", i + 1);
        scanf("%d%d", &v1, &v2);

        int ii=findPos(v1,g);
        int jj=findPos(v2,g);
        g->arcs[ii][jj]=g->arcs[jj][ii]=1;
    }
}

int main()
{
    graph g;
    create(&g);
    puts("");
    puts("");
    puts("");
    dfs(2,&g);
    return 0;
}

邻接表

遍历方法是遍历顶点->下一个顶点->它的下一个顶点的下一个顶点...该步访问完后，在访问它的下一个顶点后边连着的边

void dfs(graph *g, int n)
{
    visit(g->g[n].data);
    visited[n] = 1;

    arc *p = g->g[n].firstArc;//边
    while (p)
    {
        if (!visited[p->pos])
            dfs(g, p->pos);
        p=p->arcNext;
    }
}
//非连通图
void dfsT(graph *g)
{
    for(int i=0;i<g->vexNum;i++)
        if(!visited[i])
            dfs(g,i);
}

完整代码

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

#define N 100
typedef struct
{
    int pos;
    struct arc *arcNext;
} arc;
typedef struct
{
    int data;
    arc *firstArc;
} vex;
typedef struct
{
    vex g[N];
    int arcNum, vexNum;
} graph;
int visited[N];

void visit(int p)
{
    printf(" %d ", p);
}

int findPos(graph *g, int n)
{
    for (int i = 0; i < g->vexNum; i++)
        if (g->g[i].data == n)
            return i;
    return -1;
}

void create(graph *g)
{
    printf("Please enter the number of vertices:");
    scanf("%d", &g->vexNum);
    printf("Please enter the number of sides:");
    scanf("%d", &g->arcNum);

    for (int i = 0; i < g->vexNum; i++)
    {
        printf("Please enter the %d vertex:", i + 1);
        scanf("%d", &g->g[i].data);
        g->g[i].firstArc = NULL;
    }

    for (int i = 0; i < g->arcNum; i++)
    {
        int v1, v2;
        printf("Please enter the %d side:", i + 1);
        scanf("%d%d", &v1, &v2);
        int ii=findPos(g,v1);
        int jj=findPos(g,v2);

        arc *p = malloc(sizeof(arc));
        p->pos = ii;
        p->arcNext = g->g[jj].firstArc;
        g->g[jj].firstArc = p;

        p = malloc(sizeof(arc));
        p->pos = jj;
        p->arcNext = g->g[ii].firstArc;
        g->g[ii].firstArc = p;
    }
}

void dfs(graph *g, int n)
{
    visit(g->g[n].data);
    visited[n] = 1;

    arc *p = g->g[n].firstArc;
    while (p)
    {
        if (!visited[p->pos])
            dfs(g, p->pos);
        p=p->arcNext;
    }
}

int main()
{
    graph g;
    create(&g);
    puts("");
    puts("");
    puts("");
    dfs(&g,0);
    return 0;
}

广度优先搜索(Breadth First Serach-BFS)

方法

从某一顶点出发，依次访问与其相连的顶点，并再从被访问的顶点出发，继续依次访问与其相连的顶点，重复该过程，直到全部被访问

也是需要一个visited[N]作为是否被访问过的一个标记

类似于树的层次优先遍历

也是使用队列实现

邻接矩阵

队列

void createQueue(queue *q)
{
    q->front=q->rear=0;
}

void enQueue(queue *q,int n)
{
    q->v[q->rear]=n;
    q->rear=(q->rear+1)%N;
}
void deQueue(queue *q,int *i)
{
    visit(q->v[q->front]);
    *i=q->v[q->front];
    q->front=(q->front+1)%N;
}
bool theQueueIsEmpty(queue *q)
{
    return q->front==q->rear;
}

搜索语句

void bfs(graph *g)
{
    queue q;
    createQueue(&q);
    for(int i=0;i<g->vexNum;i++)
    {
        if(!visited[i])
        {
            enQueue(&q,g->data[i]);
            visited[i]=1;
            while(!theQueueIsEmpty(&q))
            {
                deQueue(&q,&i);
                i=foundLocation(g,i);
                for(int j=0;j<g->vexNum;j++)
                {
                    if(!visited[j]&&g->arc[i][j]==1)
                    {
                        visited[j]=1;
                        enQueue(&q,g->data[j]);
                    }
                }
            }
        }

    }
}

入队的是下标

void bfs(graph g)
{
    queue<int> q;
    q.push(0);
    visited2[0]=1;
    while (!q.empty())
    {
        int now = q.front();
        printf("%d->", g.vex[now]);
        q.pop();
        for (int i = 0; i < g.vexNum; i++)
        {
            if (!visited2[i] && g.arc[now][i])
            {
                q.push(i);
                visited2[i]=1;
            }

        }
    }
}

广搜获取最大的深度（层次）

原理是当每一层入队结束后就计数

int bfs(int nn)
{
    int cnt = 0, last = nn, tail;
    queue<int> q;
    q.push(nn);
    visited[nn] = 1;
    while (!q.empty())
    {
        int now = q.front();//每次出队的元素
        q.pop();
        for (int i = 0; i < n; i++)
        {
            if (!visited[i] && arc[now][i])
            {
                q.push(i);
                visited[i] = 1;
                tail = i;//每次指向入队的元素
            }
        }
        if (now == last)//每出队一次就判断一次，当出队的元素与上一层最后入队的元素相等 就代表该层执行完毕，就执行下列语句
        {
            last = tail;
            cnt++;
        }
    }
    return cnt;
}

完整代码

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

#define N 100
int visited[N];
typedef struct
{
    int data[N];
    int arc[N][N];
    int vexNum,arcNum;
}graph;
int foundLocation(graph *g, int n)
{
    for (int i = 0; i < g->vexNum; i++)
        if (g->data[i] == n)
            return i;
    return -1;
}

void create(graph *g)
{
    printf("Please enter the number of vertices and edges:");
    scanf("%d%d", &g->vexNum, &g->arcNum);
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            g->arc[i][j]=0;
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("Please enter the value of the %d vertex", i + 1);
        scanf("%d", &g->data[i]);
        visited[i]=0;
    }
    for (int i = 0; i < g->arcNum; i++)
    {
        int v1, v2;
        printf("Please enter the %dth two connected vertices:", i + 1);
        scanf("%d%d", &v1, &v2);
        int ii=foundLocation(g,v1);
        int jj=foundLocation(g,v2);
        g->arc[ii][jj]=g->arc[jj][ii]=1;
    }
}
void visit(int n)
{
    printf(" %d ",n);
}
void dfs(graph *g,int n)
{
    visit(g->data[n]);
    visited[n]=1;
    for(int i=0;i<g->arcNum;i++)
    {
        if(!visited[i]&&g->arc[n][i]==1)
            dfs(g,i);
    }
}
typedef struct
{
    int v[N];
    int front,rear;
}queue;

void createQueue(queue *q)
{
    q->front=q->rear=0;
}

void enQueue(queue *q,int n)
{
    q->v[q->rear]=n;//入队的是值，而不是下标
    q->rear=(q->rear+1)%N;
}
void deQueue(queue *q,int *i)
{
    visit(q->v[q->front]);
    *i=q->v[q->front];
    q->front=(q->front+1)%N;
}
bool theQueueIsEmpty(queue *q)
{
    return q->front==q->rear;
}
void bfs(graph *g)
{
    queue q;
    createQueue(&q);
    for(int i=0;i<g->vexNum;i++)
    {
        if(!visited[i])
        {
            enQueue(&q,g->data[i]);
            visited[i]=1;
            while(!theQueueIsEmpty(&q))
            {
                deQueue(&q,&i);
                i=foundLocation(g,i);
                for(int j=0;j<g->vexNum;j++)
                {
                    if(!visited[j]&&g->arc[i][j]==1)
                    {
                        visited[j]=1;
                        enQueue(&q,g->data[j]);
                    }
                }
            }
        }

    }
}
int main()
{
    graph g;
    create(&g);
    puts("");
    puts("");
    puts("");
    //dfs(&g, 0);
    bfs(&g);
    return 0;
}

DFS与BFS完整代码

#include<bits/stdc++.h>

using namespace std;
const int N = 100;
typedef struct
{
    int vex[N], arc[N][N];
    int vexNum, arcNum;
} graph;

int findVex(graph *g, int v)
{
    for (int i = 0; i < g->vexNum; i++)
        if (g->vex[i] == v)
            return i;
    return -1;
};

void create(graph *g)
{
    printf("Please input the number of vex and arc:");
    scanf("%d%d", &g->vexNum, &g->arcNum);
    for (int i = 0; i < g->vexNum; i++)
        for (int j = 0; j < g->vexNum; j++)
            g->arc[i][j] = 0;
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("Please input %d th vex:", i + 1);
        scanf("%d", &g->vex[i]);
    }
    for (int i = 0; i < g->arcNum; i++)
    {
        int v1, v2;
        printf("Please input %d th arc", i + 1);
        scanf("%d%d", &v1, &v2);
        int link1 = findVex(g, v1);
        int link2 = findVex(g, v2);
        g->arc[link1][link2] = g->arc[link2][link1] = 1;
    }
}

int visited[N];

void dfs(graph g, int vex)
{
    printf("%d->", g.vex[vex]);
    visited[vex] = 1;
    for (int i = 0; i < g.vexNum; i++)
    {
        if (!visited[i] && g.arc[vex][i])
            dfs(g, i);
    }
}

int visited2[N];

void bfs(graph g)
{
    queue<int> q;
    q.push(0);
    visited2[0]=1;
    while (!q.empty())
    {
        int now = q.front();
        printf("%d->", g.vex[now]);
        q.pop();
        for (int i = 0; i < g.vexNum; i++)
        {
            if (!visited2[i] && g.arc[now][i])
            {
                q.push(i);
                visited2[i]=1;
            }

        }
    }
}

int main()
{
    graph g;
    create(&g);
    dfs(g, 0);
    cout<<endl;
    bfs(g);
    return 0;
}

###邻接表

队列

typedef struct
{
    vex v[N];
    int front,rear;
}queue;

void createQueue(queue *q)
{
    q->front=q->rear=0;
}

void enQueue(queue *q,vex n)
{
    q->v[q->rear]=n;
    q->rear=(q->rear+1)%N;
}
void deQueue(queue *q)
{
    visit(q->v[q->front].data);
    q->front=(q->front+1)%N;
}
bool theQueueIsEmpty(queue *q)
{
    return q->front==q->rear;
}

搜索语句

void bfs(graph *g)
{
    queue q;
    createQueue(&q);//初始化队列
    for(int i=0;i<g->vexNum;i++)
    {
        if(!visited[i])
        {
            enQueue(&q,g->g[i]);//首先入队
            visited[i]=1;
            arc *p;//用来存储每个顶点的第一条边
            while(!theQueueIsEmpty(&q))//队列为空时代表结束
            {
                p=q.v[q.front].firstArc;//将顶点的第一条边赋给p
                deQueue(&q);//出队
                while(p)
                {
                    if(!visited[p->pos])
                    {
                        enQueue(&q,g->g[p->pos]);//将每个顶点指向的顶点依次入队
                        visited[p->pos]=1;
                    }
                    p=p->nextArc;
                }
            }
        }
    }
}

完整代码

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

#define N 100
int visited[N];
typedef struct
{
    int pos;
    struct arc *nextArc;
} arc;
typedef struct
{
    int data;
    arc *firstArc;
} vex;
typedef struct
{
    vex g[N];
    int vexNum, arcNum;
} graph;

int foundLocation(graph *g, int n)
{
    for (int i = 0; i < g->vexNum; i++)
        if (g->g[i].data == n)
            return i;
    return -1;
}

void create(graph *g)
{
    printf("Please enter the number of vertices and edges:");
    scanf("%d%d", &g->vexNum, &g->arcNum);
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("Please enter the value of the %d vertex", i + 1);
        scanf("%d", &g->g[i]);
        g->g[i].firstArc = NULL;
        visited[i] = 0;
    }
    for (int i = 0; i < g->arcNum; i++)
    {
        int v1, v2;
        printf("Please enter the %dth two connected vertices:", i + 1);
        scanf("%d%d", &v1, &v2);
        int ii=foundLocation(g,v1);
        int jj=foundLocation(g,v2);

        arc *p=malloc(sizeof(arc));
        p->pos=ii;
        p->nextArc=g->g[jj].firstArc;
        g->g[jj].firstArc=p;

        p=malloc(sizeof(arc));
        p->pos=jj;
        p->nextArc=g->g[ii].firstArc;
        g->g[ii].firstArc=p;
    }
}
void visit(int n)
{
    printf(" %d ",n);
}
void dfs(graph *g,int n)
{
    visit(g->g[n].data);
    visited[n]=1;

    arc *p=g->g[n].firstArc;
    while(p)
    {
        if(!visited[p->pos])
            dfs(g,p->pos);
        p=p->nextArc;
    }
}
typedef struct
{
    vex v[N];
    int front,rear;
}queue;

void createQueue(queue *q)
{
    q->front=q->rear=0;
}

void enQueue(queue *q,vex n)
{
    q->v[q->rear]=n;
    q->rear=(q->rear+1)%N;
}
void deQueue(queue *q)
{
    visit(q->v[q->front].data);
    q->front=(q->front+1)%N;
}
bool theQueueIsEmpty(queue *q)
{
    return q->front==q->rear;
}
void bfs(graph *g)
{
    queue q;
    createQueue(&q);
    for(int i=0;i<g->vexNum;i++)
    {
        if(!visited[i])
        {
            enQueue(&q,g->g[i]);
            visited[i]=1;
            arc *p;
            while(!theQueueIsEmpty(&q))
            {
                p=q.v[q.front].firstArc;
                deQueue(&q);
                while(p)
                {
                    if(!visited[p->pos])
                    {
                        enQueue(&q,g->g[p->pos]);
                        visited[p->pos]=1;
                    }
                    p=p->nextArc;
                }
            }
        }
    }
}
int main()
{
    graph g;
    create(&g);
    puts("");
    puts("");
    puts("");
    //dfs(&g, 0);
    bfs(&g);
    return 0;
}

最小生成树

生成树：所有顶点由边连在一块，但不存在回路

特点:

1. 生成树的顶点个数与图的顶点个数相同
2. 生成树是图的极小连通子图，去掉一条边就不再连通
3. 一个顶点为n个的生成树有n-1条边
4. 生成树再加一条边就会形成回路
5. 任意两点之间的连线是唯一的
6. 一个图可以有多棵生成树
7. 含有n个顶点，n-1条边的树不一定是生成树

无向图的生成树

可以对无向图进行遍历，在遍历的过程中将边加到生成树上

---

最小生成树:给定一个无向网，在该网的所有生成树中使得各边权值最小的那棵生成树被称为该网的最小生成树，也叫最小代价生成树

MST性质

假设一个图V中与$$V_1$$顶点连接的顶点有N个，则最小生成树中一定包含一个权值最小的一个边

**原话：**设N=(V,E)$$_{V是顶点集合，E是边集合}$$是一个连通网，U是顶点集V的一个非空子集，若边(u,v)是一条具有权值最小的一条边，其中u∈U，v∈V-U，则必存在一棵包含边(u,v)的最小生成树

人话：

• 落在生成树上的顶点集：U
• 未落在生成树上的顶点集：V-U

在U中的顶点和在V-U中的顶点，选一条权值最小的一条边

普利姆(Prim)算法

1. 设N=(V,E)是连通网，TE是存储最小生成树边的一个集合
2. 初始化，令U={$$u_0$$}，其中$$u_0∈V$$，$$u_0$$是在V中任取的一个顶点（也就是从这个顶点出发，寻找最小生成树），U中存储着落在生成树中顶点的集，TE此时为空
3. 在所有u∈U，v∈V-U中找一条权值最小的边($$u_0,v_0$$)
4. 将这条权值最小的边分别存储到U和TE中
5. 重复3-4步的操作，直到U=V为止(此时就代表U中包含V中的所有顶点)，也就是此时$$T=(V,TE)$$是最小生成树

当遇到权值最小且权值相同的边时，任选一条边进行相连，因此，最小生成树不是唯一的

适宜存储稠密图

人话

初始化从下标为0的点开始找，每次找已经加入最小生成树到未加入到最小生成树的权值最小的边，并将该点加入到最小生成树中

过程

每次选择距离最近的一个点加入到集合中，再用此点更新其他点

void prim(graph *g, graph *tree)
{
    int vex[N], minarc[N];
    vex[0] = minarc[0] = 0;
    for (int i = 1; i < g->vexNum; i++)
    {
        minarc[i] = g->arc[0][i];
        vex[i] = 0;
    }
    
    //以上为初始化语句
    for (int i = 0; i < g->vexNum - 1; i++)
    {
        int pos = 0;
        int min = INT_MAX;
        for (int j = 1; j < g->vexNum; j++)
        {
            if (min > minarc[j] && minarc[j] != 0)
            {
                min = minarc[j];
                pos = j;
            }
        }
        
        
        printf(" %d->%d ", g->vex[vex[pos]], g->vex[pos]);//输出是由那个顶点到哪个顶点之间的路径最短
        tree->arc[vex[pos]][pos] = tree->arc[pos][vex[pos]] = 1;//vex[pos]存储的是上个顶点的下标，pos是被连接到的顶点的下标
        
        
        minarc[pos] = 0;
        for (int j = 0; j < g->vexNum; j++)
        {
            if (minarc[j] != 0 && minarc[j] > g->arc[pos][j])
            {
                minarc[j] = g->arc[pos][j];
                vex[j] = pos;
            }
        }
    }
}

克鲁斯卡尔(Kruskal)算法

1. 设N=(V,E)是连通网，令最小生成树的初始状态是只有n个顶点且无边的非连通图$$T=(V,\left{\right})$$,每个顶点各自都是一个连通分量
2. 在E中取一条权值最小的边若该边落在不同的连通分量上（即不能构成一个环），则将此边加入到T中，否则，舍弃此边，寻找下一条最短的边
3. 重复第二步，直到所有的顶点位于同一个连通分量上(即所有顶点都已连通)

当遇到权值最小且权值相同的边时，任选一条边进行相连，因此，最小生成树不是唯一的

适宜存储稀疏图

人话

• 定义一个边的结构体 ，每个结构体中存储着出发点，到达点，权值，并按从小到大进行排序

• 定义一个用于查询是否有回路的数组，即并查集，并将初值初始化为自身，即每个元素默认就是一个集合

• 开始遍历每一条边，此时边是按照递增的顺序进行排序的，每次取一个数，判断相连的两个点是否在同一集合中，如果在同一集合中，就代表已经有一条最短路径了，就再从下一个数开始查找，如果不在同一集合，则记录下此时的长度，并将两个点并在同一集合中

代码

#include<bits/stdc++.h>

using namespace std;
int n, m;
const int N = 200001;
const int M = 100001;
int vex[M];
int find(int x)//优化后的并查集查找函数
{
    if (x != vex[x])
        vex[x] = find(vex[x]);
    return vex[x];
}

typedef struct
{
    int start, end, len;
} edge;
edge arc[N];
int cmp(edge a,edge b)
{
    return a.len<b.len;
}
//int find(int x)//未优化的并查集查找函数
//{
//    if(vex[x]!=x)
//        x=find(vex[x]);
//    return x;
//}
int fun()
{
    int cnt=0,sum=0;
    for(int i=0;i<m;i++)
    {
        int v1=arc[i].start,v2=arc[i].end;
        v1=find(v1);
        v2=find(v2);
        if(v1!=v2)//两者相等即代表在一棵树中，即此时加入该边后构成环路
        {
            vex[v1]=v2;//合并到一块
            cnt++;//记录完成的边的个数
            sum+=arc[i].len;//记录长度
        }
    }
    if(cnt==n-1)//最小生成树边的个数为顶点个数-1
        return sum;
    else
        return INT_MAX;
}
int main()
{
    cin >> n >> m;//n是顶点个数，m是边数
    for (int i =1; i <= m; i++)
    {
        cin>>arc[i].start>>arc[i].end>>arc[i].len;//输入边的信息
    }
    for(int i=1;i<=n;i++)
        vex[i]=i;//初始化并查集
    sort(arc,arc+m,cmp);//将边从小到大进行排序
    int t=fun();
    if(t!=INT_MAX)//代表是连通图
        cout<<t;
    else//代表不是连通图
        cout<<"impossible";
    return 0;
}

最短路径

最短路径为两顶点所经过的边的权值之和最短的路径或者从源点到其他任意一点的最短路径

与最小生成树的区别：不需要包含所有顶点，也不需要包括n-1条边

解决两顶点之间的路径问题使用Dijkstra(地杰斯特拉)算法

解决所有顶点之间最短路径问题使用Floyd(弗洛伊德)算法

Dijkstra(迪杰斯特拉)算法

步骤

1. 初始化 找出起始点到各终点的直达路径，即通过一条弧到达的路径，若无法直达，则记为无穷
2. 选择 在这些路径中选择一条最短的路径
3. 对路径进行更新，因为是分析的某个点到其他点的路径，如果发现更小的，则就记为更小的
   • 将已经找到最小路径的点放到一个集合中，不在最小路径集合的点单独在一个集合中
   • 继续查找，若有新的点找到最短路径，则将该点加入到最小路径集合中，同时查看到某点是否有更短的路径，如果有则再进行调整，直到最短路径集合满（即未查找的点的集合为空）
4. 继续查找，以此类推

人话

• 首先需要三个辅助数组，一个数组用于记录路径(即这个点是从哪个点过来的)，另一个数组为记录需要查找点到该点长度最小值的数组，该数组用于更新长度（与prim算法的记录长度数组作用一致），还有一个用于记录该点是否被访问的数组
• 初始化，将路径和记录长度的数组中的值分别初始化为自身(从该点出发)和出发点到每个点的长度（若不存在则初始化为INT_MAX)，还需要将下标为出发点的记录长度的数组的值设为0，即这个点到自身的距离为0
• 开始查找，每次取出一个最小值，记录下下标，用该点更新是否存在更小的值

输出最短路径所经过的点

• 用栈实现，首先栈初始化并将需要输出路径的点入栈
• 查看path[栈顶元素]是否与栈顶元素相等，若相等，就代表从该点来的，即该点就是起点
• 如果不相等，就入栈path[栈顶元素]
• 一句话：不断入栈到达该点的上一点，直到起点

代码

void dik(graph *g)
{
    int dist[N];//存储到此顶点的最小路径（长度）
    int path[N];//最小路径所存储经过的上个顶点
    int vex[N];//与visited作用一样，用来存储是否已经找到到改点的最短路径
    for (int i = 0; i < N; i++)
    {
        dist[i] = INT_MAX;
        path[i] = INT_MAX;
        vex[i] = 0;
    }
    dist[0] = 0;//从下标为0的顶点出发，该顶点到他自己的长度为0
    path[0] = 0;//该值也可以设置为一个负数
    for (int i = 0; i < g->vexNum; i++)
    {
        if (g->arcs[0][i] != INT_MAX)//初始化时，如果有能直接到达的点就直接存储
        {
            dist[i] = g->arcs[0][i];
            path[i] = 0;
        }
    }
    //以上均为初始化语句
    while (1)
    {
        int min = INT_MAX;//寻找最小值
        int pos;//存储最小值的位置
        for (int i = 0; i < g->vexNum; i++)
        {
            if (min > dist[i] && !vex[i])//当vex[i]为1时，代表该点已经找到了最短路径
            {
                min = dist[i];
                pos = i;
            }
        }
        if (min == INT_MAX)//当找不到最小的值时就代表所有的顶点的最短路径已经找到，因此跳出循环
            break;
        vex[pos] = 1;//标记
        for (int i = 0; i < g->vexNum; i++)//类似于prim查找最小生成树的算法
        {
            if (!vex[i] && g->arcs[pos][i] != INT_MAX)//查找加入vex[pos]点后，剩余未找到最小路径的点是否还有比现在更短的路，如果这个点不是vex[pos]能够直接访问到的点就不查找
            {
                if (dist[pos] + g->arcs[pos][i] < dist[i])
                {
                    dist[i] = dist[pos] + g->arcs[pos][i];
                    path[i] = pos;
                }
            }
        }
    }
    puts("");
    //测试语句开始
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("(%d %d)", dist[i], path[i]);
    }//测试语句结束
    //以下语句输出从vex[0]到每个点的最短路径，用栈来实现，因为path中存储的是它上一个点的，即从它上一点到这个点，
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("%d-%d short:",1,g->vexs[i]);
        stack<int> s;
        s.push(i);
        while (!s.empty())
        {
            int t = s.top();
            if (path[t] == t)
                break;
            s.push(path[t]);
        }
        while(s.size()!=1)
        {
            int t=s.top();
            printf(" %d ",g->vexs[t]);
            s.pop();
        }
        printf(" %d  len=%d\n",g->vexs[s.top()],dist[s.top()]);
    }
}

完整代码

/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-01-18 09:19:08
 * @LastEditTime: 2021-01-25 13:42:18
 */
// #include <stdio.h>
// #include <limits.h>
#include <bits/stdc++.h>
#define N 100
using namespace std;
typedef struct
{
    int vexs[N];        //顶点表
    int arcs[N][N];     //权值类型，可以用bool等
    int vexNum, arcNum; //记录点数和边数
} graph;
int posG(graph *g, int n) //查找顶点位置
{
    for (int i = 0; i < g->vexNum; i++)
    {
        if (g->vexs[i] == n)
            return i;
    }
    return -1;
}
void create(graph *g)
{
    scanf("%d%d", &g->vexNum, &g->arcNum); //输入总顶点数和总边数
    for (int i = 0; i < g->vexNum; i++)
        scanf("%d", &g->vexs[i]); //输入每个顶点信息
    for (int i = 0; i < g->vexNum; i++)
        for (int j = 0; j < g->vexNum; j++)
            g->arcs[i][j] = INT_MAX; //所有元素赋值为无穷大
    int v1, v2, w;
    for (int k = 0; k < g->arcNum; k++)
    {
        printf("%d th 3:", k + 1);
        scanf("%d%d%d", &v1, &v2, &w); //输入顶点，权值
        int i = posG(g, v1);           //获取位置
        int j = posG(g, v2);
        g->arcs[i][j] = g->arcs[j][i] = w; //无向网也是关于左对角线对称的，因此只用一句给两个边赋值
    }
}
void dik(graph *g)
{
    int dist[N];//存储到此顶点的最小路径（长度）
    int path[N];//最小路径所存储经过的上个顶点
    int vex[N];//与visited作用一样，用来存储是否已经找到到改点的最短路径
    for (int i = 0; i < N; i++)
    {
        dist[i] = INT_MAX;
        path[i] = INT_MAX;
        vex[i] = 0;
    }
    dist[0] = 0;//从下标为0的顶点出发，该顶点到他自己的长度为0
    path[0] = 0;//该值也可以设置为一个负数
    for (int i = 0; i < g->vexNum; i++)
    {
        if (g->arcs[0][i] != INT_MAX)//初始化时，如果有能直接到达的点就直接存储
        {
            dist[i] = g->arcs[0][i];
            path[i] = 0;
        }
    }
    //以上均为初始化语句
    while (1)
    {
        int min = INT_MAX;//寻找最小值
        int pos;//存储最小值的位置
        for (int i = 0; i < g->vexNum; i++)
        {
            if (min > dist[i] && !vex[i])//当vex[i]为1时，代表该点已经找到了最短路径
            {
                min = dist[i];
                pos = i;
            }
        }
        if (min == INT_MAX)//当找不到最小的值时就代表所有的顶点的最短路径已经找到，因此跳出循环
            break;
        vex[pos] = 1;//标记
        for (int i = 0; i < g->vexNum; i++)//类似于prim查找最小生成树的算法
        {
            if (!vex[i] && g->arcs[pos][i] != INT_MAX)//查找加入vex[pos]点后，剩余未找到最小路径的点是否还有比现在更短的路，如果这个点不是vex[pos]能够直接访问到的点就不查找
            {
                if (dist[pos] + g->arcs[pos][i] < dist[i])
                {
                    dist[i] = dist[pos] + g->arcs[pos][i];
                    path[i] = pos;
                }
            }
        }
    }
    puts("");
    //测试语句开始
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("(%d %d)", dist[i], path[i]);
    }//测试语句结束
    //以下语句输出从vex[0]到每个点的最短路径，用栈来实现，因为path中存储的是它上一个点的，即从它上一点到这个点，
    for (int i = 0; i < g->vexNum; i++)
    {
        printf("%d-%d short:",1,g->vexs[i]);
        stack<int> s;
        s.push(i);
        while (!s.empty())
        {
            int t = s.top();
            if (path[t] == t)
                break;
            s.push(path[t]);
        }
        while(s.size()!=1)
        {
            int t=s.top();
            printf(" %d ",g->vexs[t]);
            s.pop();
        }
        printf(" %d  len=%d\n",g->vexs[s.top()],dist[s.top()]);
    }
}
int visited[N] = {0};

void dfs(int n, graph *g)
{
    printf(" %d ", g->vexs[n]);
    visited[n] = 1;
    for (int i = 0; i < g->vexNum; i++)
    {
        if (!visited[i] && g->arcs[n][i] != INT_MAX)
            dfs(i, g);
    }
}

int main()
{
    graph g;
    create(&g);
    printf("\n\n\n");

    dfs(0, &g);

    printf("\n\n\n\n");
    dik(&g);
    return 0;
}

邻接表法

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int head[N],pos[2*N],edgeNext[2*N],len[2*N],idx=0;
int n,m;

void add(int v1,int v2,int value)
{
    pos[idx]=v2;
    edgeNext[idx]=head[v1];
    len[idx]=value;
    head[v1]=idx++;
}
int visited[N];
int main()
{
    memset(head,-1,sizeof head);
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int v1,v2,value;
        cin>>v1>>v2>>value;
        if(v1!=v2)
        {
            add(v1,v2,value);
            add(v2,v1,value);
        }

    }
    int dirt[N];
    for(auto &c:dirt)
        c=INT_MAX;
    for(int i=head[1];i!=-1;i=edgeNext[i])
    {
        int pos2=pos[i];
        dirt[pos2]=len[i];
    }
    cout<<endl<<endl;

    visited[1]=1;
    dirt[1]=0;
    int cnt=0;
    while(1)
    {
        for(int i=1;i<=n;i++)
            cout<<dirt[i]<<' ';
        cout<<endl<<endl;
        int min=INT_MAX,pos2=-1;
        for(int i=1;i<=n;i++)
        {
            if(min>dirt[i]&&!visited[i])
            {
                pos2=i;
                min=dirt[i];
            }
        }
        if(pos2==-1)
            break;
        else
            cnt++;
        visited[pos2]=1;
        cout<<"pos= "<<pos2<<' ';
        for(int i=head[pos2];i!=-1;i=edgeNext[i])
        {
            int pos3=pos[i];
            if(!visited[pos3]&&dirt[pos3]>dirt[pos2]+len[i])
                dirt[pos3]=dirt[pos2]+len[i];
        }
    }
    for(int i=1;i<=n;i++)
        cout<<dirt[i]<<' ';
    return 0;
}

Floyd(弗洛伊德)算法

解决所有顶点之间最短路径问题使用Floyd(弗洛伊德)算法

算法思想

• 逐个顶点进行试探出两点可能存在的路径
• 选出一条最短的路径

步骤

1. 初始化两个二维数组，path存储路径，dirt存储i-j之间的距离，令对角线元素为0（即自己到自己的距离为0），若两点有连线 则对应元素为权值，否则为无穷
2. 逐步试探着在原路径中增加顶点，若加入中间顶点后路径变短，则进行修改路径和权值，否则保持原样，若所有顶点试探完毕，算法结束

输出路径的步骤

在算法中，i->j所经过的路径path[i][j]中存储着i->j中i所经过的下一个点，或者就是j，如果是j，就代表j就是终点。如果不是j，则是中间点，则继续取出中间点到j的点，直到该值为j

/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-01-18 09:19:08
 * @LastEditTime: 2021-01-25 13:42:18
 */
// #include <stdio.h>
// #include <limits.h>
#include <bits/stdc++.h>

#define N 100
using namespace std;
typedef struct
{
    int vexs[N];        //顶点表
    int arcs[N][N];     //权值类型，可以用bool等
    int vexNum, arcNum; //记录点数和边数
} graph;

int posG(graph *g, int n) //查找顶点位置
{
    for (int i = 0; i < g->vexNum; i++)
    {
        if (g->vexs[i] == n)
            return i;
    }
    return -1;
}

void create(graph *g)
{
    scanf("%d%d", &g->vexNum, &g->arcNum); //输入总顶点数和总边数
    for (int i = 0; i < g->vexNum; i++)
        scanf("%d", &g->vexs[i]); //输入每个顶点信息
    for (int i = 0; i < g->vexNum; i++)
        for (int j = 0; j < g->vexNum; j++)
            g->arcs[i][j] = INT_MAX; //所有元素赋值为无穷大
    int v1, v2, w;
    for (int k = 0; k < g->arcNum; k++)
    {
        printf("%d th 3:", k + 1);
        scanf("%d%d%d", &v1, &v2, &w); //输入顶点，权值
        int i = posG(g, v1);           //获取位置
        int j = posG(g, v2);
        g->arcs[i][j] = g->arcs[j][i] = w; //无向网也是关于左对角线对称的，因此只用一句给两个边赋值
    }
}

void flo(graph *g)
{
    int path[N][N], dirt[N][N];
    for (int i = 0; i < g->vexNum; i++)
        for (int j = 0; j < g->vexNum; j++)
        {
            dirt[i][j] = g->arcs[i][j];
            path[i][j] = j;
        }
    for(int k=0;k<g->vexNum;k++)
    {
        for(int i=0;i<g->vexNum;i++)
        {
            for(int j=0;j<g->vexNum;j++)
            {
                if(dirt[i][j]>dirt[i][k]+dirt[k][j]&&(dirt[i][k]!=INT_MAX&&dirt[k][j]!=INT_MAX))
                {
                    dirt[i][j]=dirt[i][k]+dirt[k][j];
                    path[i][j]=path[i][k];//也可以写成path[i][j]=k;
                }
            }
        }
    }

    for(int i=0;i<g->vexNum;i++)
    {
        for(int j=i+1;j<g->vexNum;j++)
        {
            printf("%d-%d:",i,j);
            int k=path[i][j];
            printf(" %d ",g>vex[i]);
            while(k!=j)
            {
                printf(" %d ",k);
                k=path[k][j];
            }
            printf(" %d len=%d\n",g->vex[j],dirt[i][j]);
        }
    }
}

int visited[N] = {0};

void dfs(int n, graph *g)
{
    printf(" %d ", g->vexs[n]);
    visited[n] = 1;
    for (int i = 0; i < g->vexNum; i++)
    {
        if (!visited[i] && g->arcs[n][i] != INT_MAX)
            dfs(i, g);
    }
}

int main()
{
    graph g;
    create(&g);
    printf("\n\n\n");

    dfs(0, &g);

    printf("\n\n\n\n");
    flo(&g);
    return 0;
}

拓扑排序

针对有向无环图 即没有回路的图，也称为DAG图

拓扑序列

• 在图中选择一个入度为零的点并输出
• 将其在图中删掉，包括该点与其他点相连接的边
• 重复前两步，直到图为空

Q.E.D.