【数据结构 | C语言】求图（邻接表）两个顶点之间的简单路径算法 C语言实现

2022-01-07 09:16:10

文章目录

算法
文字说明
完整代码

算法

void SamplePath(pGraph graph, ElemType vexa, ElemType vexb) {
	// path是结构体类型，存放图的顶点，和存储数量。就是个栈
    Path *path = (Path *) malloc(sizeof(Path));
    memset(path, 0, sizeof(Path));
    // 标志数组
    bool searched[MAX_SIZE];
    bool found=false;
    int i;
    for (i=0; i<MAX_SIZE; i++)
        searched[i] = false;
    // 先找到 a
    for (i=0; i<graph->vexnum; i++)
        if (graph->vertices[i].data==vexa)
            break;
    // 调用 SampleP 生成路径
    SampleP(graph, i, vexb, path, searched, 0, &found);
	
	// 如果遍历完图，没有找到路径，说明两顶点不连通
	if (path->path[path->final-1].data!=vexb) {
        printf("%c与%c不连通\n", vexa, vexb);
        return ;
    }
    
    for (int i=0; i<path->final; i++)
        printf("%c\t", path->path[i].data);
    printf("\n");
}

// 参数： v，搜索的结点索引， vexb 是目标结点， path 存放路径， found 如果找到了就为 true，否则一直为 false
void SampleP(pGraph graph, int v, ElemType vexb, Path *path, bool *searched, bool *found) {
    searched[v] = true;
    // 把当前结点添加进 路径 中
    Add(path, graph->vertices[v]);
    // 循环遍历结点的邻接点
    for (ArcNode *arc=graph->vertices[v].firstArc; arc!=NULL && *found==false; arc=arc->nextArc) {
    	// 如果找到了，把 目标顶点添加进 路径中
        if (graph->vertices[arc->adj].data==vexb) {
            *found = true;
            Add(path, graph->vertices[arc->adj]);
        }
        // 如果没遍历过该结点，递归遍历
        else if (searched[arc->adj]==false)
            SampleP(graph, arc->adj, vexb, path, searched, found);
    }
    // 没找到，把当前结点退出栈
    if (*found==false)
        Delete(path);
}

文字说明

搜索路径，利用栈

把遍历的结点入栈，并遍历该结点的邻接点。
若邻接点未被访问过，递归搜索邻接点
如果所有的邻接点遍历完，都没有目标结点，那么当前结点出栈。退回上一个顶点
重复步骤 1-3 。
当找到结点时， found 相当于全局变量，告诉递归函数，已经找到

完整代码

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

# define MAX_SIZE 20
# define true 1
# define false 0

typedef char ElemType;
typedef int bool;

typedef enum {
    DG, DN, UDG, UDN
} GraphKind;

typedef struct ArcNode {
    int adj;    // 指向弧头
    struct ArcNode *nextArc;   // 指向的下一个弧头
    ElemType *info;     // 弧尾信息
} ArcNode;

typedef struct {
    ElemType data;  // 数据域
    ArcNode *firstArc;  // 第一个弧头
} VNode, AdjList[MAX_SIZE];

typedef struct {
    VNode path[MAX_SIZE];
    int final;
} Path;

typedef struct {
    AdjList vertices;   // 数据域
    int vexnum, arcnum;     // 顶点数，弧数
    GraphKind kind;     // 图类型
} Graph, *pGraph;

// 路径
void Add(Path *path, VNode c);
void Delete(Path *path);
// 图
pGraph CreateGraph(GraphKind kind);
void AddVex(pGraph graph, ElemType vex);
void AddArc(pGraph graph, ElemType vexa, ElemType vexb);
// 求两个顶点之间的简单路径
void SamplePath(pGraph graph, ElemType vexa, ElemType vexb);
void SampleP(pGraph graph, int v, ElemType vexb, Path *path, bool *searched, bool *found);

