Obsidian-Knowledge-Base/X-Knowledge-Base/raw/Joplin/计算机专业基础/数据结构与算法/(C)840数据结构与算法/7.图.md

7.1 图的邻接矩阵

#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型

bool visited[MVNum];//定义标志数组

typedef struct {
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
    int i;
    for (int i = 0; i < G.vexnum; i++)
        if (u == G.vexs[i]) return i;
    return -1;
}
/*--------打印图的邻接矩阵-----------*/
void PrintfAMGraph(AMGraph G) {
    //将图的邻接矩阵输出在控制台上
    for (int i = 0; i < G.vexnum; i++) {
        cout << "v" << i + 1 << ":";
        for (int j = 0; j < G.vexnum; j++)
            cout << G.arcs[i][j] << " ";
        cout << endl;
    }
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
    //采用邻接矩阵表示法，创建无向网
    int i = 0, j = 0, k = 0;
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for ( i = 0; i < G.vexnum; i++)//依次输入点的信息
        cin >> G.vexs[i];
    for ( i = 0; i < G.vexnum; i++)//初始化邻接矩阵
        for ( j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = 0;
    for ( k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;//定义两个顶点v1,v2
        cin >> v1 >> v2 ;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j] = G.arcs[j][i] = 1;
    }
}
/*-----------主函数-----------*/
int main() {
    AMGraph G;
    CreateUDN(G);
    PrintfAMGraph(G);
    return 0;
}

7.2 图的邻接表

#include<iostream>
#include<string>
using namespace std;
/*--------图的邻接表存储表示----------*/
#define MVNum 100//最大顶点数
#define OK 1
typedef int OtherInfo;
typedef string VerTexType;
typedef int Status;
typedef struct ArcNode {//边结点
    int adjvex;//该边所指向的顶点位置
    struct ArcNode* nextarc;//指向下一条边的指针
    OtherInfo info;//和边相关的信息
}ArcNode;
typedef struct VNode {//顶点信息
    VerTexType data;
    ArcNode* firstarc;//指向第一条依附该顶点的边的指针
}VNode,AdjList[MVNum];
typedef struct {
    AdjList vertices;
    int vexnum, arcnum;//图的当前顶点数和边数
}ALGraph;
int LocateVex(ALGraph G,VerTexType v1) {//返回传入结点在图中的位置下标
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == v1)
            return i;
    }
    return -1;
}
Status CreateUDG(ALGraph& G) {
    //采用邻接表表示法，创建无向图G
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for (int i = 0; i < G.vexnum; i++) {
        //输入各点，构造表头结点表
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
    }
    for (int k = 0; k < G.arcnum; k++) {
        //输入各边，构造邻接表
        VerTexType v1, v2;
        cin >> v1 >> v2;//输入一条边依附的两个顶点
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点在G.vertices中的序号
        ArcNode* p1 = new ArcNode;//生成新的一个边结点*p1
        p1->adjvex = j;//邻接点序号为j
        p1->nextarc = G.vertices[i].firstarc;//采用头插法
        G.vertices[i].firstarc = p1;//将新结点*p1插入顶点vi的边表头部
        ArcNode* p2 = new ArcNode;//生成新的一个边结点*p2
        p2->adjvex = i;//邻接点序号为i
        p2->nextarc = G.vertices[j].firstarc;//采用头插法
        G.vertices[j].firstarc = p2;//将新结点*p2插入顶点vj的边表头部
    }
    return OK;
}
/*--------将邻接表输出在控制台上---------*/
void PrintfALGraph(ALGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        cout << G.vertices[i].data << "：";
        ArcNode* p = new ArcNode;//生成一个边指针
        p = G.vertices[i].firstarc;//边指针指向第一个边结点
        while (p!=NULL) {//当边指针不为空时，即指针未遍历完
            cout << p->adjvex << " ";
            p = p->nextarc;//边指针继续遍历邻接表
        }
        cout << endl;
    }
}
/*----------主函数-----------*/
int main() {
    ALGraph G;
    CreateUDG(G);
    PrintfALGraph(G);
    return 0;
}

7.3 广度优先搜索遍历 (BFS)

