图(Graph)的常用代码集合

图的相关概念请查阅离散数学图这一章或者数据结构中对图的介绍。代码来自课本。

/*Graph存储结构*/
//邻接矩阵表示法
#define MAX_VERTEX_NUM 20    /*最多顶点个数*/
#define INFINITY 32768       /*表示极大值,即∞*/

/*图的种类:DG表示有向图,DN表示有向网,DUG表示无向图,UDN表示无向网*/
typedef enum {DG, DN, UDG, UDN} GraphKind;  /*枚举类型*/
typedef char VertexData     /*假设顶点数据为字符型*/
typedef struct ArcNode {
    AdjType adj;            /*对于无权图,用1或0表示是否相邻;对带权图,则为权值类型*/
    OtherInfo info;
} ArcNode;
typedef struct {
    VertexData vertex[MAX_VERTEX_NUM];    /*顶点向量*/
    ArcNode arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];    /*邻接矩阵*/
    int vexnum,arcnum;
    GraphKind kind;
} AdjMartrix;     /*(AdjMartrix Matrix Graph)*/
/*采用邻接矩阵表示法创建有向图*/
int LocateVertex(AdjMartrix *G, VertexData v) {     /*定位顶点位置函数*/
    int j = ERROR, k;
    for(k = 0; k < G->vexnum; k++) {
        if(G->vertex[k] == v) {
            j = k; break;
        }
    }
    return j;
}

int CreateDN(AdjMartrix *G) {
    int i,j,k,weight; VertexData v1,v2;
    scanf("%d,%d", &G->arcnum; &G->vexnum);     /*输入图的顶点数和弧数*/
    for(i = 0; i < G->vexnum; i++) {            /*初始化邻接矩阵*/
        for(j = 0; j < G->vexnum; j++) {
            G->arcs[i][j].adj = INFINITY;
        }
    }
    for(i = 0; i < G->vertex; i++) {      /*输入图的顶点*/
        scanf("%c", &G->vertex)[i];
    }
    for(k = 0; k < G->arcnum; k++) {      /*输入一条弧的两个顶点和权值*/
        scanf("%c,%c,%d", &v1,&v2,&weight);
        i = LocateVertex_M(G, v1);
        j = LocateVertex_M(G, v2);
        G->arcs[i][j].adj = weight;      /*建立弧*/
    }
    return OK;
}
//邻接表表示法
#define MAX_VERTEX_NUM 20
typedef enum {DG, DN, UDG, UDN} GraphKind;
typedef struct ArcNode {
    int adjvex;                   /*该弧指向顶点的位置*/
    struct ArcNode *nextarc;      /*指向下一条弧的指针*/
    OtherInfo;
} ArcNode;
typedef struct VerNode {
    VertexData data;
    ArcNode *firstarc;
} VerNode;
typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM];
    int vexnum,arcnum;
    GraphKind kind;
} AdjList;     /*Adjacency List Graph*/
//十字链表
#define MAX_VERTEX_NUM 20
typedef enum {DG, NG, UDG, UDN} GraphKind;
typedef struct ArcNode {
    int tailvex,headvex;
    struct ArcNode *hlink, *tlink;
} ArcNode;
typedef struct VertexNode {
    VertexData data;
    ArcNode *firstin, *firstout;
} VertexNode;
typedef struct {
    VertexNode vertex[MAX_VERTEX_NUM];
    int vexnum,arcnum;     //图的顶点数和弧数
    GraphKind kind;
} OrthList;
/*创建图的十字链表*/
void CrtOrthList(OrthList *g) {
/*从终端输入n个顶点的信息和e条弧的信息,以建立一个有向图的十字链表*/
    scanf("%d,%d", &n,&e);    /*从键盘输入图的顶点个数和弧的个数*/
    g->vertex = n;
    g->vertex = e;
    for(i = 0; i < n; i++) {     /*初始化顶点结点*/
        scanf("%c", &(g->vertex[i].data));
        g->vertex[i].firstin = NULL;
        g->vertex[i].firstout = NULL;
    }
    for(k = 0; k < e; k++) {     /*创建弧结点,建立弧结点个顶点的连接*/
        scanf("%c,%c", &vt,&vh);
        i = LocateVertex(g, vt);
        j = LocateVertex(g, vh);
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->tailvex = i; p->headvex = j;
        p->tlink = g->vertex[i].firstout;
        g->vertex[i].firstout = p;
        p->hlink = g->vertex[j];
        g->vertex[j].firstin = p;
    }
}    /*CrtOrthList*/
/*邻接多重表*/
#define MAX_VERTEX_NUM 20
typedef struct EdgeNode {
    int mark,ivex,jvex;
    struct EdgeNode *ilink, *jlink;
} EdgeNode;
typedef struct {
    VertexData data;
    EdgeNode *firstedge;
} VertexNode;
typedef struct {
    VertexNode vertexp[MAX_VERTEX_NUM];
    int vernum,arcnum;
    GraphKind kind;
} AdjMultiList;

