Mki's Blog

数据结构(八):图和图的遍历

题目描述

题目要求

06-图1 列出连通集 (25 分) 给定一个有N个顶点和E条边的无向图,请用DFS和BFS分别列出其所有的连通集。假设顶点从0到N−1编号。进行搜索时,假设我们总是从编号最小的顶点出发,按编号递增的顺序访问邻接点。

输入格式:

输入第1行给出2个整数N(0<N≤10)和E,分别是图的顶点数和边数。随后E行,每行给出一条边的两个端点。每行中的数字之间用1空格分隔。

输出格式:

按照"{ v1 v2... vk}"的格式,每行输出一个连通集。先输出DFS的结果,再输出BFS的结果。

输入样例:

8 6 0 7 0 1 2 0 4 1 2 4 3 5

输出样例:

{ 0 1 4 2 7 } { 3 5 } { 6 } { 0 1 2 7 4 } { 3 5 }

基础知识

呵,我可是在院长手下飘过的离散数学,你以为我会怕你吗。

关于图的基本概念

  • 图(Graph),用来表示多对多的关系。
  • 顶点(Vertex) 边(Edge)
  • 无向边用圆括号(v,m),有向边用尖括号
  • 数据结构里面的图一般不考虑平行边(重边)和回路(自旋)-->此处吐槽杭电的那本离散教材,严重与主流脱节,尤其是命名和定义这方面。
  • 生气了,剩下的概念自行百度。

图的表示

在程序里面表示一个图有好多办法,最主要的是邻接矩阵邻接表

邻接矩阵就是用一个n*n的数组来表示每两个点的关系,优点是简单易懂好操作,但是在遇上洗漱图(就是没用的顶点很多,但是边却少的一批)的情况下,会浪费空间。

邻接表就是用指针数组来表示,每个指针对应每行的一个链表,优点是方便计算度,缺点是不见得一定比邻接矩阵更省地方,有向图计算出入度也不简单,关键是我对指针还一窍不通......

图的遍历

初始化并输入关系后,一张图就搞好了,自然而然我们需要对它进行各种操作,遍历便是很常见的一种。一般来说遍历有两种方法。

懒得画图了。

深度优先遍历

一句话概括,深度优先就是:一条道走到黑,直到撞墙返回后一步接着找路。更像是线性搜索。

void DFS(int v) {
    Visited[v] = 1;
    //;
    for (int i = 0; i < Nv; i++) {
        if (!Visited[i] && G[v][i]) {
            printf("%d ", i);
            DFS(i);
        }
    }
}

广度优先遍历

广度优先遍历就是小孩子才做选择,我全都要,把有关的点全部丢到队列里,再把这些点有关的依次丢进去,呈辐射状搜索。

void BFS(int v) {
    int quene[Size];
    int head = -1, rear = -1;
    quene[++rear] = v;
    Visited[v] = 1;

    while (head < rear) {   //直到队列空了
        int out = quene[++head];
        printf("%d ", out);
        for (int i = 0; i < Nv; i++) {
            if (!Visited[i] && G[out][i]) {
                Visited[i] = 1;
                quene[++rear] = i;
            }
        }
    }
}

代码

#include<stdio.h>
#include<stdlib.h>
#define MaxVertexNum 10
#define Size 100
int Visited[MaxVertexNum];
int Nv, Ne, G[MaxVertexNum][MaxVertexNum];

/*初始化链接图*/
void Init_Vertex(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            G[i][j] = 0;
        }
    }
}
void Init_Visited(void) {
    for (int i = 0; i < MaxVertexNum; i++) {
        Visited[i] = 0;
    }
}

/*输入链接图*/
void Set(int E) {
    int n1, n2;
    for (int i = 0; i < E; i++) {
        scanf_s("%d %d", &n1, &n2);
        G[n1][n2] = 1;
        G[n2][n1] = 1;
    }
}


/*深度优先搜索*/
void DFS(int v) {
    Visited[v] = 1;
    //;
    for (int i = 0; i < Nv; i++) {
        if (!Visited[i] && G[v][i]) {
            printf("%d ", i);
            DFS(i);
        }
    }
}
/*广度优先搜索*/
void BFS(int v) {
    int quene[Size];
    int head = -1, rear = -1;
    quene[++rear] = v;
    Visited[v] = 1;

    while (head < rear) {   //直到队列空了
        int out = quene[++head];
        printf("%d ", out);
        for (int i = 0; i < Nv; i++) {
            if (!Visited[i] && G[out][i]) {
                Visited[i] = 1;
                quene[++rear] = i;
            }
        }
    }
}

void Loop(int N,int choice) {
    for (int i = 0; i < N; i++) {
        if (!Visited[i]) {
            printf("{ ");
            if (choice == 1) {
                printf("%d ", i);
                DFS(i);
            }
            else
                BFS(i);
            printf("}\n");
        }
    }
}

int main(void) {
    int N, E;
    scanf_s("%d %d", &Nv,&Ne);
    Init_Vertex(Nv);
    Set(Ne);
    Loop(Nv, 1);
    Init_Visited();
    Loop(Nv, 2);
    system("pause");
    return 0;
}

在写最后

这两天刷魔禁...炮姐真的敲可奈啊!超喜欢这种类型! (没错,两天没更博客就是去看炮姐去了哈哈哈哈 然后突然发现国庆假期马上就要没了。。。 ああ 不幸だ!!!