图结构_邻接矩阵

结构 - 图结点 GNode - PtrToGNode - MGraph

1. 顶点数Nv
2. 边数Ne
3. 邻接矩阵二维数组G
4. 顶点数据Data

结构 - 边结构

1. 无向边(V1,V2),V1 V2为顶点
2. 权重Weight

创建零图

1. 创建一个有VertexNum个顶点0条边的图MGraph
2. 遍历,初始化二维数组,顶点的权重为无限大或-1

向图中插入边

1. 插入边<v1,v2>,二维数组的顶点V1,V2写入权重Weight
2. 如果是无向图还需要插入反向点，对称矩阵

创建图,含顶点与边

1. 读入顶点个数，构造含有Nv个顶点无边的图
2. 读入边数Ne
3. 循环读入一条边,并插入Graph中
4. 如果顶点有数据的话的，读入数据

是否无连接边

1. 邻接矩阵是否为INFINITY或-1

BFS广度优先搜索邻接矩阵图

1. 创建队列Q,访问结点S并将结点S加入队列Q
2. 遍历队列至为空
3. 将元素移出队列得到V
4. 遍历所有的顶点
5. 若W是V的邻接点并且未访问过
6. 访问新的结点W并将新结点W加入队列

DFS邻接矩阵的深度优先搜索

1. 先访问结点v，并将标记置为true
2. 遍历与V相邻的结点
3. 找到下一个与V点相交的点，同时该点未被访问
4. 递归与V相邻的第一个未访问的结点W

编码

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

#define MaxVertexNum 100
#define INFINITY 65535
#define MaxSize 1024

typedef int Vertex;// 用整形表示顶点
typedef int WeightType; // 权重
typedef char DataType;// 顶点数据，字符型
bool Visited[MaxVertexNum];

typedef struct GNode *PtrToGNode;
typedef PtrToGNode MGraph;
struct GNode {
    //1.顶点数Nv
    int Nv;
    //2.边数Ne
    int Ne;
    //3.邻接矩阵二维数组G
    WeightType G[MaxVertexNum][MaxVertexNum];
    //4.顶点数据Data
    DataType Data[MaxVertexNum];
};

typedef struct ENode *PtrToENode;
typedef PtrToENode Edge;
struct ENode {
    //1.无向边(V1,V2),V1 V2为顶点
    Vertex V1, V2;
    //2.权重Weight
    WeightType Weight;
};


// 创建零图
MGraph CreateGraph(int VertexNum) {
    // 1.创建一个有VertexNum个顶点0条边的图MGraph
    Vertex V, W;
    MGraph Graph;
    Graph = (MGraph) malloc(sizeof(struct GNode));
    Graph->Nv = VertexNum;
    Graph->Ne = 0;
    // 2.遍历,初始化二维数组,顶点的权重为无限大或-1
    for (V = 0; V < Graph->Nv; V++) {
        for (W = 0; W < Graph->Nv; W++)
            Graph->G[V][W] = INFINITY;
    }
    return Graph;
}

// 向图中插入边
void InsertEdge(MGraph Graph, Edge E) {
    // 1.插入边<v1,v2>,二维数组的顶点V1,V2写入权重Weight
    Graph->G[E->V1][E->V2] = E->Weight;
    // 2.如果是无向图还需要插入反向点，对称矩阵
    Graph->G[E->V2][E->V1] = E->Weight;
}

// 创建图,含顶点与边
MGraph BuildGraph() {
    MGraph Graph;
    Edge E;
    Vertex V;
    int Nv, i;
    //1.读入顶点个数，构造含有Nv个顶点无边的图
    scanf("%d", &Nv);
    Graph = CreateGraph(Nv);

    // 2.读入边数Ne
    scanf("%d", &(Graph->Ne));
    if (Graph->Ne != 0) {
        E = (Edge) malloc(sizeof(struct ENode));
        for (i = 0; i < Graph->Ne; i++) {
            // 3.循环读入一条边,并插入Graph中
            scanf("%d %d %d", &E->V1, &E->V2, &E->Weight);
            InsertEdge(Graph, E);
        }
    }
    // 4.如果顶点有数据的话的，读入数据
    for (V = 0; V < Graph->Nv; V++) {
        scanf(" %c ", &(Graph->Data[V]));
    }
    return Graph;
}

// 是否无连接边
bool isEdge(MGraph Graph, Vertex V, Vertex W) {
    return Graph->G[V][W] < INFINITY ? true : false;
}

// 访问结点
void Visit(Vertex V) {
    printf("正在访问顶点%d\n", V);
}