/*图的深度遍历算法*/
#define True  1
#define False 0
#define Error -1
#define OK    1
int visited[MAX_VERTEX_NUM];     /*初始化标准数组*/

void TraverseGraph(Graph g) {
/*在图g中寻找未访问的顶点作为起始点,并调用深度优先搜索过程进行遍历。Graph表示图的
一种存储结构,如邻接矩阵或者邻接表等*/
    for(vi = 0; vi < g.vexnum; vi++) Visited[vi] = False;    /*访问标志数组*/
    for(vi = 0; vi < g.vexnum; vi++) {    //循环调用深度优先遍历连通子图,若g是连通图,则此
        if(!visted[vi]) DepthFirstSearch(g,vi);    //仅调用一次
    }                                     
} /*TraverseGraph*/
/*深度优先遍历v0所在的连通子图*/
void DepthFirstSearch(Graph g, int v0) {
    visit(v0); visit[v0] = True;     /*访问顶点v0,修改访问变量*/

    w = FirstAdjVertex(g, v0);
    while(w != -1) {
        if(!visited[w]) DepthFirstSearch(g, w);    /*递归调用DepthFirstSearch*/
        w = NextAdjVertex(g, v0, w);     /*找下一个邻接点*/ 
    }
}     /*DepthFirstSearch*/
/*采用邻接矩阵的DepthFirstSearch*/
void DepthFirstSearch(AdjMartrix g, int v0) {
    visit(v0); visited[vo] = True;
    for(vj = 0; vj < g.vexnum; vj++) {
        if(!visited[vj] && g.arcs[v0][vj].adj  == 1) {    //未访问过且路径存在
            DepthFirstSearch(g, vj);
        }
    }
}     /*DepthFirstSearch*/
/*采用邻接表的DepthFiirstSearch*/
void DepthFirstSearch(AdjList g, int v0) {
    visit(v0); visited[v0] = True;
    p = g.vertex[v0].firstarc;
    while(p != NULL) {
        if(!visited[p->adjvex]) DepthFirstSearch(g, p->adjvex);
        p = p->nextarc;
    }
}     /*DepthFirstSearch*/
/*非递归形式的DepthFirstSearch*/
void DepthFirstSearch(Graph g, int v0) {
/*从v0出发深度优化搜索图g*/
    InitStack(&s);
    Push(&S, v0);
    while(!is Empty(S)) {
        Pop(&S, &v);
        if(!visited[v]) {
            visit(v);
            visited[v] = True;
            w = FirstAdjVertex(g, v);
            while(w != -1) {
                if(!visted[w]) {
                    Push(&S, w);
                }
                w = NextAdjVertex(g, v, w);     /*求v相对于w的下一个邻接点*/
            }
        }
    }
}
/*广度优先搜索图g中v0所在的连通子图*/
void BreadthFirstSearch(Graph g, int v0) {
    visit(v0); visited[v0] = True;
    InitQueue(&Q);
    EnterQueue(&Q, v0);
    while(Empty(&Q, v0)) {
        DeleteQueue(&Q, &v);
        w = FirstAdjVertex(g, v);
        while(w != -1) {
            if(!visited[w]) {
                visit(w); visited[w] = True;
                EnterQueue(&Q, w);
            }
            w = NextAdjVertex(g, v, w);
        }
    }
}
/*图的应用*/
/*深度优先找出从顶点u到v的简单路径*/
int *pre;
void one_path(Graph *G, int u, int v) {
    int i;
    pre = (int *)malloc(G->vexnum * sizeof(int));
    for(i = 0; i < G->vexnum; i++) {     /*初始化,置-1*/
        pre[i] = -1;
    }
    pre[u] = -2;           /*将pre[u]置-2,表示已访问过,且没有前驱*/
    DFS_path(G, u, v);     /*用深度优先算法找出一条从u到v的简单路径*/
    free(pre);
}
int DFS_path(Graph *G, int u, int v) {
    int j;
    for(j = firstadj(G, u)); j >= 0; j = nextadj(G, u, j)) {
        if(pre[j] == -1) {     //不等于-1则参数有误
            pre[j] = u;
            if(j == v) {
                print_path(pre, v);   //从v0开始,沿着pre[]中保留的前驱指针输出路径(直到-2)
            }
            else if(DFS_path(G, j, v)); return 1;
        }
    }
    return 0;
}
/*求图的最小生成树*/
/*prim算法(加点法)*/
struct {
    int adjvex;
    int lowcost;
} closedge[MAX_VERTEX_NUM];    /*求最小生成树时的辅助数组*/