#include<iostream>
#include<string>
using namespace std;
//#define OK 1
#define ERROR 0
#define MAXQSIZE 100
#define MVNum 100
typedef int Status;
typedef string VexType;
typedef int QElemType;
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode* NextAdj;
}ArcNode;
typedef struct VNode
{
    VexType data;
    ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct
{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;
typedef struct
{
    QElemType* base;
    int q_front;
    int q_rear;
}SqQueue;
Status InitQueue(SqQueue& Q)
{
    Q.base=new QElemType[MAXQSIZE];
    Q.q_front=Q.q_rear=0;
    return 1;
}
Status EnQueue(SqQueue& Q,QElemType e)
{
    if((Q.q_rear+1)%MAXQSIZE==Q.q_front)
        return ERROR;
    Q.base[Q.q_rear]=e;
    Q.q_rear=(Q.q_rear+1)%MAXQSIZE;
    return 1;
}
Status DeQueue(SqQueue& Q,QElemType& e)
{
    if(Q.q_front==Q.q_rear) return ERROR;
    e=Q.base[Q.q_front];
    Q.q_front=(Q.q_front+1)%MAXQSIZE;
    return 1;
}
Status QueueEmpty(SqQueue& Q)
{
    if(Q.q_front==Q.q_rear) return 1;
    return ERROR;
}
int LocateVex(ALGraph G,VexType v)
{
    for(int i=0;i<G.vexnum;i++)
    {
        if(v==G.vertices[i].data) return i;
    }
    return -1;
}
int CreateUDG(ALGraph& 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++)
    {
        VexType v1,v2;
        cin>>v1>>v2;//输入依附于一条边的两个顶点
        int i=LocateVex(G,v1);//找到v1的位置
        int j=LocateVex(G,v2);//找到v2的位置
        ArcNode* p1=new ArcNode;//定义指向第一个边结点的指针
        p1->NextAdj=G.vertices[i].firstarc;//指针指向第一个边结点
        G.vertices[i].firstarc=p1;
        p1->adjvex=j;
        ArcNode* p2=new ArcNode;
        p2->NextAdj=G.vertices[j].firstarc;
        p2->adjvex=i;
        G.vertices[j].firstarc=p2;
    }
    return 1;
}
Status GetTop(SqQueue Q)
{
    if(Q.q_front!=Q.q_rear)
        return Q.base[Q.q_front];
}
/*-------采用邻接表表示广度优先搜素遍历------*/
bool visited[MVNum];
void BFS_AL(ALGraph G,int v)
{
    cout<<G.vertices[v].data<<" ";//输出顶点数据域
    visited[v]=true;//将该结点的访问数组单位值赋为true
    SqQueue Q;
    InitQueue(Q);//定义并初始化队列
    EnQueue(Q,v);//将该顶点进队
    ArcNode* w=new ArcNode;//定义指向边结点的指针
    while(Q.q_front!=Q.q_rear)
    {
        int u=0;//定义接收出队元素的变量
        DeQueue(Q,u);//出队
        w=G.vertices[u].firstarc;//令指针指向顶点的第一个边结点
        while(w!=NULL)
        {
            if(!visited[w->adjvex])//某边结点的访问数组的单位值为false
            {
                cout<<G.vertices[w->adjvex].data<<" ";//输出边结点数据域值
                visited[w->adjvex]=true;//将边结点数据域所在顶点的访问数组单位值赋为true
                EnQueue(Q,w->adjvex);//将边结点所表示的顶点进队
            }
            w=w->NextAdj;//将指针指向下一个边结点，直到指向最后一个结点将其赋值为空，循环结束
        }
    }
}
int main()
{
    ALGraph G;
    CreateUDG(G);
    int v=0;
    BFS_AL(G,v);
    return 0;
}

7.4 深度优先搜索遍历（DFS）

#pragma clang diagnostic push
#pragma ide diagnostic ignored "misc-no-recursion"

#include<iostream>
#include<string>

using namespace std;
#define OK 1
#define MVNum 100//最大顶点数
typedef string VerTexType;//假设顶点的数据类型为字符串
typedef int ArcType;//假设边的权值类型为整型
/*---------图的邻接矩阵---------*/
typedef struct Graph {
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum]{};//邻接矩阵
    int vexnum{}, arcnum{};//图的顶点数和边数
} Graph;

/*--------确定顶点在图中的位置--------*/
int LocateVex(const Graph &G, const VerTexType &V) {
    //确定V在G中的位置
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vexs[i] == V) return i;
    }
    return -1;//未找到指定结点
}