// 广度优先搜索邻接矩阵图
void BFS(MGraph Graph, Vertex S, void(*Visit)(Vertex)) {
    Queue Q;
    Vertex V, W;
    // 1.创建队列Q,访问结点S并将结点S加入队列Q
    Q = CreateQueue(MaxSize);
    Visit(S);
    Visited[S] = true;
    AddQ(Q, S);
    // 2.遍历队列至为空
    while (!IsEmpty(Q)) {
        //3.将元素移出队列得到V
        V = DeleteQ(Q);
        //4.遍历所有的顶点
        for (W = 1; W <= Graph->Nv; W++) {
            //5.若W是V的邻接点并且未访问过
            if (!Visited[W] && isEdge(Graph, V, W)) {
                // 6.访问新的结点W并将新结点W加入队列
                Visit(W);
                Visited[W] = true;
                AddQ(Q, W);
            }
        }
    }
}

// 邻接矩阵的深度优先搜索
void DFS(MGraph Graph, Vertex V, void(*Visit)(Vertex)) {
    // 1.先访问结点v，并将标记置为true
    Visit(V);
    Visited[V] = true;
    Vertex W;
    // 2.遍历与V相邻的结点
    for (W = 0; W < Graph->Nv; W++) {
        //3.找到下一个与V点相交的点，同时该点未被访问
        if (Graph->G[V][W] && !Visited[W]) {
            // 4.递归与V相邻的第一个未访问的结点W
            DFS(Graph, W, Visit);
        }
    }
}

// 求最短距离的顶点
Vertex FindMinDist(MGraph Graph, int dist[], int collected[]) {
    // 0.变量MinDist最短距离，MinV为对应的顶点
    Vertex MinV, V;
    int MinDist = INFINITY;
    // 1.遍历所有顶点
    for (V = 0; V < Graph->Nv; V++) {
        // 2.若V未被收录，且dist[V]更小
        if (collected[V] = false && dist[V] < MinDist) {
            //3.更新最小距离,更新对应顶点
            MinDist = dist[V];
            MinV = V;
        }
    }
    //4.若找到最小dist,返回对应的顶点下标,否则返回-1
    if (MinDist < INFINITY)
        return MinV;
    else
        return -1;
}

// 单源最短路算法 - 迪杰斯特拉算法
bool Dijkstra(MGraph Graph, int dist[], int path[], Vertex S) {
    // 0.数组dist[w]为顶点S到任意顶点w的距离(权重和),
    // 数组path[w]为到顶点w的最短路径的前驱顶点,
    // 数组collected[w]=true为顶点w找到最短路径
    int collected[MaxVertexNum];
    Vertex V, W;
    //1.初始化dist[v]为边的权重，path为s或-1
    for (V = 0; V < Graph->Nv; V++) {
        dist[V] = Graph->G[S][V];
        if (dist[V] < INFINITY)
            path[V] = S;
        else
            path[V] = -1;
        collected[V] = false;
    }
    //2.先将起点S收入集合collected，距离dist[s]为0
    dist[S] = 0;
    collected[S] = true;
    // 3.遍历
    while (1) {
        //4.V为未被收录顶点中dist最小者, S到V路径最短
        V = FindMinDist(Graph, dist, collected);
        //5.若这样的V不存在,跳出循环
        if (V == -1) {
            break;
        }
        //6.收录V
        collected[V] = true;
        //7.遍历图中的每个顶点W
        for (W = 0; W < Graph->Nv; W++) {
            //8.若W是V的邻接点并且未被收录
            if (collected[W] == false && Graph->G[V][W] < INFINITY) {
                //9.若有负边,不能正确解决，返回错误标记
                if (Graph->G[V][W] < 0)
                    return false;
                // 10.若收录V使得dist[W]变小,更新dist[W],更新S到W的路径path[W]
                if (dist[V] + Graph->G[V][W] < dist[W]) {
                    dist[W] = dist[V] + Graph->G[V][W];
                    path[W] = V;
                }
            }
        }
    }
    return true;
}

// 求两点i,j间的最短距离
bool Floyd(MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum]) {
    // 0.数组D[i][j]为i,j两点间的最短路径,path[i][j]为i,j最短路径,点j的前驱点
    Vertex i, j, k;
    // 1.初始化Vi,Vj的最短路径D为两点间的权重,路径path为-1
    for (i = 0; i < Graph->Nv; i++) {
        for (j = 0; j < Graph->Nv; j++) {
            D[i][j] = Graph->G[i][j];
            path[i][j] = -1;
        }
    }
    // 2.三重遍历，找到任意两点i,j间的最短距离及路径
    for (k = 0; k < Graph->Nv; k++) {
        for (i = 0; i < Graph->Nv; i++) {
            for (j = 0; j < Graph->Nv; j++) {
                // 3.如果找到新的k点，使得ik加kj距离小于原来的值，更新距离和路径
                if (D[i][k] + D[k][j] < D[i][j]) {
                    D[i][j] = D[i][k] + D[k][j];
                    // 4.如果存在负值圈，返回false
                    if (i == j && D[i][j] < 0)
                        return false;
                    path[i][j] = k;
                }
            }
        }
    }
    return true;
}

小结

1. 注意顶点是从0开始，还是从1开始；遍历时需要注意