MiniSpanTree_Prim(AdjMartrix gn, int u) {
/*从顶点u出发,按prim算法构造连通网gn的最小生成树,并输出生成时的每条边*/
    closedge[u].lowcost = 0;     /*初始化*, U = {u}*/
    for(i = 0; i < gn.vexnum; i++) {
        if(i != u) {             /*对V-U的顶点i,初始化closedge[i]*/
            closedge[i].adjvex = u;
            closedge[i].lowcost = gn.arcs[u][i].adj;    
        }
    }
    for(e = 1; e < gn.vexnum - 1; e++) {    /*找n-1条边*/
        v = Mimium(closedge);     /*closedge中存有当前最小边(u,v)的信息*/
        printf(u, v);     /*输出生成树的当前最小边(u,v)*/
        closedge[v].lowcost = 0;     /*将顶点v纳入U集合*/
        for(i = 0; i < gn.vexnum; i++) {     /*顶点v纳入U集合后,更新closedge[i]*/
            if(gn.arcs[v][i].adj < closedge[i].lowcost) {
                closedge[i].lowcost = gn.arcs[v][i].adj;
                closedge[i].adj = v;
            }
        }
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

数据结构——图相关概念

可是现实生活中,好多关系不再是一对一或一对多,比如人和人之间的关系,会互相认识,就要考虑多对多的情况。这就是今天要介绍的——图。

11220
来自专栏云霄雨霁

加权无向图----加权无向图的实现

19600
来自专栏zaking's

用js来实现那些数据结构15(图01)

20240
来自专栏mathor

搜索(1)

 在讨论图的遍历问题之前,我们先来讨论一下图的存储问题,也就是我们在写程序的时候如何保存、表示一个图。首先我们会用连续的整数编号来表示点集。比如1号顶点、2号顶...

13810
来自专栏向治洪

数据结构之图

基本概念 图(Graph):图(Graph)是一种比线性表和树更为复杂的数据结构。 图结构:是研究数据元素之间的多对多的关系。在这种结构中,任意两个元素之间...

22450
来自专栏架构之路

Kosaraju算法、Tarjan算法分析及证明--强连通分量的线性算法

一、背景介绍 强连通分量是有向图中的一个子图,在该子图中,所有的节点都可以沿着某条路径访问其他节点。强连通性是一种非常重要的等价抽象,因为它满足 自反性:顶点V...

40960
来自专栏nnngu

数据结构10 图

这一篇我们要总结的是图(Graph),图可能比我们之前学习的线性结构和树形结构都要复杂,不过没关系,我们一点一点地来总结。那么关于图,我将从以下几点进行总结: ...

36170
来自专栏算法与数据结构

数据结构 图

1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

43870
来自专栏编程理解

数据结构(八):邻接表与邻接矩阵

邻接表和邻接矩阵是图的两种常用存储表示方式,用于记录图中任意两个顶点之间的连通关系,包括权值。

24130
来自专栏calmound

HDU 3652 B-number(数位DP)

http://acm.hdu.edu.cn/showproblem.php?pid=3652 题意:类似3555,0-n之间某个数中包含13,且整个数能被13...

36360

扫码关注云+社区

领取腾讯云代金券