第六章学习小结

骑猪看日落 2021-12-13 20:29 304阅读 0赞

**题目：**

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

### 输入格式: ###

输入第1行给出2个整数N(0)和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 }
    { 6 }
    
    
    心得体会： 这道题的解题思路还是比较清晰的 即对于两个遍历的运用 解决这道题的思路是： ①建立起一个图并且填充 ②完成DFS遍历 ③完成BFS遍历 ① 根据题意可以选择以邻接矩阵的数据结构来建立图 首先是根据题意定义一个图的结构体

struct graph
    {
         
        int arcs[mvnum][mvnum];//邻接矩阵
        int vexnum, arcnum;//顶点数 边数
    };

然后是图的填充

void creategraph(graph &g)
    {
        cin >> g.vexnum >> g.arcnum;//输入顶点与边数
        int a, b;//端点编号
        for (int i = 0; i < g.arcnum; ++i)
        {
            cin >> a >> b;//输入相连的端点编号
            g.arcs[a][b] = g.arcs[b][a] = 1;//在邻接矩阵中将两端点状态赋值为相连
        }
    }

②

DFS遍历

首先是定义一个访问数组

bool visited[mvnum];//访问数组

然后为完成遍历连通图部分

void dfs(graph g, int v)
    {
        cout << " "<<v; //输出当前访问端点编号
        visited[v] = true; //将其作为访问数组下标，赋值其状态为已访问
        for (int i = 0; i < g.vexnum; ++i)
        {
            {
                if (!visited[i] && g.arcs[v][i] == 1)//若该端点编号i未被访问过，且其与当前所访问端点v相连
                {
                    dfs(g,i);//利用递归，访问端点i（下一层）
                }
            }
        }
    }

最后为完成非连通图部分

void dfss(graph g)
    {
        for (int j = 0; j < g.vexnum; ++j)
        {
            if (!visited[j])//若有端点未被访问
            {
                cout << "{
         ";
                dfs(g, j);
                cout << " }"<<endl;
            }
        }
    }

③

BFS遍历

首先还是定义一个访问数组

bool visit[mvnum];

然后为完成遍历连通图部分

void bfs(graph g,int v)
    {
        int x;//队头元素
        cout << " " << v; //输出当前访问端点编号
        visit[v] = 1; //将其作为访问数组下标，赋值其状态为已访问
        queue<int> q; //存放端点编号队列
        q.push(v);//v入队
        while(!q.empty()) //当队列为空时结束循环
        {
            x = q.front();//取队头元素
            q.pop();//队头元素出队
            for (int i = 0; i < g.vexnum; ++i)
            {
                if (!visit[i] && g.arcs[x][i] == 1)//若该端点编号i未被访问过，且其与当前所访问端点x相连
                {
                    cout << " "<<i;
                    visit[i] = 1; //将其作为访问数组下标，赋值其状态为已访问
                    q.push(i); //将其压入队列
    
                }
            }
    
        }
    }

最后最后为完成非连通图部分

void bfss(graph g)
    {
        for (int i = 0; i < g.vexnum; ++i)
        {
            
            if (!visit[i])//若有端点未被访问
            {
                cout << "{
         ";
                bfs(g, i);
                cout << " }" << endl;
            }
        }
    }

需要注意的地方：

弄清循环条件，究竟是图的边数还是顶点数

目标完成情况：
    
    与之前相比，找出入手点能力有所提高

目标：

提高对“图”方面知识的认识与理解，并能运用

转载于:https://www.cnblogs.com/Berlins/p/10891387.html