数据结构 – 图

发布于 19 天前  11 次阅读 本文共6578个字


邻接矩阵

//
// Created by Miku on 2020/6/23.
//
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

// 定义最大顶点个数
#define MaxV 4
// 定义顶点其他信息类型
#define Info_Type char
// 顶点数据类型
#define Data_Type int

// 邻接矩阵存储
typedef struct{
    int no;
    Info_Type *info;  // 顶点其他信息
} VertexType;

// 图的定义
typedef struct{
    // 邻接矩阵
    VertexType edges[MaxV][MaxV];
    // 定点数,边数
    int n, e;
    Data_Type vexs[MaxV];  // 存放顶点信息
}MGraph;

// 根据顶点本身数据,判断顶点在二维数组中的位置
int LocateVex(MGraph *G, Data_Type v){
    int i = 0;
    // 遍历一维数组,找到变量 x
    for (;  i< G->n; i++) {
        if (G->vexs[i] == v)
            break;
    }
    // 如果找不到
    if (i > G->n){
        printf("no such vertex.\n");
        return  -1;
    }
    return i;
}


// 构造有向图
void CreateDG(MGraph *G){
    // 输入图含有含有的顶点树和弧的个数
    scanf("%d %d", &(G->n), &(G->e));
    // 依次输入顶点本身的数据
    for (int i = 0; i < G->n; ++i) {
        scanf("%d", &(G->vexs[i]));  // 存放顶点信息
    }
    // 初始化二维矩阵,全部归零,指针指向 NULL
    for (int i = 0; i < G->n; ++i) {
        for (int j = 0; j < G->n; ++j) {
            G->edges[i][j].no = 0;
            G->edges[i][j].info = NULL;
        }
    }
    // 在二维数组中添加弧的数据
    for (int i = 0; i < G->e; ++i) {
        int v1, v2;
        // 输入弧头,弧尾
        scanf("%d,%d", &v1, &v2);
        // 确定顶点位置
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m == -1 || n == -1){
            printf("no this vertex\n");
            return;
        }
        // 将正确的弧的数据加入到二维数组
        G->edges[n][m].no = 1;
    }
}

// 构造无向图
void CreateDN(MGraph *G){
    // 输入图含有含有的顶点树和弧的个数
    scanf("%d %d", &(G->n), &(G->e));
    // 依次输入顶点本身的数据
    for (int i = 0; i < G->n; ++i) {
        scanf("%d", &(G->vexs[i]));  // 存放顶点信息
    }
    // 初始化二维矩阵,全部归零,指针指向 NULL
    for (int i = 0; i < G->n; ++i) {
        for (int j = 0; j < G->n; ++j) {
            G->edges[i][j].no = 0;
            G->edges[i][j].info = NULL;
        }
    }
    // 在二维数组中添加弧的数据
    for (int i = 0; i < G->e; ++i) {
        int v1, v2;
        // 输入弧头,弧尾
        scanf("%d,%d", &v1, &v2);
        // 确定顶点位置
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (m == -1 || n == -1){
            printf("no this vertex\n");
            return;
        }
        // 将正确的弧的数据加入到二维数组
        G->edges[n][m].no = 1;
        G->edges[n][m].no = 1;
    }
}

//构造有向网,和有向图不同的是二阶矩阵中存储的是权值。
void CreateUDG(MGraph *G){
    // 顶点树 x 边数
    scanf("%d %d", &(G->n), &(G->e));
    // 顶点数据
    for (int i = 0; i < G->n; ++i) {
        scanf("%d", &(G->vexs[i]));
    }
    // 初始化二维矩阵
    for (int i = 0; i < G->n; ++i) {
        for (int j = 0; j < G->n; ++j) {
            G->edges[i][j].no = 0;
            G->edges[i][j].info = NULL;
        }
    }
    // 填写边信息
    for (int i = 0; i < G->e; ++i) {
        int v1, v2, w;
        // 读入 头顶点,后点,权值
        scanf("%d,%d,%d", &v1,&v2,&w);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (n == - 1 || m == -1){
            printf("No this vertex\n");
            return;
        }
        G->edges[n][m].no = w;
    }
}