/*--------返回顶点的第一个邻接点编号-------*/
/*
int FirstAdjVex(const Graph &G, int v) {
    //返回v的第一个邻接表编号，没有则返回-1
    for (int i = 0; i < G.vexnum; i++) {
        if (G.arcs[v][i] == 1)//邻接表该处为1，表明形参结点和i号结点之间有边
            return i;
    }
    return -1;
}
*/
/*---------返回v相对于w的下个邻接点--------*/
/*
int NextAdjVex(Graph &G, int v, int w) {
    //返回v相对于w的下一个邻接点，没有则返回-1
    for (int i = w + 1; i < G.vexnum; i++) {
        if (G.arcs[v][i] == 1)
            return i;
    }
    return -1;
}
*/
/*采用邻接矩阵表示法创建无向图*/
int CreateUDG(Graph &G) {
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++) {//输入各顶点信息
        cin >> G.vexs[i];
    }
    for (int i = 0; i < G.vexnum; i++)
        for (int j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = 0;//将边结点表都初始化为0
    for (int k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;
        cin >> v1 >> v2;//输入相连通的两个结点
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);//找到两个结点的位置
        G.arcs[i][j] = G.arcs[j][i] = 1;
        //G.arcs[i][j] = 1;
    }
    return OK;
}

bool visited[MVNum];//访问标志数组，其初值为"false"
/*----------深度优先搜索遍历连通图--------*/
void DFS(const Graph &G, int v) {
    //从第v个顶点出发递归地深度优先遍历图G
    cout << G.vexs[v] << " ";
    visited[v] = true;//访问第v个顶点，并置访问标志数组相应分量值为true
    for (int w = 0; w < G.vexnum; w++) {
        //依次检查v的所有邻接点w,FirstAdjVex(G,v)表示v的第一个邻接点
        //NextAdjVex(G,v,w)表示v相对于w的下一个邻接点，w>=0表示存在邻接点
        if (G.arcs[v][w] != 0 && !visited[w]) {
            DFS(G, w);//对v的尚未访问的邻接顶点w递归调用DFS
        }
    }
}

/*----------深度优先搜索遍历非连通图---------*/
void DFSTraverse(const Graph &G) {
    //对非连通图G，做深度优先遍历
    for (int i = 0; i < G.vexnum; i++)
        visited[i] = false;//访问标志数组初始化
    for (int i = 0; i < G.vexnum; i++)
        if (!visited[i]) {
            DFS(G, i);
        }//对尚未访问的顶点调用DFS
}

/*----------主函数----------*/
int main() {
    Graph G;
    CreateUDG(G);
    int v = 0;
    DFS(G, v);
    DFSTraverse(G);
    return 0;
}

#pragma clang diagnostic pop

7.5最小生成树之Prim算法

#include<iostream>
#include<string>
using namespace std;
#define MVNum 100
#define MAXInt 32767//定义无穷大
typedef  string VerTexType;
typedef int ArcType;
/*----------图的邻接矩阵表示法存储结构---------*/
typedef struct {
    int arcnum, vexnum;//顶点数和边数
    VerTexType vex[MVNum];//定义存储顶点的数组
    ArcType arcs[MVNum][MVNum];//定义存储边的数组
}AMGraph;
/*-------辅助数组的定义，用来记录从顶点集U到V-U的权值最小的边-------*/
typedef struct 
{
    VerTexType adjvex;//最小边在U中的那个顶点
    ArcType lowcost;//最小边上的权值
}MinEdge;
MinEdge closedge[MVNum];
/*----------在顶点表中找到传入顶点的位置---------*/
int LocateVex(AMGraph G, VerTexType v) {
    //遍历顶点表，返回某顶点在顶点表中的位置下标
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vex[i] == v)//在顶点表中找到了顶点v
            return i;//返回其下标
    }
    return -1;//没找到返回-1
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
    //采用邻接矩阵表示法，创建无向网
    int i = 0, j = 0, k = 0, w;
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for (i = 0; i < G.vexnum; i++)//依次输入点的信息
        cin >> G.vex[i];
    for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
        for (j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MAXInt;
    for (k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;//定义两个顶点v1,v2
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j] = G.arcs[j][i] = w;
    }
}
/*--------在辅助数组中找到lowcost最小的顶点-------*/
int Min(MinEdge closedge[],int size) {
    //取最小权值边的顶点位置
    int k = -1;//最后接收最小权值邻接点的下标
    for (int i = 0; i < size; i++) {
        if (closedge[i].lowcost > 0) {//i号顶点并未被归入到生成树中
            int min = closedge[i].lowcost;//设置min中间变量存放最小权值
            for (int j = i; j < size; j++) {
                if (closedge[j].lowcost > 0 && min >= closedge[j].lowcost) {
                    min = closedge[j].lowcost;
                    k = j;
                }
            }
            break;
        }
    }
    return k;
}
/*------------构造最小生成树的Prim算法----------*/
void MiniSpanTree_Prim(AMGraph G, VerTexType u) {
    //无向网G以邻接矩阵形式存储，从顶点u出发构造G的最小生成树T，输出T的各条边
    int k = LocateVex(G, u);//k为顶点u的下标
    for (int j = 0; j < G.vexnum; j++) {
        //对V-U的每一个顶点vj，初始化closedge[j]
        closedge[j].adjvex = u;//{adjvex,lowcost}
        closedge[j].lowcost = G.arcs[k][j];
    }
    closedge[k].lowcost = 0;//初始,U={u}
    for (int i = 1; i < G.vexnum; i++) {
        //选择其余n-1个结点，生成n-1条边（n=G.vexnum）
        int k = Min(closedge,G.vexnum);
        //求出T的下一个结点；第k个顶点,closedge[k]中存有当前最小边
        ArcType u0 = closedge[k].lowcost;//u0为最小边的一个顶点,u0属于u
        VerTexType v0 = G.vex[k];//v0为最小边的另一个顶点，v0属于V-U
        cout << u0 << " " << v0 << endl;//输出当前的最小边(u0,v0);
        closedge[k].lowcost = 0;//第k个顶点并入U集
        for (int j = 0; j < G.vexnum; j++) {
            if (G.arcs[k][j] < closedge[j].lowcost)//新顶点并入U后重新选择最小边
            {
                closedge[j].adjvex = G.vex[k];
                closedge[j].lowcost = G.arcs[k][j];
            }
        }
    }
}
int main() {
    AMGraph G;
    CreateUDN(G);
    int v = 0;
    MiniSpanTree_Prim(G,G.vex[v]);
    return 0;
}

