图原创

『图(Graph)』，由顶点集V和边集E组成，记为G=(V,E)或G=<V,E>，其中V(G)表示图G中定点的有限非空集，E(G)表示图G中顶点之间的关系(即边)集合。

顶点:vertex 边:edeg
图分为：有向图、无向图。

# 有向图

有向边(也称为弧)。有向边的图称为「有向图」。「弧」是顶点的有序对，记为<v,w>，其中v称为「弧尾」，w称为「弧头」(带箭头端)。<v,w>称为从v到w的弧，也称为v邻接到w。

有向图的表示：
G1=(V1,E1);   
V1={1,2,3}               //  顶点集合
E1={<1,2>,<2,1>,<2,3>}   // 边集合，<>尖括号表示有向边

$latex有向图示例$

# 无向图

无向变(简称边)。无向边的图称为「无向图」。「边」是顶点的无序对，记为<v,w>或<w,v>，v和w互为邻接点。边(v,w)依附于v和w，或称边(v,w)和v,w相互关联。

无向图的表示：
G2=(V2,E2);   
V2={1,2,3,4}               //  顶点集合
E2={(1,2),(1,3),(1,4),(2,4)}   // 边集合，()小括号表示无向边

$latex无向图示例$

# 图的存储

# 邻接矩阵法

用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息(即各边的关系)。存储顶点之间邻接关系的二维数组称为『邻接矩阵』。

有 向 图 无 向 图

1代表该边存在,0表示该边不存在。如:

有向图:[0,1]为1，表示<1,2>;[0,2]为1，表示<1,3>;
无向图：[0,3]为1，表示(1,4);[3,0]为1，表示(1,4);

警告

当一个图为稀疏图时，邻接矩阵浪费空间。

# 邻接表法

『邻接表』是指对图G中的每个顶点vi建立一个单链表。邻接表法结合了顺序存储和链式存储，大大减少了不必要的空间浪费。
$latex邻接表示例$

笔记

邻接表可以和邻接矩阵互相转化。

# 图的遍历

# 深度优先遍历

笔记

思路：

首先访问图中某一顶点v，然后由该顶点v出发，访问与v邻接且未被访问的任一顶点w1，在访问w1邻接且未被访问过的任一顶点w2……重复该过程。当不能再继续往下访问时，依次回退到最近被访问的顶点，若它还有邻接顶点未被访问过吗，则从该点继续上述过程，直到图中所有顶点均被访问。

# 广度优先遍历

笔记

思路：

首先访问其实顶点v，接着访问由v出发，依次访问v的各个未被访问过的邻接顶点w1,w2,w3……，然后依次访问w1,w2,w3……的所有未被访问过的邻接顶点；再从这些访问过的顶点出发，访问他们所有未被访问过的邻接顶点，直到图中所有顶点均被访问。

# 图实例

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

#define MaxVertexNum 15 // 最大点数
#define LENGTH(a) (sizeof(a)/sizeof(a[0])) //计算数组长度的宏
typedef char VertexType;  // 边的数据类型
typedef int EdgeType; // 点的数据类型
// 图的邻接矩阵 结构体
typedef struct{
    VertexType Vex[MaxVertexNum]; // 顶点集合
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // 边集合
    int vex_num,arc_num; // 图的顶点数和边数
}MGraph;

// 邻接表 结构体
typedef struct _ENode{ // 弧头结构体
    int ivex;  // 本条弧的弧头
    struct _ENode *next_edge; // 指向下一条弧的指针
}ENode,*pENode;
typedef struct _VNode{ // 邻接表中顶点结构体
    char data; // 顶点信息
    ENode *first_edge; // 该顶点的第一条弧  调用 ENode 结构体
}VNode;
typedef struct _LGraph{
    int vex_num; // 图的顶点数
    int edge_num; // 图的边数
    VNode vexs[MaxVertexNum]; // 顶点数组，调用 VNode 结构体
}LGraph,*pLGraph;

static int get_postion(LGraph g, char c){ //
    for (int i = 0; i < g.vex_num; i++) {
        if(g.vexs[i].data == c)
            return i; // 获取顶点在顶点数组的下标
    }
    return -1;
}

static void link_last(ENode *list, ENode *node)
{
    ENode *p = list;

    while(p->next_edge)
        p = p->next_edge;
    p->next_edge = node;
}


// 创建无向图
pLGraph create_example_lgraph(){
    char c1,c2;
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//    char edges[][2] = {
//        {'A', 'C'},
//        {'A', 'D'},
//        {'A', 'F'},
//        {'B', 'C'},
//        {'C', 'D'},
//        {'E', 'G'},
//        {'F', 'G'}
//    };
    char edges[][2] = {
        {'A', 'B'},
        {'B', 'C'},
        {'B', 'E'},
        {'B', 'F'},
        {'C', 'E'},
        {'D', 'C'},
        {'E', 'B'},
        {'E', 'D'},
        {'F', 'G'}
    };
    int vlen = LENGTH(vexs); // 一维数组，计算出有多少个元素
    int elen = LENGTH(edges); // 二维数组，计算出有多少行
    int i,p1,p2;
    pENode node1,node2;
    pLGraph pG;
    if((pG = (pLGraph)malloc(sizeof(LGraph))) == NULL){ // 考虑内存空间不足的情况
        return NULL;
    }
    memset(pG,0, sizeof(LGraph)); // 把申请的空间初始化为零

    pG->vex_num = vlen; //初始化邻接表的顶点数
    pG->edge_num = elen; //初始化邻接表的边数
    for (i = 0; i < pG->vex_num; i++) { // 初始化邻接表各顶点
        pG->vexs[i].data = vexs[i];
        pG->vexs[i].first_edge=NULL;
    }
    for (i = 0; i < pG->edge_num; i++) { // 初始化邻接表边
       c1=edges[i][0];
       c2=edges[i][1];
       p1=get_postion(*pG,c1); //
       p2=get_postion(*pG,c2);
        // 初始化node1
        node1 = (ENode*) calloc(1, sizeof(ENode)); // calloc 申请空间，并初始化为零
        node1->ivex = p2;
        //将node1链接到p1所指的链表末尾
        if(pG->vexs[p1].first_edge ==NULL){
            pG->vexs[p1].first_edge = node1;
        }else{
            link_last(pG->vexs[p1].first_edge,node1);
        }
        // 初始化node2   针对无向图
        node2 = (ENode*) calloc(1, sizeof(ENode)); // calloc 申请空间，并初始化为零
        node2->ivex = p1;
        if(pG->vexs[p2].first_edge ==NULL){
            pG->vexs[p2].first_edge = node2;
        }else{
            link_last(pG->vexs[p2].first_edge,node2);
        }
    }

    return pG;
}