// 构造无向图,有权值
void CreateUDN(MGraph *G){
    // 顶点树 x 边数
    scanf("%d %d", &(G->n), &(G->e));
    // 顶点数据
    for (int i = 0; i < G->n; ++i) {
        scanf("%d", &(G->vexs[i]));
    }
    // 初始化二维矩阵
    for (int i = 0; i < G->n; ++i) {
        for (int j = 0; j < G->n; ++j) {
            G->edges[i][j].no = 0;
            G->edges[i][j].info = NULL;
        }
    }
    // 填写边信息
    for (int i = 0; i < G->e; ++i) {
        int v1, v2, w;
        // 读入 头顶点,后点,权值
        scanf("%d,%d,%d", &v1,&v2,&w);
        int n = LocateVex(G, v1);
        int m = LocateVex(G, v2);
        if (n == - 1 || m == -1){
            printf("No this vertex\n");
            return;
        }
        G->edges[n][m].no = w;
        G->edges[m][n].no = w;  // 矩阵对称
    }
}

// 输出函数
void PrintGraph(MGraph G){
    for (int i = 0; i < G.n; ++i) {
        for (int j = 0; j < G.n; ++j) {
            printf("%d", G.edges[i][j].no);
        }
        printf("\n");
    }
}

int visited[7];
// DFS遍历
void DFS(MGraph G, int v){
    int vertex;
    visited[v] = 1;
    printf("%d", v); // 输出被访问顶点的编号
    for (int i = 0; i < G.n; ++i) {
        vertex = G.vexs[i];
        if (visited[vertex] == 0 && vertex != v)
            DFS(G, vertex);  // 若 vertex未被访问,则递归访问其
    }
}

// BFS遍历  离初始点越近越优先访问。
void BFS(MGraph G, int v){
    int vertex;
    // 定义一个队列
    int queue[MaxV], front = 0, rear = 0;
    int visited[MaxV];
    // 初始化标志
    for (int i = 0; i < G.n; ++i) {
        visited[i] = 0;
    }
    // 输出顶点
    printf("%2d", v);
    visited[v] = 1;
    rear = (rear + 1) % MaxV;
    // 进队
    queue[rear] = v;
    // 队列不空循环
    while (front != rear){
        front = (front + 1) % MaxV;
        vertex = queue[front];  // 出队并赋w
        // 循环找到 v 的第一个连接点
        for (int i = 0; i < G.n; ++i) {
            // 首先遍历一遍这个,将其邻近点全部输出,然后continue回去,继续取出,再继续
            if (G.edges[vertex - 1][i].no == 1 && visited[G.vexs[i]] == 0)
            {
                printf("%2d", G.vexs[i]);
                visited[G.vexs[i]] = 1;
                rear = (rear + 1) % MaxV;  // 相邻顶点进队
                queue[rear] = G.vexs[i];
            }
        }
        // 返回,继续
        continue;
    }
}

// 辅助数组,用来每次筛选出权值最小的边的邻接点
typedef struct {
    Data_Type adjvex;  // 记录权值最小的边的起始点
    int lowcost; // 记录该边的权值
}closedge[MaxV];
closedge theclose;   // 创建一个全局数组,每个函数都会用到
// 在辅助数组中,找出权值最小的边的数组下标,就可以间接找到此边的终点顶点
int minimum(MGraph G, closedge close){
    int min = 9999;
    int min_i = -1;
    for (int i = 0; i < G.n; ++i) {
        // 权值为0,说明顶点已经归于最小生成树中,然后每次与min变量相比,最后找出最小的
        if (close[i].lowcost >0 && close[i].lowcost < min){
            min = close[i].lowcost;
            min_i = i;
        }
    }
    // 返回最小权值所在的数组下标
    return min_i;
}

// 最小生成树 - 普里姆算法, G为无向网,u为在网中选择的任意顶点作为起始点
void miniSpanTreePrim(MGraph G, Data_Type u){
    // 找到该起始点在顶点数组中的位置下标
    int k = LocateVex(&G, u);
    // 首先将与该起始点相关的所有边的信息写入辅助数组中相应的位置
    for (int i = 0; i < G.n; ++i) {
        if (i != k)
        {
            // 起始点
            theclose[i].adjvex = k;
            theclose[i].lowcost = G.edges[k][i].no;  // 权值
        }
    }
    // 由于起始点已经归为最小生成树,所以辅助数组对应位置的权值为0,这样遍历时不会被选中
    theclose[k].lowcost = 0;
    // 选择下一个点,并且更新数组中的信息
    for (int i = 1; i < G.n; ++i) {
        // 找出权值最小的边所在数组下标
        k = minimum(G, theclose);
        // 输出选择的路径
        printf("v%d, v%d\n", G.vexs[theclose[k].adjvex], G.vexs[k]);
        // 归于最小生成树的顶点的辅助数组中的权值设0
        theclose[k].lowcost = 0;
        // 信息辅助数组中存储的信息,由于此时树中新加了一个顶点,需要判断,由此顶点出发,到达其它各个顶点的权值是否比之前记录的权值还要小,如果还小,就刷新
        for (int j = 0; j < G.n; ++j) {
            if (G.edges[k][j].no < theclose[j].lowcost && G.edges[k][j].no != 0){
                theclose[j].adjvex = k;
                theclose[j].lowcost = G.edges[k][j].no;
            }
        }
    }
    printf("\n");
}

