PAT甲级 图的遍历 相关题_C++题解

图的遍历

目录

• 《算法笔记》重点摘要
• 1021 Deepest Root (25)
• 1076 Forwards on Weibo (30)

《算法笔记》 10.3 图的遍历 重点摘要

1. 定义

• 边 两端可以是 相同 的顶点
• 可以把 无向图 当作所有 边 都由 正向 和 负向 两条 有向边 组成
• 顶点的度：与该顶点相连的边的条数
• 顶点和边量化的属性分别成为点权和边权

2. 存储

2.1 邻接矩阵

• G[i][j] 存放边权，不存在的边设边权为0、-1 或 一个很大的数
• 邻接矩阵只适用于顶点数目不太大（一般不超过 1000）的题目

2.2 邻接表

• 若只存放每条边的终点编号，vector 元素类型定义为 int 即可

vector<int> Adj[N];

Adj[u].push_back(v);

• 若同时存放终点编号和边权，可建立结构体，vector 元素类型定义为结构体

struct Node{

    int v;

    int weight;

};

vector<Node> Adj[N];

Adj[u].push_back({v,weight});

3. DFS

若已知给定图为连通图，则只需一次 DFS 即可完成遍历

const int MAXV = 1000;

const INF = 1000000000;

3.1 邻接矩阵

int n, G[MAXV][MAXV];

bool vis[MAXV] = {false};

void DFS(int u, int depth){

    vis[u] = true;

    // 若需要对 u 进行一些操作，在这里进行

    for (int v = 0; v < n; v++)

        if (!vis[v] && G[u][v] != INF)

            DFS(v, depth + 1);

}

void DFSTrave(){

    for (int u = 0; u < n; u++)

        if (!vis[u])

            DFS(u, 1);

}

3.2 邻接表

vector<int> Adj[MAXV];

int n;

bool vis[MAXV] = {false};

void DFS(int u, int depth){

    vis[u] = true;

    // 若需要对 u 进行一些操作，在这里进行

    for(int i = 0; i < Adj[u].size(); i++){

        int v = Adj[u][i];

        if (!vis[v])

            DFS(v, depth + 1);

    }

}

void DFSTrave(){

    for (int u = 0; u < n; u++)

        if (!vis[u])

            DFS(u,1);

}

4. BFS

4.1 邻接矩阵

int n, G[MAXV][MAXV];

bool inq[MAXV] = {false};

void BFS(int u){

    queue<int> q;

    q.push(u);

    inq[u] = true;

    while (!q.empty()){

        int u = q.front();

        q.pop();

        for (int v = 0; v < n; v++){

            if (!inq[v] && G[u][v] != INF){

                q.push(v);

                inq[v] = true;

            }

        }

    }

}

void BFSTrave(){

    for (int u = 0; u < n; u++)

        if (!inq[u])

            BFS(u);

}

4.2 邻接表

vector<int> Adj[MAXN];

int n;

bool inq[MAXN] = {false};

void BFS(int u){

    queue<int> q;

    q.push(u);

    inq[u] = true;

    while (!q.empty()){

        int u = q.front();

        q.pop();

        for (int i = 0; i < Adj[u].size(); i++){

            int v = Adj[u][i];

            if (!inq[v]){

                q.push(v);

                inq[v] = true;

            }

        }

    }

}

void BFSTrave(){

    for (int u = 0; u < n; u++)

        if (!inq[u])

            BFS(u);

}

4.3 输出结点层号（邻接表）

struct Node{

    int v;

    int level;

};

vector<Node> Adj[N];

void BFS(int s){

    queue<Node> q;

    Node start = {s,0};

    q.push(start);

    inq[start.v] = true;

    while(!q.empty()){

        Node now = q.front();

        q.pop();

        int u = now.v;

        for (int i = 0; i < Adj[u].size(); i++){

            Node next  = Adj[u][i];

            next.level = now.level + 1;

            if (!inq[next.v]){

                q.push(next);

                inq[next.v] = true;

            }

        }

    }

}

1021 Deepest Root (25)

题目思路

• 边为双向，邻接表法注意两个方向都要存储
• 先按正常 DFS 遍历一遍，记录连通分量个数
• 若不为树（分量个数 > 1），直接按要求输出分量个数即可
• 若为树（分量个数 = 1），分别以每个结点为根结点进行 DFS，记录这样遍历树的深度，与最大深度比较
  • 相等则将此根压入根集合中
  • 若大于最大深度，说明找到了更大深度，将之前的根集合清空，压入新发现的根结点

#include<iostream>

#include<vector>

#include<set>

using namespace std;

set<int> roots;

vector<int> Adj[10001];

int n, components = 0, depth = 0, maxdepth = 0;

bool vis[10001] = {false};

void DFS(int root, int level){

	vis[root] = true;

	if (level > depth) depth = level;

	for (int i = 0; i < Adj[root].size(); i++)

		if (!vis[Adj[root][i]])

			DFS(Adj[root][i], level+1);

}

void DFSTrave(){

	for (int i = 1; i < n + 1; i++){

		if (!vis[i]){

			DFS(i, 0);

			components++;

		}

	}

	if (components == 1){

		for (int i = 1; i < n + 1; i++){

			fill(vis, vis+10001, false);

			depth = 0;

			DFS(i,0);

			if (depth == maxdepth) roots.insert(i);

			else if (depth > maxdepth){

				maxdepth = depth;

				roots.clear();

				roots.insert(i);

			}

		}

	}

}

int main()

{

	int u, v;

	scanf("%d", &n);

	for (int i = 1; i < n; i++){

		scanf("%d%d", &u, &v);

		Adj[u].push_back(v);

		Adj[v].push_back(u);

	}

	DFSTrave();

	if (components > 1) printf("Error: %d components\n", components);

	else for (auto it: roots) printf("%d\n",it);

	return 0;

}

1076 Forwards on Weibo (30)

题目思路：带层数的广度优先

• 用 Node 结构体同时保存 id 和 level
• 用 inq 记录结点是否入队过，入队过不能重复入队（重复转发消息）
• 记录结点层数，若超过要求的最高层数也不可再入队

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

struct Node{

	int id, level;

};

int maxlevel, numforward;

vector<Node> Adj[1001];

void BFS(int start){

	bool inq[1001] = {false};

	queue<Node> q;

	q.push({start,0});

	inq[start] = true;

	while (!q.empty()){

		Node now = q.front();

		q.pop();

		for (int i = 0; i < Adj[now.id].size(); i++){

			Node next = Adj[now.id][i];

			next.level = now.level + 1;

			if (!inq[next.id] && next.level <= maxlevel){

				inq[next.id] = true;

				q.push(next);

				numforward++;

			}

		}

	}

}

int main()

{

	int n, m, followed, k, query;

	scanf("%d%d", &n, &maxlevel);

	for (int i = 1; i < n + 1; i++){

		scanf("%d", &m);

		for (int j = 0; j < m; j++){

			scanf("%d", &followed);

			Adj[followed].push_back({i,0});

		}

	}

	scanf("%d", &k);

	for (int i = 0; i < k; i++){

		scanf("%d", &query);

		numforward = 0;

		BFS(query);

		printf("%d\n", numforward);

	}

	return 0;

}