int main() {
    pGraph graph = CreateGraph(DG);
    // 添加结点
    AddVex(graph, 'a');
    AddVex(graph, 'b');
    AddVex(graph, 'c');
    AddVex(graph, 'd');
    AddVex(graph, 'e');
    AddVex(graph, 'f');
    AddVex(graph, 'g');
    AddVex(graph, 'h');
    AddVex(graph, 'k');
    // 添加弧
    AddArc(graph, 'a', 'b');
    AddArc(graph, 'c', 'a');
    AddArc(graph, 'b', 'd');
    AddArc(graph, 'b', 'e');
    AddArc(graph, 'd', 'h');
    AddArc(graph, 'e', 'h');
    AddArc(graph, 'c', 'f');
    AddArc(graph, 'c', 'g');
    AddArc(graph, 'f', 'g');
    /*
    // 广度优先遍历
    WidFirstSearch(graph, 'a');
    // 深度优先遍历
    DeepFirstSearch(graph, 'a');
    */
    
    /*
    // 创建图
    pGraph graph = CreateGraph(UDN);
    // 添加顶点
    AddVex(graph, 'a');
    AddVex(graph, 'b');
    AddVex(graph, 'c');
    AddVex(graph, 'd');
    AddVex(graph, 'e');
    AddVex(graph, 'f');
    AddVex(graph, 'g');
    // 添加边
    AddArc(graph, 'a', 'b');
    AddArc(graph, 'a', 'c');
    AddArc(graph, 'a', 'd');
    AddArc(graph, 'a', 'e');
    AddArc(graph, 'a', 'f');
    AddArc(graph, 'a', 'g');
    AddArc(graph, 'b', 'c');
    AddArc(graph, 'd', 'e');
    AddArc(graph, 'f', 'g');
    */

    // 找路径
    SamplePath(graph, 'a', 'k');
    SamplePath(graph, 'a', 'e');

    return 0;
}

pGraph CreateGraph(GraphKind kind) {
    pGraph new = (pGraph) malloc(sizeof(Graph));
    memset(new, 0, sizeof(Graph));
    new->kind = kind;
    return new;
}

void AddVex(pGraph graph, ElemType vex) {
    graph->vertices[graph->vexnum++].data = vex;
}

void AddArc(pGraph graph, ElemType vexa, ElemType vexb) {
    // 找到元素索引
    int index_a, index_b;
    for (int i=0; i<graph->vexnum; i++) {
        if (graph->vertices[i].data==vexa)
            index_a = i;
        if (graph->vertices[i].data==vexb)
            index_b = i;
    }
    // 创建弧结点
    ArcNode *node = (ArcNode *) malloc(sizeof(ArcNode));
    memset(node, 0, sizeof(ArcNode));
    node->adj = index_b;
    // 添加弧结点
    if (graph->vertices[index_a].firstArc==NULL)
        graph->vertices[index_a].firstArc = node;
    else {
        ArcNode *final = graph->vertices[index_a].firstArc;
        while (final->nextArc!=NULL)
            final = final->nextArc;
        final->nextArc = node;
    }
    // 弧的另一个结点
    node = (ArcNode *) malloc(sizeof(ArcNode));
    memset(node, 0, sizeof(ArcNode));
    node->adj = index_a;
    // 添加弧结点
    if (graph->vertices[index_b].firstArc==NULL)
        graph->vertices[index_b].firstArc = node;
    else {
        ArcNode *final = graph->vertices[index_b].firstArc;
        while (final->nextArc!=NULL)
            final = final->nextArc;
        final->nextArc = node;
    }
    graph->arcnum++;
}

void SamplePath(pGraph graph, ElemType vexa, ElemType vexb) {
    Path *path = (Path *) malloc(sizeof(Path));
    memset(path, 0, sizeof(Path));
    // 标志数组
    bool searched[MAX_SIZE];
    bool found=false;
    int i;
    for (i=0; i<MAX_SIZE; i++)
        searched[i] = false;
    // 先找到 a
    for (i=0; i<graph->vexnum; i++)
        if (graph->vertices[i].data==vexa)
            break;
    SampleP(graph, i, vexb, path, searched, &found);

    if (path->path[path->final-1].data!=vexb) {
        printf("%c与%c不连通\n", vexa, vexb);
        return ;
    }

    for (int i=0; i<path->final; i++)
        printf("%c\t", path->path[i].data);
    printf("\n");
}

void SampleP(pGraph graph, int v, ElemType vexb, Path *path, bool *searched, bool *found) {
    searched[v] = true;
    Add(path, graph->vertices[v]);
    for (ArcNode *arc=graph->vertices[v].firstArc; arc!=NULL && *found==false; arc=arc->nextArc) {
        if (graph->vertices[arc->adj].data==vexb) {
            *found = true;
            Add(path, graph->vertices[arc->adj]);
        }
        else if (searched[arc->adj]==false)
            SampleP(graph, arc->adj, vexb, path, searched, found);
    }
    if (*found==false)
        Delete(path);
}

void Add(Path *path, VNode c) {
    path->path[path->final++] = c;
}

void Delete(Path *path) {
    path->final--;
}

码农公寓

文章目录

算法

文字说明

完整代码

相关文章