7.6 最小生成树之Kruskal算法

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define MVNum 100
#define MAXInt 32767//定义无穷大
typedef  string VerTexType;
typedef int ArcType;
/*----------图的邻接矩阵表示法存储结构---------*/
typedef struct {
    int arcnum, vexnum;//顶点数和边数
    VerTexType vex[MVNum];//定义存储顶点的数组
    ArcType arcs[MVNum][MVNum];//定义存储边的数组
}AMGraph;
/*-----------辅助数组Edges的定义--------------*/
typedef struct edge{
    VerTexType Head;//边的始点
    VerTexType Tail;//边的终点
    ArcType lowcost;//边上的权值
}Edgea;
Edgea Edge[MVNum];
/*---------辅助数组Vexset的定义------------*/
int Vexset[MVNum];
/*----------在顶点表中找到传入顶点的位置---------*/
int LocateVex(AMGraph G, VerTexType v) {
    //遍历顶点表，返回某顶点在顶点表中的位置下标
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vex[i] == v)//在顶点表中找到了顶点v
            return i;//返回其下标
    }
    return -1;//没找到返回-1
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
    //采用邻接矩阵表示法，创建无向网
    int i = 0, j = 0, k = 0, w;
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for (i = 0; i < G.vexnum; i++)//依次输入点的信息
        cin >> G.vex[i];
    for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
        for (j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MAXInt;
    for (k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;//定义两个顶点v1,v2
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j] = G.arcs[j][i] = w;
        Edge[k].Head = v1;
        Edge[k].Tail = v2;
        Edge[k].lowcost = w;
    }
}
/*-----获取图的边数---------*/
int getArcnum(int n) {//获取图的边数
    return n;
}

bool cmd(edge a,edge b) {
    return a.lowcost < b.lowcost;
}
/*----------Kruskal算法的代码实现----------*/
void MiniSpanTree_Kruskal(AMGraph& G) {
    //无向网G以邻接矩阵形式存储，构造G的最小生成树T，输出T的各条边
    sort(Edge, Edge + G.arcnum, cmd);//将数组Edge中的元素按权值从小到大排序
    int sum = 0;
    for (int i = 0; i < G.vexnum; i++)//辅助数组，表示各顶点自成一个连通分量
        Vexset[i] = i;
    for (int i = 0; i < G.arcnum; i++) {//依次查看数组Edge中的边
        int v1, v2 = 0;
        v1 = LocateVex(G, Edge[i].Head);//v1为边的始点Head的下标
        v2 = LocateVex(G, Edge[i].Tail);//v2为边的终点Tail的下标
        int vs1, vs2 = 0;
        vs1 = Vexset[v1];//获取边Edge[i]的始点所在的连通分量vs1
        vs2 = Vexset[v2];//获取边Edge[i]的终点所在的连通分量vs2
        if (vs1 != vs2) {//边的两个顶点分属不同的连通分量
            cout << Edge[i].Head <<" "<< Edge[i].Tail <<" "<< Edge[i].lowcost << endl;//输出此边
            for (int j = 0; j < G.vexnum; j++) {//合并vs1和vs2两个分量，即两个集合统一编号
                if (Vexset[j] == vs2) Vexset[j] = vs1;//集合编号为vs2的都改成vs1
            }
        }
    }
}
int main() {
    AMGraph G;
    CreateUDN(G);
    MiniSpanTree_Kruskal(G);
    return 0;
}