// 创建有向图
pLGraph create_example_lgraph_s(){
    char c1,c2;
    char vexs[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
    char edges[][2] = {
            {'A', 'B'},
            {'B', 'C'},
            {'B', 'E'},
            {'B', 'F'},
            {'C', 'E'},
            {'D', 'C'},
            {'E', 'B'},
            {'E', 'D'},
            {'F', 'G'}
    };
    int vlen = LENGTH(vexs); // 一维数组，计算出有多少个元素
    int elen = LENGTH(edges); // 二维数组，计算出有多少行
    int i,p1,p2;
    pENode node1,node2;
    pLGraph pG;
    if((pG = (pLGraph)malloc(sizeof(LGraph))) == NULL){ // 考虑内存空间不足的情况
        return NULL;
    }
    memset(pG,0, sizeof(LGraph)); // 把申请的空间初始化为零

    pG->vex_num = vlen; //初始化邻接表的顶点数
    pG->edge_num = elen; //初始化邻接表的边数
    for (i = 0; i < pG->vex_num; i++) { // 初始化邻接表各顶点
        pG->vexs[i].data = vexs[i];
        pG->vexs[i].first_edge=NULL;
    }
    for (i = 0; i < pG->edge_num; i++) { // 初始化邻接表边
        c1=edges[i][0];
        c2=edges[i][1];
        p1=get_postion(*pG,c1); //
        p2=get_postion(*pG,c2);
        // 初始化node1
        node1 = (ENode*) calloc(1, sizeof(ENode)); // calloc 申请空间，并初始化为零
        node1->ivex = p2;
        //将node1链接到p1所指的链表末尾
        if(pG->vexs[p1].first_edge ==NULL){
            pG->vexs[p1].first_edge = node1;
        }else{
            link_last(pG->vexs[p1].first_edge,node1);
        }
    }

    return pG;
}

void print_lgraph(LGraph g){
    pENode node;
    printf("邻接表：\n");
    for (int i = 0; i < g.vex_num; ++i) {
        printf("%d(%c):",i,g.vexs[i].data);
        node =g.vexs[i].first_edge;
        while( node != NULL){
            printf("%d(%c)",node->ivex,g.vexs[node->ivex].data);
            node=node->next_edge;
        }
        printf("\n");
    }
}

//深度优先遍历
static void DFS(LGraph g,int i,int *visited){ // 因为visited是一个数组指针，因此需要使用*,不然得改成 visited[]
    ENode *node;
    visited[i] = 1; // 标记访问
    printf("%2c",g.vexs[i].data); //打印该点数据
    node = g.vexs[i].first_edge; //指针偏移
    while ( node != NULL){
        if(!visited[node->ivex]){ // 判断对应顶点是否被访问过
            DFS(g,node->ivex,visited);
        }
        node = node->next_edge; // 下一条边
    }
}
void DFSTraverse(LGraph g){
    int visited[MaxVertexNum]; // 记录已经访问过的顶点

    for (int i = 0; i < g.vex_num; i++) {
        visited[i] = 0; //初始化
    }
    for (int i = 0; i < g.vex_num; i++) {
        if(!visited[i]){
            DFS(g,i,visited);
        }
    }
    printf("\n");
}
// 广度优先遍历
void BFS(LGraph g){
    int head =0,rear=0;
    int queue[MaxVertexNum],visited[MaxVertexNum];// queue 辅助队列；visited记录已访问过的顶点
    pENode node;
    int j,k;
    for (int i = 0; i < g.vex_num; i++) {
        visited[i] = 0; //初始化
    }
    for (int i = 0; i < g.vex_num; i++) {
        if(!visited[i]){
            visited[i] = 1; // 标记访问
            printf("%2c",g.vexs[i].data); //打印该点数据
            queue[rear++] =i;//入队
        }
        while(head !=rear){ // 遍历进来的每一条边
            j = queue[head++]; //出队
            node = g.vexs[j].first_edge;
            while (node != NULL){
                k = node->ivex;
                if(!visited[k]){
                    visited[k]=1;
                    printf("%2c",g.vexs[k].data); //打印该点数据
                    queue[rear++]=k;
                }
                node = node->next_edge;
            }
        }

    }

}
int main() {
    pLGraph G;
//    G = create_example_lgraph();
//    print_lgraph(*G);
    G = create_example_lgraph_s();
//    print_lgraph(*G);

    DFSTraverse(*G);
    BFS(*G);
    return 0;
}

上次更新: 2022/08/23, 18:12:45

← 排序