美文网首页
图

图

作者: TomyZhang | 来源:发表于2019-05-12 23:36 被阅读0次

一、概念

图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为：G（V，E），其中，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。

注意：线性表中可以没有元素，称为空表。树中可以没有结点，叫做空树。但是在图中不允许没有顶点，可以没有边。

无向图

无向图 无向图解析

有向图

有向图 有向图解析

二、图的存储

1.邻接矩阵

使用数组的形式来储存数据。

有向图邻接矩阵

在有向图中，当一个顶点能够指向另外一个顶点，则矩阵中的值为1，否则为0。

无向图邻接矩阵

在无向图中，边是相当于两个顶点相互指向。

#include<stdio.h>
#define GRAPH_SIZE 5

int graph[GRAPH_SIZE][GRAPH_SIZE];

void initGraph() {
    for(int i=0; i<GRAPH_SIZE; i++) {
        for(int j=0; j<GRAPH_SIZE; j++) {
            graph[i][j] = 0;
        }
    }

    graph[0][2] = 1;
    graph[0][3] = 1;
    graph[1][3] = 1;
    graph[1][4] = 1;
    graph[2][0] = 1;
    graph[2][4] = 1;
    graph[3][0] = 1;
    graph[3][1] = 1;
    graph[4][1] = 1;
    graph[4][2] = 1;
}