7.7 最短路径之Dijkstra算法

#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define MaxInt 32767//无穷大
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型

bool visited[MVNum];//定义标志数组

typedef struct {
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*-----------迪杰斯特拉算法辅助数组的建立----------*/
bool S[MVNum];
int Path[MVNum];
int D[MVNum];
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
    int i;
    for (int i = 0; i < G.vexnum; i++)
        if (u == G.vexs[i]) return i;
    return -1;
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
    //采用邻接矩阵表示法，创建无向网
    int i = 0, j = 0, k = 0;
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for (i = 0; i < G.vexnum; i++)//依次输入点的信息
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
        for (j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;
    for (k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;//定义两个顶点v1,v2
        int w = 0;
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j] = w;
    }
}
/*-----------最短路径之迪杰斯特拉算法------------*/
void ShortestPath_DIJ(AMGraph G, int v0) {
    //用Dijkstra算法求有向图G的v0顶点到其余顶点的最短路径
    int n = G.vexnum;//n为G中顶点的个数
    for (int v = 0; v < n; v++) {
        S[v] = false;//S初始化为空集
        D[v] = G.arcs[v0][v];//将v0到各个终点的最短路径长度初始化为弧上的权值
        if (D[v] < MaxInt) Path[v] = v0;//如果v0和v之间有弧，则将v的前驱置为v0
        else Path[v] = -1;//如果v0和v之间无弧，则将v的前驱置为-1
    }
    S[v0] = true;//将v0加入S
    D[v0] = 0;//源点到源点的距离为0
    /*----------初始化结束，开始主循环，每次求得v0到某个顶点v的最短路径，将v加到S集-------*/
    for (int i = 1; i < n; i++) {
        //对其余n-1个顶点，依次进行计算
        int min = MaxInt;
        int v = 0;
        for (int w = 0; w < n; w++)
            if (!S[w] && D[w] < min) {
                v = w; min = D[w];//选择一条当前的最短路径，终点为v
            }
            S[v] = true;//将v加入S
            for (int w = 0; w < n; w++) {//更新从v0出发到集合V-S上所有顶点的最短路径长度
                if (!S[w] && (D[v] + G.arcs[v][w] < D[w])) {
                    D[w] = D[v] + G.arcs[v][w];//更新D[w]
                    Path[w] = v;//更改w的前驱为v
                }
            }
    }
}
/*-----------递归输出最短路径----------*/
void find(int x) {
    if (Path[x] == 0) {
        cout << 0;
    }
    else {
        find(Path[x]);
    }
    cout << "->" << x;
    return;
}
/*--------输出结果----------*/
void PrintResult(AMGraph G) {
    cout << "点v0到其他各点的最短路程为：" << endl;
    for (int i = 0; i < G.vexnum; i++) {
        cout << D[i] << " ";
    }
    cout << endl;
    for (int i = 1; i < G.vexnum; i++) {
        if (D[i] == MaxInt) continue;
        cout << "起点v0到v" << i << "的路径为：";
        find(i);
        cout << endl;
    }
}
/*-----------主函数-----------*/
int main() {
    AMGraph G;
    CreateUDN(G);
    ShortestPath_DIJ(G, 0);
    PrintResult(G);
    return 0;
}

7.8 最短路径之Floyd算法

#include<iostream>
using namespace std;
/*-------图的邻接矩阵存储表示-----*/
#define MVNum 100//最大顶点数
#define MaxInt 32767//无穷大
#define OK 1
#define ERROR 0
typedef int Status;
typedef string VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型

bool visited[MVNum];//定义标志数组