/*
 * 设有一组初始记录关键字序列(K1,K2,。。。,Kn),要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两个部分,其中左半部分的每个关键字均小于Ki,右半部分的每个关键字均大于等于Ki。
 */
// 假定 ki  i是下标,从 0开始
void quick(int List[], int Length, int i){
    int low = 0;
    int high = Length - 1;
    int privokey = List[i];
    int flag = 0;  // 标志位,这里毕竟不是快排,形似。
    while (low  < high){
        // high 指针左移,直到遇到比 privokey值小的
        while (low < high && List[high] >= privokey)
        {
            high--;
        }
        if (low < high)
        {
            if (flag == 0){
                List[i] = List[high];
            } else{
                List[low] = List[high];
                List[high] = 0;
            }
            flag++;
        }
        // low 指针右移,直到遇到比 privokey值大的
        while (low < high && List[low] <= privokey){
            low++;
        }
        if (low < high)
        {
            if (flag == 0){
                List[i] = List[low];
            } else{
                List[high] = List[low];
                List[low] = 0;
            }
            flag++;
        }
    }
    List[low] = privokey;
    for (int j = 0; j < Length; ++j) {
        printf("%3d", List[j]);
    }
}

// Kruskal算法
// 暂时不写

// 最短路径
// Dijkstra算法

// floyd 算法不写

// 主函数
int main(){
   // MGraph  G;  // 建立一个图的变量
   // CreateDG(&G);  // 调用构造函数,传入地址参数
   // PrintGraph(G);  // 输出图的二阶矩阵
//    MGraph T;
    //CreateDN(&T);  // 构造无向图
//    CreateUDN(&T);
//    miniSpanTreePrim(T, 1);
    //Prim(T, 1);
    //PrintGraph(T);
    //BFS(T, 1);
    //int List[] = {3, 8, 5, 9, 7, 2, 10, 4};
    // 3 8 5 9 4 2 10
    // 3   5 9 4 2 10 8
    // 3 2 5 9 4   10 8
    // 3 2 5   4 9 10 8
    // 3 2 5 4   9 10 8
    // 3 2 5 4 7 9 10 8
    //quick(List, 8, 4);
}

邻接表

//
// Created by Miku on 2020/6/23.
//

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>

#define InfoType int
#define Vertex_type int
#define  MaxV 5
typedef struct ANode{
    int adjvex;  // 该边的终点编号
    struct ANode *nextarc; // 指向下一条边的指针
    InfoType info;  // 该边的权值等信息
}ArcNode;

// 头结点类型
typedef struct Vnode{
    Vertex_type data;  // 顶点信息
    ArcNode *fristarc;  // 指向第一条边
}VNode;

// 邻接表
typedef  struct {
    VNode adjlist[MaxV]; // 邻接表
    int n, e; // 国中定点数,边数
}ALGraph;

int  visited[MaxV];
// DFS
void DFS(ALGraph *G, int v){
    ArcNode *p;
    int w;
    visited[v] = 1;
    printf("%d", v);  // 输出被访问顶点的编号
    // p 指向 v 的第一条边的边头结点
    p = G->adjlist[v].fristarc;
    while (p != NULL){
        w = p->adjvex;  // 终点编号
        if (visited[w] == 0)
            DFS(G, w);
        p = p->nextarc;   // 若 p 指向顶点 v 的下一条边的头节点
    }
}

// BFS
void BFS(ALGraph *G, int v){
    ArcNode  *p;
    int w, i;
    int queue[MaxV], front = 0, rear = 0;
    int visited[MaxV];
    for (int i = 0; i < MaxV; ++i) {
        visited[i] = 0;
    }
    printf("%2d", v);
    visited[v] = 1;
    rear = (rear + 1) % MaxV;
    queue[rear] = v;
    while (front != rear){
        // 出队
        front = (front + 1) % MaxV;
        w = queue[front];  // 出队并且赋予 w
        p = G->adjlist[w].fristarc; // 找出 w 的第一个邻接点
        while (p != NULL){
            if (visited[p->adjvex] != 0)
            {
                printf("%2d", p->adjvex);  // 访问
                visited[p->adjvex] = 1;
                rear = (rear+1) % MaxV;   // 相邻顶点入队
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;  // 找出 下一个相邻顶点
        }
    }
}


粉色的花瓣,美丽地缠绕在身上。依在风里。