C和数据结构——图和prime算法

图的实现和相关算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//自定义
#define INF INT_MAX
#define MAXVEX 30
//typedef char VertexType;
typedef struct vertex
{
    int adjvex;    //顶点编号
    char data[10]; //顶点的信息,可有可无，这里定义为char[10]
} VType;           //顶点的数据类型

typedef struct graph
{
    int n, e;                  //n,e,为图中存在的顶点和边的个数
    VType vexs[MAXVEX];        //顶点集合
    int edges[MAXVEX][MAXVEX]; //邻接矩阵
} MGraph;                      //图的数据类型
//图的邻接表
typedef char VertexType[10]; //
typedef struct edgenode
{
    int adjvex;               //相邻点序号
    int weight;               //边的权值
    struct edgenode *nextarc; //指向下一条边的顶点
} ArcNode;                    //每个顶点建立的单链表中边结点的数据类型

typedef struct vexnode
{
    VertexType data;   //存放顶点信息
    ArcNode *firstarc; //作为头指针指向第一条边结点
} VHeadNode;           //单链表的头结点数据类型
typedef struct
{
    int n, e;                  //,n,e为实际的顶点数和边数
    VHeadNode adjlist[MAXVEX]; //单链表头结点数组
} ALGraph;                     //图的邻接表数据类型

//----------------------------------------------------------------
//邻接矩阵相关的算法
/*已知邻接矩阵数组A,顶点数n,边数e,建立图G的邻接矩阵存储结构*/
void CreatGraph(MGraph &g, int A[][MAXVEX], int n, int e)
{
    int i, j;
    g.n = n;
    g.e = e;
    for (i = 0; i < n; i++)
        for (j = 0; j < n; j++)
            g.edges[i][j] = A[i][j];
}

//求无向图顶点的度
int Degree1(MGraph g, int v)
{
    int i, d = 0;
    if (v < 0 || v >= g.n) //判断边是否合法
        return -1;
    for (i = 0; i < g.n; i++)
    {
        if (g.edges[v][i] > 0 && g.edges[v][i] < INF) //计算度
            d++;
    }
    return d;
}

//数组存储的有向图的顶点的度的计算
int Degree2(MGraph g, int v)
{
    int i, d1 = 0, d2 = 0, d;
    if (v < 0 || v >= g.n)
        return -1;
    for (i = 0; i < g.n; i++)
        if (g.edges[v][i] > 0 && g.edges[v][i] < INF)
            d1++; //以v为开始的度，就是出度
    for (i = 0; i < g.n; i++)
        if (g.edges[i][v] > 0 && g.edges[i][v] < INF)
            d2++; //以v为结束的度，也就是入度
    d = d1 + d2;  //总的度数
    return d;
}

//================================================================
//建立图的邻接表算法
/*已知邻接矩阵数组A,顶点数n,边数e,建立图G的邻接矩阵存储结构*/
void CreatGraph2(ALGraph *&G, int A[][MAXVEX], int n, int e)
{
    int i, j;
    ArcNode *p; //这是结点指针
    G = (ALGraph *)malloc(sizeof(ALGraph));
    G->n = n;
    G->e = e;                  //先确认边和结点的个数
    for (i = 0; i < G->n; i++) //将每个头结点的指针域先置空
        G->adjlist[i].firstarc = NULL;
    for (i = 0; i < G->n; i++)                          //对于每个链表都进行循环赋值插入
        for (j = G->n - 1; j >= 0; j--)                 //对某一个链表进行操作
            if (A[i][j] > 0 && A[i][j] < INF)           //只要邻接矩阵存在边
            {                                           //使用头插法将所有边的信息链接起来
                p = (ArcNode *)malloc(sizeof(ArcNode)); //先申请一块新的空间
                p->adjvex = j;                          //让这个边的后值置为j
                p->weight = A[i][j];                    //赋权4给w
                p->nextarc = G->adjlist[i].firstarc;    //再让p指向i个链表的第一个结点
                G->adjlist[i].firstarc = p;             //再让头结点重置为p,这样头结点还是头结点，新的结点实现头插
            }
}