typedef struct {
    VerTexType vexs[MVNum];//顶点表
    ArcType arcs[MVNum][MVNum];//邻接矩阵
    int vexnum, arcnum;//图的当前点数和边数
}AMGraph;
/*-----------迪杰斯特拉算法辅助数组的建立----------*/
bool S[MVNum];
int Path[MVNum][MVNum];
int D[MVNum][MVNum];
/*---------确定某顶点在G中的位置下标-----------*/
int LocateVex(AMGraph G, VerTexType u) {
    int i;
    for (int i = 0; i < G.vexnum; i++)
        if (u == G.vexs[i]) return i;
    return -1;
}
/*---------采用邻接矩阵表示法创建无向网-------*/
void CreateUDN(AMGraph& G) {
    //采用邻接矩阵表示法，创建无向网
    int i = 0, j = 0, k = 0;
    cin >> G.vexnum >> G.arcnum;//输入总顶点数，总边数
    for (i = 0; i < G.vexnum; i++)//依次输入点的信息
        cin >> G.vexs[i];
    for (i = 0; i < G.vexnum; i++)//初始化邻接矩阵
        for (j = 0; j < G.vexnum; j++)
            G.arcs[i][j] = MaxInt;
    for (k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;//定义两个顶点v1,v2
        int w = 0;
        cin >> v1 >> v2 >> w;
        i = LocateVex(G, v1);
        j = LocateVex(G, v2);//确定v1和v2在G中的位置，即顶点数组的下标
        G.arcs[i][j] = w;
    }
}
/*----------弗洛伊德算法代码实现----------*/
void ShortestPath_Floyd(AMGraph G) {
    //用Floyd算法求有向图G中各顶点i和j之间的最短路径
    for(int i=0;i<G.vexnum;i++)//各对结点之间初始已知路径及距离
        for (int j = 0; j < G.vexnum; j++) {
            D[i][j] = G.arcs[i][j];
            if (D[i][j] < MaxInt && i != j) Path[i][j] = i;//如果i和j之间有弧，则将j的前驱置为1
            else Path[i][j] = -1;//如果i和j之间无弧，则将j的前驱置为-1
        }
    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 (D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];//更新D[i][j]
                    Path[i][j] = Path[k][j];//更改j的前驱为k
                }
}
/*-----------输出结果-----------*/
void PrintResult(AMGraph G) {
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            if (D[i][j] == MaxInt && i != j) {
                cout << "-1 ";
            }
            else if (i == j)
                cout << "0 ";
            else
                cout << D[i][j] << " ";
        }
        cout << endl;
    }
}
/*-----------主函数-----------*/
int main() {
    AMGraph G;
    CreateUDN(G);
    ShortestPath_Floyd(G);
    PrintResult(G);
    return 0;
}

7.9 拓扑排序的实现

#include<iostream>
#include<string>
using namespace std;
#define MVNum 100
#define OK 1
#define ERROR 0
#define MaxInt 100
typedef string VerTexType;
typedef int Status;
typedef int SElemType;
typedef struct{
    SElemType* base;
    SElemType* top;
    int stacksize;
}SqStack;
typedef struct ArcNode {
    int adjvex;
    struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {
    VerTexType data;
    ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct {
    int vexnum, arcnum;
    AdjList vertices;
}ALGraph;
/*--------拓扑排序辅助数组的存储结构--------*/
int indegree[MVNum];//存放各顶点入度
int topo[MVNum];//记录拓扑序列的顶点编号
Status InitStack(SqStack& S) {
    S.base = new SElemType[MaxInt];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MaxInt;
    return OK;
}
Status StackEmpty(SqStack S) {
    if (S.top == S.base) return OK;
    return ERROR;
}
Status Push(SqStack& S, SElemType e) {
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;
}
Status Pop(SqStack& S, SElemType& e) {
    if (S.base == S.top) return ERROR;
    S.top--;
    e = *S.top;
    return OK;
}
int LocateVex(ALGraph G, VerTexType v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == v)
            return i;
    }
    return -1;
}
void CreateUDG(ALGraph& G) {
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++) {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
    }
    for (int k = 0; k < G.arcnum; k++) {
        VerTexType 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;
    }
}
void FindInDegree(ALGraph G, int indegree[]) {
    for (int i = 0; i < G.vexnum; i++) {
        int cnt = 0;//设置变量存储邻接点域为i的结点个数
        for (int j = 0; j < G.vexnum; j++) {
            ArcNode* p = new ArcNode;//定义指向各个边结点的指针
            p = G.vertices[j].firstarc;
            while (p) {//当p未指到单个链表的末尾时继续循环
                if (p->adjvex == i)//当某边结点邻接点域等于i时，计数变量++
                    cnt++;
                p = p->nextarc;//指针不断向后指
            }
            indegree[i] = cnt;//将计数结果保留在indegree数组中
        }
    }
}
Status TopologicalSort(ALGraph G, int topo[]) {
    //有向图G采用邻接表存储结构
    //若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERROR
    FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中
    SqStack S;
    InitStack(S);//初始化栈
    for (int i = 0; i < G.vexnum; i++) {
        if (!indegree[i]) Push(S, i);//入度为0者进栈
    }
    int m = 0;//对输出顶点计数u，初始为0
    while (!StackEmpty(S)) {
        int i = 0;
        Pop(S, i);//将栈顶顶点vi出栈
        topo[m] = i;//将vi保存在拓扑序列数组topo中
        ++m;//对输出顶点计数
        ArcNode* p = new ArcNode;
        p = G.vertices[i].firstarc;//p指向vi的第一个邻接点
        while (p != NULL) {
            int k = p->adjvex;//vk为vi的邻接点
            --indegree[k];//vi的每个邻接点的入度减一
            if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈
            p = p->nextarc;//p指向顶点vi下一个邻接结点
        }
    }
    if (m < G.vexnum) return ERROR;//该有向图有回路
    else return OK;
}
/*输出拓扑排序后的结果*/
void PrintResult(ALGraph G) {
    if (TopologicalSort(G, topo)) {
        for (int i = 0; i < G.vexnum; i++) {
            cout << G.vertices[topo[i]].data << " ";
        }
    }
}
int main() {
    ALGraph G;
    CreateUDG(G);
    PrintResult(G);
    return 0;
}