void printGraph() {
    printf("printGraph:\n");
    for(int i=0; i<GRAPH_SIZE; i++) {
        for(int j=0; j<GRAPH_SIZE; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

void main() {
    initGraph();
    printGraph();
}

2.邻接表与逆邻接表

使用顶点以及其弧的指向来储存数据。

邻接表与逆邻接表 
#include<stdio.h>
#include<malloc.h>
#define GRAPH_SIZE 4

struct EdgeNode { //边结点
    int id; //弧头顶点
    EdgeNode *next; //弧尾相同，下一条边指针（对应出度指针）
};

struct VertexNode { //顶点结点
    int id;
    EdgeNode *firstOut; //出度指针
};

VertexNode graph[GRAPH_SIZE];

EdgeNode* mallocEdgeNode() {
    return (EdgeNode*)malloc(sizeof(EdgeNode));
}

void initGraph() {
    for(int i=0; i<GRAPH_SIZE; i++) {
        graph[i].id = i;
        graph[i].firstOut = NULL;
    }

    EdgeNode *temp = mallocEdgeNode();
    temp->id = 3;
    temp->next = graph[0].firstOut;
    graph[0].firstOut = temp;

    temp = mallocEdgeNode();
    temp->id = 0;
    temp->next = graph[1].firstOut;
    graph[1].firstOut = temp;

    temp = mallocEdgeNode();
    temp->id = 2;
    temp->next = graph[1].firstOut;
    graph[1].firstOut = temp;

    temp = mallocEdgeNode();
    temp->id = 0;
    temp->next = graph[2].firstOut;
    graph[2].firstOut = temp;

    temp = mallocEdgeNode();
    temp->id = 1;
    temp->next = graph[2].firstOut;
    graph[2].firstOut = temp;
}

void printGraph() {
    printf("printGraph:\n");
    for(int i=0; i<GRAPH_SIZE; i++) {
        printf("VertexNode %d ==> ", i);
        EdgeNode* edgeNode = graph[i].firstOut; //求出度
        while(edgeNode != NULL) {
            printf("%d ", edgeNode->id);
            edgeNode = edgeNode->next;
        }
        printf("\n");
    }
}

void main() {
    initGraph();
    printGraph();
}

#include<stdio.h>
#include<malloc.h>
#define GRAPH_SIZE 4

struct EdgeNode { //边结点
    int id; //弧尾顶点
    EdgeNode *next; //弧头相同，下一条边指针（对应入度指针）
};

struct VertexNode { //顶点结点
    int id;
    EdgeNode *firstIn; //入度指针
};

VertexNode graph[GRAPH_SIZE];

EdgeNode* mallocEdgeNode() {
    return (EdgeNode*)malloc(sizeof(EdgeNode));
}

void initGraph() {
    for(int i=0; i<GRAPH_SIZE; i++) {
        graph[i].id = i;
        graph[i].firstIn = NULL;
    }

    EdgeNode *temp = mallocEdgeNode();
    temp->id = 1;
    temp->next = graph[0].firstIn;
    graph[0].firstIn = temp;

    temp = mallocEdgeNode();
    temp->id = 2;
    temp->next = graph[0].firstIn;
    graph[0].firstIn = temp;

    temp = mallocEdgeNode();
    temp->id = 2;
    temp->next = graph[1].firstIn;
    graph[1].firstIn = temp;

    temp = mallocEdgeNode();
    temp->id = 1;
    temp->next = graph[2].firstIn;
    graph[2].firstIn = temp;

    temp = mallocEdgeNode();
    temp->id = 0;
    temp->next = graph[3].firstIn;
    graph[3].firstIn = temp;
}

void printGraph() {
    printf("printGraph:\n");
    for(int i=0; i<GRAPH_SIZE; i++) {
        printf("VertexNode %d <== ", i);
        EdgeNode* edgeNode = graph[i].firstIn; //求入度
        while(edgeNode != NULL) {
            printf("%d ", edgeNode->id);
            edgeNode = edgeNode->next;
        }
        printf("\n");
    }
}

void main() {
    initGraph();
    printGraph();
}

3.十字链表

图 十字链表 
#include<stdio.h>
#include<malloc.h>
#define GRAPH_SIZE 4

struct EdgeNode { //边结点
    int tailId; //弧尾顶点
    int headId; //弧头顶点
    EdgeNode *headLink; //弧头相同，下一条边指针（对应入度指针）
    EdgeNode *tailLink; //弧尾相同，下一条边指针（对应出度指针）
};

struct VertexNode { //顶点结点
    int id;
    EdgeNode *firstIn; //入度指针
    EdgeNode *firstOut; //出度指针
};

VertexNode graph[GRAPH_SIZE];

EdgeNode* mallocEdgeNode() {
    return (EdgeNode*)malloc(sizeof(EdgeNode));
}

void initGraph() {
    for(int i=0; i<GRAPH_SIZE; i++) {
        graph[i].id = i;
        graph[i].firstIn = NULL;
        graph[i].firstOut = NULL;
    }

    EdgeNode *temp = mallocEdgeNode();
    temp->tailId = 0; //弧尾顶点
    temp->headId = 3; //弧头顶点
    temp->headLink = graph[temp->headId].firstIn; //弧头相同，下一条边指针
    graph[temp->headId].firstIn = temp;
    temp->tailLink = graph[temp->tailId].firstOut; //弧尾相同，下一条边指针
    graph[temp->tailId].firstOut = temp;

    temp = mallocEdgeNode();
    temp->tailId = 1; //弧尾顶点
    temp->headId = 0; //弧头顶点
    temp->headLink = graph[temp->headId].firstIn; //弧头相同，下一条边指针
    graph[temp->headId].firstIn = temp;
    temp->tailLink = graph[temp->tailId].firstOut; //弧尾相同，下一条边指针
    graph[temp->tailId].firstOut = temp;

    temp = mallocEdgeNode();
    temp->tailId = 2; //弧尾顶点
    temp->headId = 0; //弧头顶点
    temp->headLink = graph[temp->headId].firstIn; //弧头相同，下一条边指针
    graph[temp->headId].firstIn = temp;
    temp->tailLink = graph[temp->tailId].firstOut; //弧尾相同，下一条边指针
    graph[temp->tailId].firstOut = temp;

    temp = mallocEdgeNode();
    temp->tailId = 1; //弧尾顶点
    temp->headId = 2; //弧头顶点
    temp->headLink = graph[temp->headId].firstIn; //弧头相同，下一条边指针
    graph[temp->headId].firstIn = temp;
    temp->tailLink = graph[temp->tailId].firstOut; //弧尾相同，下一条边指针
    graph[temp->tailId].firstOut = temp;

    temp = mallocEdgeNode();
    temp->tailId = 2; //弧尾顶点
    temp->headId = 1; //弧头顶点
    temp->headLink = graph[temp->headId].firstIn; //弧头相同，下一条边指针
    graph[temp->headId].firstIn = temp;
    temp->tailLink = graph[temp->tailId].firstOut; //弧尾相同，下一条边指针
    graph[temp->tailId].firstOut = temp;
}

void printGraph() {
    printf("printGraph:\n");
    for(int i=0; i<GRAPH_SIZE; i++) {
        printf("VertexNode %d ==> ", i);
        EdgeNode* edgeNode = graph[i].firstOut; //求出度
        while(edgeNode != NULL) {
            printf("%d ", edgeNode->headId);
            edgeNode = edgeNode->tailLink;
        }
        printf("\n");

        printf("VertexNode %d <== ", i);
        edgeNode = graph[i].firstIn; //求入度
        while(edgeNode != NULL) {
            printf("%d ", edgeNode->tailId);
            edgeNode = edgeNode->headLink;
        }
        printf("\n\n");
    }
}

void main() {
    initGraph();
    printGraph();
}

三、图的遍历

1.深度优先遍历

顺着一个顶点不断向下遍历，当遍历到的顶点与前面搜索过的顶点形成环的时候就停止。有点类似树的前序遍历。

#include<stdio.h>
#define GRAPH_SIZE 5

int graph[GRAPH_SIZE][GRAPH_SIZE];
bool visit[GRAPH_SIZE]; //顶点的访问标志

void initGraph() {
    for(int i=0; i<GRAPH_SIZE; i++) {
        for(int j=0; j<GRAPH_SIZE; j++) {
            graph[i][j] = 0;
        }
    }

    graph[0][2] = 1;
    graph[0][3] = 1;
    graph[1][3] = 1;
    graph[1][4] = 1;
    graph[2][0] = 1;
    graph[2][4] = 1;
    graph[3][0] = 1;
    graph[3][1] = 1;
    graph[4][1] = 1;
    graph[4][2] = 1;
}

void printGraph() {
    printf("printGraph:\n");
    for(int i=0; i<GRAPH_SIZE; i++) {
        for(int j=0; j<GRAPH_SIZE; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
}

void DFS(int index) {
    visit[index] = true;
    printf("visit: %d\n", index);
    for(int i=0; i<GRAPH_SIZE; i++) {
        if(graph[index][i] == 0 || visit[i] == true) {
            continue;
        }

        DFS(i);
    }
}

void main() {
    initGraph();
    printGraph();
    
    for(int i=0; i<GRAPH_SIZE; i++) {
        visit[i] = false;   
    }
    DFS(0);
}

2.广度优先遍历

按层来不断进行遍历。

#include<stdio.h>
#include<malloc.h>
#define GRAPH_SIZE 5

struct GraphNode { //图的顶点结点
    int id;
};

GraphNode graphNode[GRAPH_SIZE]; //图的顶点
int graph[GRAPH_SIZE][GRAPH_SIZE]; //图的边
bool visit[GRAPH_SIZE]; //顶点的访问标志

//----------Queue start----------
struct Node { //队列结点
    int graphIndex; //图使用数组存储顶点结点，因此队列结点存储图的顶点索引即可，通过该索引可以在数组中找到图的顶点结点
    Node* next;
};

struct Queue { //队列数据结构
    Node* front;
    Node* rear;
    int size;
};

Node* mallocNode() { //申请结点内存
    Node* node = (Node*)malloc(sizeof(Node));
    return node;
}

void initQueue(Queue* queue) { //初始化队列
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

void enQueue(Queue* queue, int graphIndex) { //入队，插入队尾
    Node* node = mallocNode();
    node->graphIndex = graphIndex;
    node->next = NULL;
    if(queue->rear == NULL) {
        queue->front = queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->size++;
}

Node* deQueue(Queue* queue) { //出队，删除队头
    Node* node;
    if(queue->front == NULL) {
        node = NULL;
    } else {
        node = queue->front;
        queue->front = queue->front->next;
        if(queue->front == NULL) {
            queue->rear = NULL;
        }
        queue->size--;
    }
    return node;
}
//----------Queue end----------

void initGraph() {
    for(int i=0; i<GRAPH_SIZE; i++) { //初始化顶点
        graphNode[i].id = i;
    }

    for(int i=0; i<GRAPH_SIZE; i++) { //初始化边
        for(int j=0; j<GRAPH_SIZE; j++) {
            graph[i][j] = 0;
        }
    }

    graph[0][2] = 1;
    graph[0][3] = 1;
    graph[1][3] = 1;
    graph[1][4] = 1;
    graph[2][0] = 1;
    graph[2][4] = 1;
    graph[3][0] = 1;
    graph[3][1] = 1;
    graph[4][1] = 1;
    graph[4][2] = 1;
}

void printGraph() {
    printf("printGraph:\n");
    for(int i=0; i<GRAPH_SIZE; i++) {
        printf("%d ", graphNode[i].id);
    }
    printf("\n\n");

    for(int i=0; i<GRAPH_SIZE; i++) {
        for(int j=0; j<GRAPH_SIZE; j++) {
            printf("%d ", graph[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void BFS(int index) { //使用队列，按照"从上到下，从左到右"规则，进行广度优先遍历
    Queue queue;
    initQueue(&queue);

    enQueue(&queue, index); //入队
    visit[index] = true;
    while(queue.size != 0) { //循环结束条件：队列空
        Node* deleteNode = deQueue(&queue); //出队
        printf("%d ", deleteNode->graphIndex);
        for(int i=0; i<GRAPH_SIZE; i++) {
            if(graph[deleteNode->graphIndex][i] == 0 || visit[i] == true) {
                continue;
            }
            enQueue(&queue, i);
            visit[i] = true;
        }
        free(deleteNode); //释放被删除的结点内存
    }
}

void main() {
    initGraph();
    printGraph();
    
    for(int i=0; i<GRAPH_SIZE; i++) {
        visit[i] = false;
    }
    BFS(0);
    printf("\n");
}

四、最小生成树

当遍历的时候涉及边的权值问题，就要使用最小生成树来解决。


最小生成树-前 最小生成树-后

1.普里姆算法（Prim）

过程：
1.选定一个点A，放入点集合。
2.关于A的所有的边放入 待选边集合。
3.从待选边集合选取权值最小的边 A - F (1)，放入边集合。
4.边集合中提取出未在点集合的点F，放入点集合。
5.刷新待选边集合，列出所有A和F有关的边。
6.选出权值最小且不会与当前已选边形成闭环的边，然后放入边集合。
7.以此类推，得出所有边，既是最小生成树。

普里姆算法（Prim）-后

点集合 ==> 待选边集合(小根堆) ==> 最终边集合(取最小值) ==> 重复

2.克鲁斯卡尔算法（Kruskal）

过程：
1.列出所有边的集合。
2.依次选取权值最小的边，同时将涉及的点加入点集合。
3.选取的边不能与已选边构成闭合。
4.当点集合中出现了所有点以后，需要让所有点能连通，形成生成树（边 = 点 - 1）。

克鲁斯卡尔算法（Kruskal）-后

待选边集合(小根堆) ==> 最终边集合(取最小值) ==> 点集合 ==> 重复

五、最短路径

1.深度优先搜索算法（两点最短路径，有权图）

#include<stdio.h>
#define INF 9999999 //表示无穷大
#define GRAPH_SIZE 6 //定义图的顶点数量（顶点索引从1开始算起，这里定义的值为实际顶点数量加1）

int graph[GRAPH_SIZE][GRAPH_SIZE]; //图
bool visit[GRAPH_SIZE]; //顶点访问标志
int path[GRAPH_SIZE]; //路径
int pathIndex; //路径索引
int min = INF; //最小值，初始化为无穷大

void DFS(int cur, int to, int curDistance) { //cur：当前顶点，to：目标顶点，curDistance：当前路径距离
    if(cur == to) { //找到目标顶点
        for(int i=0; i<pathIndex; i++) { // 输出当前路径
            printf("%d ", path[i]);
        }
        printf("==> %d\n", curDistance); //当前路径距离
 
        if(curDistance < min) { //取最小值作为最终输出结果
            min = curDistance;
        }
        return;
    }
 
    for(int i=1; i<=GRAPH_SIZE-1; i++) {
        if(graph[cur][i] == INF || visit[i] == true) { //cur->i路径不可达，或者i已访问
            continue;
        }
        visit[i] = true; //设置顶点i为已访问
        path[pathIndex++] = i; //将顶点i加入路径，然后将路径索引加1
        DFS(i, to, curDistance+graph[cur][i]); //DFS
        visit[i] = false; // 上一步DFS探索完毕后, 设置顶点i为未访问
        pathIndex--; //将路径索引减1，进行下一步DFS探索
    }
}

void main() {
    for (int i=1; i<=GRAPH_SIZE-1; i++) { //初始化边的权值,顶点索引从1开始算起
        for (int j=1; j<=GRAPH_SIZE-1; j++) {
            if(i == j) {
                graph[i][j] = 0; //自己到自己，权值初始化为0
            } else {
                graph[i][j] = INF; //其它情况，权值初始化为无穷大
            }
        }
    }
 
    //初始化边的权值,顶点索引从1开始算起
    graph[1][2] = 2;
    graph[2][3] = 3; 
    graph[3][1] = 4;
    graph[3][4] = 4;  
    graph[4][5] = 5;
    graph[5][3] = 3; 
    graph[2][5] = 7;
    graph[1][5] = 10; 

    for(int i=1; i<=GRAPH_SIZE-1; i++) { //初始化顶点访问标志，顶点索引从1开始算起
        visit[i] = false;
    }
    pathIndex = 0; //路径索引初始化为0

    visit[1] = true; //将位于起点的顶点访问标志设置为true，表示该顶点已访问
    path[pathIndex++] = 1; //将位于起点的顶点索引保存到路径中，然后将路径索引加1
    DFS(1, 5, 0);
    printf("min: %d\n", min);
}

2.广度优先搜索算法（两点最短路径，无权图）

#include<stdio.h>
#include<malloc.h>
#define GRAPH_SIZE 6 //定义图的顶点数量（顶点索引从1开始算起，这里定义的值为实际顶点数量加1）

int graph[GRAPH_SIZE][GRAPH_SIZE]; //图
bool visit[GRAPH_SIZE]; //顶点访问标志

//----------Queue start----------
struct Node { //队列结点
    int graphIndex; //图使用数组存储顶点结点，因此队列结点存储图的顶点索引即可，通过该索引可以在数组中找到图的顶点结点
    int distance;
    Node* next;
};

struct Queue { //队列数据结构
    Node* front;
    Node* rear;
    int size;
};

Node* mallocNode() { //申请结点内存
    Node* node = (Node*)malloc(sizeof(Node));
    return node;
}

void initQueue(Queue* queue) { //初始化队列
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

void enQueue(Queue* queue, int graphIndex, int distance) { //入队，插入队尾
    Node* node = mallocNode();
    node->graphIndex = graphIndex;
    node->distance = distance;
    node->next = NULL;
    if(queue->rear == NULL) {
        queue->front = queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }
    queue->size++;
}

Node* deQueue(Queue* queue) { //出队，删除队头
    Node* node;
    if(queue->front == NULL) {
        node = NULL;
    } else {
        node = queue->front;
        queue->front = queue->front->next;
        if(queue->front == NULL) {
            queue->rear = NULL;
        }
        queue->size--;
    }
    return node;
}
//----------Queue end----------

int BFS(int cur, int to) { //使用队列，按照"从上到下，从左到右"规则，进行广度优先遍历
    if(cur == to) { //当前顶点即是目标顶点
        return 0;
    }

    Queue queue;
    initQueue(&queue);

    enQueue(&queue, cur, 0); //入队
    visit[cur] = true;
    while(queue.size != 0) { //循环结束条件：队列空
        Node* deleteNode = deQueue(&queue); //出队
        for(int i=1; i<=GRAPH_SIZE-1; i++) {
            if(graph[deleteNode->graphIndex][i] == 0 || visit[i] == true) {
                continue;
            }
            if(i == to) { //找到目标顶点
                return deleteNode->distance+1;  
            }
            enQueue(&queue, i, deleteNode->distance+1);
            visit[i] = true;
        }
        free(deleteNode); //释放被删除的结点内存
    }
}

void main() {
    for (int i=1; i<=GRAPH_SIZE-1; i++) { //初始化边,顶点索引从1开始算起
        for (int j=1; j<=GRAPH_SIZE-1; j++) {
            graph[i][j] = 0; //0表示不可达，1表示可达
        }
    }
 
    //初始化边,顶点索引从1开始算起
    graph[1][2] = 1;
    graph[2][3] = 1; 
    graph[3][1] = 1;
    graph[3][4] = 1;  
    graph[4][5] = 1;
    graph[5][3] = 1; 
    graph[2][5] = 1;
    graph[1][5] = 1; 

    for(int i=1; i<=GRAPH_SIZE-1; i++) { //初始化顶点访问标志，顶点索引从1开始算起
        visit[i] = false;
    }
    int distance = BFS(1, 3);
    printf("min distance: %d\n", distance);
}

3.迪杰斯特拉算法（单源最短路径，有权图，权重无负值）

迪杰斯特拉算法过程

点集合 ==> 待选边集合 ==> 最终边集合 ==> 重复
顶点结点内容：距离源点总距离、上一个顶点结点

4.Bellman-Ford算法（单源最短路径，有权图，权重有负值）

Bellman-Ford算法过程

第i次遍历（1 <= i <= 顶点数-1） ==> 经过一条边进行松弛 ==> 经过两条边进行松弛 ==> 重复

5.弗洛伊德算法（多源最短路径）

弗洛伊德算法过程

三重循环：

for(int k=1; k<=n; k++) {
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=n; j++) {
            if(i != j && j != k && i != k) {
                if(a[i][j] > a[i][k] + a[k][j]) {
                    a[i][j] = a[i][k] + a[k][j];
                }
            }
        }
    }
}

相关文章

网友评论

      本文标题：图

      本文链接：https://www.haomeiwen.com/subject/obfkaqtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|图|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！