//销毁图
void DestroyGraph(ALGraph *&G)
{
    int i;
    ArcNode *pre, *p;
    for (i = 0; i < G->n; i++) //遍历所有的头结点
    {
        pre = G->adjlist[i].firstarc; //通过头结点删除链表
        if (pre != NULL)
        {
            /*同遍历链表类似，区别在于p_mov每指向某个节点后都将该节点释放

1、释放前要先保存下一个节点，释放后备份恢复给p_mov,否则释放了当前节点，下一个节点的地址就将失去；
2、依次将所有节点释放后，最后返回NULL（标示释放完毕）。*/
            p = pre->nextarc; //记录后一个结点的位置
            while (p != NULL) //释放i个链表
            {
                free(pre);        //释放前一个结点
                pre = p;          //递归，让前驱指针继续移动，直到后继为空
                p = pre->nextarc; //后继指针同步移动
            }
            free(pre); //释放最后一个结点
        }
    }
    free(G); //释放G所指的头头结点数组的内存空间
}

//求无向图顶点的度
int Degree21(ALGraph *G, int v)
{
    int d = 0;
    ArcNode *p; //创建一个指向结点的指针，便于遍历
    if (v < 0 || v > G->n)
        return -1;
    p = G->adjlist[v].firstarc;
    while (p != NULL) //只要统计单链表的长度就行
    {
        d++;
        p = p->nextarc;
    }
    return d;
}
//有向图的度
int Degree22(ALGraph *G, int v)
{
    int i, d1 = 0, d2 = 0, d;
    ArcNode *p; //
    if (v < 0 || v > G->n)
        return -1;
    p = G->adjlist[v].firstarc;
    while (p != NULL) //先一维循环，查找以v为起点的边，也就是出度
    {
        d1++;
        p = p->nextarc;
    }
    for (i = 0; i < G->n; i++) //再二维循环，遍历整个数组
    {
        p = G->adjlist[i].firstarc;
        while (p != NULL) //查找以v为末尾节点的边，也就是入度
        {
            if (p->adjvex == v)
                d2++;
            p = p->nextarc;
        }
    }
    d = d1 + d2;
    return d;
}

//将邻接矩阵g转换为邻接表G
void MAtTodj(MGraph g, ALGraph *&G)
{
    int i, j;
    ArcNode *p;                             //
    G = (ALGraph *)malloc(sizeof(ALGraph)); //先建表
    for (i = 0; i < g.n; i++)
        G->adjlist[i].firstarc = NULL;                      //置空
    for (i = 0; i < g.n; i++)                               //对邻接矩阵进行遍历
        for (j = g.n - 1; j >= 0; j--)                      //这个遍历显然是二重的
            if (g.edges[i][j] != 0 && g.edges[i][j] != INF) //对于第i中可取的值，都创建一个新的结点p
            {
                p = (ArcNode *)malloc(sizeof(ArcNode)); //申请结点指针类型空间
                p->adjvex = j;                          //记录尾结点的位置                     //对这个结点p进行赋值
                p->weight = g.edges[i][j];              //赋权
                p->nextarc = G->adjlist[i].firstarc;    //只要结点值合法，就创建一个结点，采用头插法
                G->adjlist[i].firstarc = p;             //重置头结点
            }
    G->n = g.n;
    G->e = g.e;
}
//////////////////////////////////////////////////////////////////////////////////////////////////////
/*为了防止多次访问，设置标记数组visited[],开始为0，访问后为1
1,深度优先遍历、确定一个开始当我起点，然后开始访问第一个临界点，然后访问第一个临界点的临界点，
对于已经被访问的，直接跳过，然后开始，直到所有的结点都被访问
*/
int visited[MAXVEX] = {0};  //先设置一个全局变量
void DFS(ALGraph *G, int v) //深度优先遍历算法
{
    int w;                             //标记邻接点的位置
    ArcNode *p;                        //用于遍历
    printf("即将访问的是顶点v:%d", v); //访问v顶点
    visited[v] = 1;                    //改变标志位
    p = G->adjlist[v].firstarc;        //找v的第一个邻接点
    while (p != NULL)                  //找v的所有邻接点
    {
        w = p->adjvex; //
        {
            if (visited[w] == 0) //只要w没被访问
                DFS(G, w);       //就从w出发进行深度优先遍历
            p = p->nextarc;      //被访问就下一个
        }
    }
}
/*----------------------------------------------------------------
2)广度优先算法
指定从v开始，依次访问它所在的链表，也就是访问它的所有的邻接点，然后再从第一个邻接点开始，
重复这样的循环，直到v的最后一个邻接点也被遍历了。*/
void BFS(ALGraph *G, int vi)
{
    int i, v;
    ArcNode *p;
    int Q[MAXVEX], front = 0, rear = 0; //定义一个队列Q,初始化Q
    for (i = 0; i < G->n; i++)          //这一步在已经有了全局变量的时候就不用了
        visited[i] = 0;                 //这一步在已经有了全局变量的时候就不用了
    printf("现在访问的:%d\t", vi);      //输出
    visited[i] = 1;                     //已经访问的结点，要进行置一操作
    rear = (rear + 1) % MAXVEX;         //初始顶点进队，这里涉及到队列的知识，可以回头复习一下
    Q[rear] = vi;                       //进队，先进先出，所以用队呀
    while (front != rear)               //只要队列不为空
    {
        front = (front + 1) % MAXVEX;
        v = Q[front];               //出队顶点v
        p = G->adjlist[v].firstarc; //对v所在的链表进行遍历，也就是查找v的所有的邻接点
        while (p != NULL)           //只要v的邻接点没有被访问完
        {
            if (visited[p->adjvex] == 0) //如果是访问了visited=0的，就访问它且进队，否则跳过
            {
                printf("现在访问到了：%d\n\t", p->adjvex); //访问
                visited[p->adjvex] = 1;                    //置一
                rear = (rear + 1) % MAXVEX;                //进队
                Q[rear] = p->adjvex;                       //进队
            }
            p = p->nextarc; //如果visited=1,就跳过，继续后面的访问
        }
    }
}

