首页 > 编程语言 > 详细

图 - 邻接矩阵深度优先遍历(C语言)

时间:2021-04-09 00:06:17      阅读:35      评论:0      收藏:0      [点我收藏+]
技术分享图片

#include <stdio.h>
/*
 * 邻接矩阵,深度优先遍历
 *
 */

#define MAX 100
#define INFINITY 65535

int visited[MAX]; // 标记遍历过的顶点下标

typedef struct {
    char vexs[MAX]; // 顶点的数组,顶点类型为了简单使用char
    int arc[MAX][MAX]; // 边表二维数组,对,行列的下标对应实际存在的顶点,值为1表示两顶点间有边
    int numVex, numEdg; // 顶点和边的数量,创建的时候用
}GRAPH, *PGRAPH;

void create(PGRAPH);
void traverse_dfs(GRAPH);
void dfs(GRAPH, int);

void dfs(GRAPH graph, int i)
{
    int j;

    // 先打印,并更新visited数组
    printf("%c ", graph.vexs[i]);
    visited[i] = 1;

    // 在顶点i的行中查找,一旦找到没有访问的顶点,则递归调用
    for (j=0; j<graph.numVex; j++) {
        if (graph.arc[i][j] == 1 && !visited[j] ) {
            dfs(graph, j);
        }
    } 
}

void traverse_dfs(GRAPH graph)
{
    int i;
    // 先初始化标记数组visited
    for (i=0; i<graph.numVex; i++) {
        visited[i] = 0;
    }

    // 开始遍历
    for (i=0; i<graph.numVex; i++) {
        if (!visited[i])
            dfs(graph, i);
    }
}

void create(PGRAPH g)
{
    int i, j, k, w;
    printf("请输入顶点及边的个数:\n"); // 这里输入边的个数也就只有在创建的时候用得着
    scanf("%d %d", &g->numVex, &g->numEdg);

    // 创建顶点
    printf("请一次性输入顶点的值:\n");
    getchar();
    for (i=0; i<g->numVex; i++) {
        scanf("%c", &g->vexs[i]);
    }

    // 初始化边表
    for (i=0; i<g->numVex; i++) {
        for (j=0; j<g->numVex; j++) {
            g->arc[i][j] = INFINITY;
        }
    }

    // 创建表
    for (k=0; k<g->numEdg; k++) {
        printf("请输入边的顶点下标和权:\n"); // 本例中并没有对权有操作
        scanf("%d %d %d", &i, &j, &w);
        g->arc[i][j] = g->arc[j][i] = w; 
    }   
}

int main(void)
{
    GRAPH graph;
    create(&graph);
    printf("深度优先遍历结果: ");
    traverse_dfs(graph);
    putchar(‘\n‘);

    return 0;
}

output

[root@8be225462e66 c]# gcc dfs_adMatrix.c && ./a.out
请输入顶点及边的个数:
8 9
请一次性输入顶点的值:
ABCDEFGH
请输入边的顶点下标和权:
0 1 1
请输入边的顶点下标和权:
1 2 1
请输入边的顶点下标和权:
2 5 1
请输入边的顶点下标和权:
1 4 1
请输入边的顶点下标和权:
0 4 1
请输入边的顶点下标和权:
0 3 1
请输入边的顶点下标和权:
3 6 1
请输入边的顶点下标和权:
6 4 1 #输入 4 6 1也可以,因为是对称矩阵
请输入边的顶点下标和权:
6 7 1
深度优先遍历结果: A B C F E G D H
[root@8be225462e66 c]

图 - 邻接矩阵深度优先遍历(C语言)

原文:https://blog.51cto.com/sndapk/2693061

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!