7.10 关键路径的实现

#include<iostream>
#include<string>
using namespace std;
#define MVNum 100
#define OK 1
#define ERROR 0
#define MaxInt 100
typedef string VerTexType;
typedef int Status;
typedef int SElemType;
typedef int OtherInfo;
typedef struct{
    SElemType* base;
    SElemType* top;
    int stacksize;
}SqStack;
typedef struct ArcNode {
    int adjvex;
    OtherInfo weight;
    struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {
    VerTexType data;
    ArcNode* firstarc;
}VNode,AdjList[MVNum];
typedef struct {
    int vexnum, arcnum;
    AdjList vertices;
}ALGraph;
/*--------拓扑排序辅助数组的存储结构--------*/
int indegree[MVNum];//存放各顶点入度
int topo[MVNum];//记录拓扑序列的顶点编号
/*-------关键路径算法的两个辅助数组---------*/
int ve[MVNum];//事件vi的最早发生时间
int vl[MVNum];//事件vi的最迟发生时间
Status InitStack(SqStack& S) {
    S.base = new SElemType[MaxInt];
    if (!S.base) return ERROR;
    S.top = S.base;
    S.stacksize = MaxInt;
    return OK;
}
Status StackEmpty(SqStack S) {
    if (S.top == S.base) return OK;
    return ERROR;
}
Status Push(SqStack& S, SElemType e) {
    if (S.top - S.base == S.stacksize) return ERROR;
    *S.top = e;
    S.top++;
    return OK;
}
Status Pop(SqStack& S, SElemType& e) {
    if (S.base == S.top) return ERROR;
    S.top--;
    e = *S.top;
    return OK;
}
int LocateVex(ALGraph G, VerTexType v) {
    for (int i = 0; i < G.vexnum; i++) {
        if (G.vertices[i].data == v)
            return i;
    }
    return -1;
}
void CreateUDG(ALGraph& G) {
    cin >> G.vexnum >> G.arcnum;
    for (int i = 0; i < G.vexnum; i++) {
        cin >> G.vertices[i].data;
        G.vertices[i].firstarc = NULL;//初始化表头结点的指针域为NULL
    }
    for (int k = 0; k < G.arcnum; k++) {
        VerTexType v1, v2;
        int w=0;
        cin >> v1 >> v2 >> w;
        int i = LocateVex(G, v1);
        int j = LocateVex(G, v2);
        ArcNode* p1 = new ArcNode;
        p1->adjvex = j;
        p1->weight = w;
        p1->nextarc = G.vertices[i].firstarc;
        G.vertices[i].firstarc = p1;
    }
}
void FindInDegree(ALGraph G, int indegree[]) {
    for (int i = 0; i < G.vexnum; i++) {
        int cnt = 0;//设置变量存储邻接点域为i的结点个数
        for (int j = 0; j < G.vexnum; j++) {
            ArcNode* p = new ArcNode;//定义指向各个边结点的指针
            p = G.vertices[j].firstarc;
            while (p) {//当p未指到单个链表的末尾时继续循环
                if (p->adjvex == i)//当某边结点邻接点域等于i时，计数变量++
                    cnt++;
                p = p->nextarc;//指针不断向后指
            }
            indegree[i] = cnt;//将计数结果保留在indegree数组中
        }
    }
}
/*----------拓扑排序算法---------------*/
Status TopologicalSort(ALGraph G, int topo[]) {
    //有向图G采用邻接表存储结构
    //若G无回路，则生成G的一个拓扑排序topo[]并返回OK，否则ERROR
    FindInDegree(G, indegree);//求出各结点的入度存入数组indegree中
    SqStack S;
    InitStack(S);//初始化栈
    for (int i = 0; i < G.vexnum; i++) {
        if (!indegree[i]) Push(S, i);//入度为0者进栈
    }
    int m = 0;//对输出顶点计数u，初始为0
    while (!StackEmpty(S)) {
        int i = 0;
        Pop(S, i);//将栈顶顶点vi出栈
        topo[m] = i;//将vi保存在拓扑序列数组topo中
        ++m;//对输出顶点计数
        ArcNode* p = new ArcNode;
        p = G.vertices[i].firstarc;//p指向vi的第一个邻接点
        while (p != NULL) {
            int k = p->adjvex;//vk为vi的邻接点
            --indegree[k];//vi的每个邻接点的入度减一
            if (indegree[k] == 0) Push(S, k);//若入度减为0，则入栈
            p = p->nextarc;//p指向顶点vi下一个邻接结点
        }
    }
    if (m < G.vexnum) return ERROR;//该有向图有回路
    else return OK;
}
/*---------关键路径算法---------*/
Status CriticalPath(ALGraph& G) {
    //G为邻接表存储的有向图，输出G的各项关键活动
    if (!TopologicalSort(G, topo)) return ERROR;
    //调用拓扑排序算法，使拓扑序列保存在topo中，若调用失败，则存在有向环，返回ERROR
    int n = G.vexnum;//n为顶点个数
    for (int i = 0; i < n; i++)//给每个事件的最早发生时间置初值为0
        ve[i] = 0;
    /*-------------按拓扑序列求每个事件的最早发生时间---------------*/
    for (int i = 0; i < n; i++) {
        int k = topo[i];//取得拓扑序列中的顶点序号k
        ArcNode* p = new ArcNode;
        p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点
        while (p != NULL) {
            int j = p->adjvex;//j为邻接顶点的序号
            if (ve[j] < ve[k] + p->weight)//更新顶点j的最早发生时间ve[j]
                ve[j] = ve[k] + p->weight;
            p = p->nextarc;//p指向k的下一个邻接顶点
        }
    }
    for (int i = 0; i < n; i++)
        vl[i] = ve[n - 1];//给每个事件的最迟发生时间置初值ve[n-1]
    /*-----------按拓扑次序求每个事件的最迟发生时间-----------*/
    for (int i = n - 1; i >= 0; i--) {
        int k = topo[i];//取得拓扑序列中的顶点序号k
        ArcNode* p = new ArcNode;
        p = G.vertices[k].firstarc;//p指向k的第一个邻接顶点
        while (p != NULL) {//根据k的邻接点，更新k的最迟发生时间
            int j = p->adjvex;//j为邻接顶点的序号
            if (vl[k] > vl[j] - p->weight)//更新顶点k的最迟发生时间vl[k]
                vl[k] = vl[j] - p->weight;
            p = p->nextarc;//p指向k的下一个邻接顶点
        }
    }
    /*-----------判断每一个活动是否为关键活动--------------*/
    for (int i = 0; i < n; i++) {
        ArcNode* p = new ArcNode;
        p = G.vertices[i].firstarc;//p指向i的第一个邻接顶点
        while (p != NULL) {
            int j = p->adjvex;//j为邻接顶点的序号
            int e = ve[i];//计算活动<vi,vj>的最早开始时间
            int l = vl[j] - p->weight;//计算活动<vi,vj>的最迟开始时间
            if (e == l)
                cout << G.vertices[i].data << " " << G.vertices[j].data << endl;
            p = p->nextarc;//p指向i的下一个邻接顶点
        }
    }
}
int main() {
    ALGraph G;
    CreateUDG(G);
    CriticalPath(G);
    return 0;
}