int main()
{

    ALGraph tu = {4, 1};
    ALGraph &G = tu;
    ALGraph *q;
    *q = tu;
    int A[][30] = {
        {1111}, {0000}, {1111}, {0000}};
    int(*p)[30] = A;
    int n = 4;
    int e = 8;
    CreatGraph2(q, p, n, e);
    DFS(q, 1);
}

---

prime算法

#include "tu.h"
//prim算法的实现
//从顶点开始，进行遍历
//开始v1,然后遍历最小权值的点
//只要点没有被遍历，就如此进行
//设置两个辅助数组，用来选择点
/*
对于v-u中的每个顶点j，记录它到u中的一条最小边
closest[j]存储该边依附在u中的顶点的编号
lowcost[j]存储该边的权值
U中lowcost[k]=0;v-u中的lowcost[j]>0
*/
void prim(MGraph g, int v)
{ //v是开始的点
    //采用邻接矩阵的方式
    int lowcost[MAXVEX]; //存储访问到的结点的值，也就是邻接矩阵对应的权值
    int closest[MAXVEX]; //存储最小权值所在的点
    int min, i, j, k;
    for (i = 0; i < g.n; i++) //初始化
    {
        lowcost[i] = g.edges[v][i]; //先初始化权值表，后续会改动
        closest[i] = v;             //初始化
        for (i = 0; i < g.n; i++)   //构造n-1条边
        {
            min = INF;
            k = -1;
            for (j = 0; j < g.n; j++) //从V-U中找出与U最近的顶点K
            {
                if (lowcost[j] != 0 && lowcost[j] < min) //查找最小权值所在的点和记录它的权值
                {
                    min = lowcost[j]; //找到最小权值
                    k = j;            //k作为最近的顶点的编号
                }
                printf("\n边%d到%d---------权值为%d\n", closest[k], k, min);
                lowcost[k] = 0;           //标记k已经加入U
                for (j = 0; j < g.n; j++) //修正lowcost和closet，还是循环n次
                {
                    if (lowcost[j] != 0 && g.edges[k][j] < lowcost[j]) //原先的lowcost里存储的是v所在行的权值，使之与k所在的行的权值进行比较，查出最小的，作为新的k点
                    {
                        lowcost[j] = g.edges[k][j];
                        closest[j] = k;
                        //查找出的最小的权值和对应的边，
                    }
                }
            }
        }
    }
}