12.16~12.17图的存储方式(邻接矩阵,邻接表),相应定义与构建,PTA特性(要初始化),BFS抓牛,判断题

2023-12-18 06:02:54

图的存储方式

邻接矩阵

#include<iostream>
using namespace std;
#define maxn;
struct tu {
	int juzhen[maxn][maxn];//行为起点,列为终点,即第一个为起点,第二个为终点
	//确定一个点的出度,就固定行,即第一个不动(即起点固定不动),然后看这一行里有多少个不为0的数
	//确定一个点的入度,就固定列,即第二个不动(固定终点不动),然后看这一列里有多少个不为0的数
	int vn, an;//节点数量为vn,边的数量为an
};
int main() {
	tu a;//定义一个图a
	cin >> a.vn >> a.an;//输入图a的节点数量以及边的数量
	for (int i = 0; i < a.an; i++) {//循环次数为边的数量,每个边连接起两个点
		int v1, v2;
		cin >> v1 >> v2;
		juzhen[v1][v2] = 1;
		juzhen[v2][v1] = 1;//这是无向图,如果为有向图,那么就只有第一行
		//即只有从起点到终点,而没有终点到起点
	}
	return 0;
}

邻接表?

这个表就是图中的节点,可以看成是一个数组,不过数组里记录的元素是以这个节点为起点的边,然后串起来的链表

创建一个大小为n的数组,其中n是图的顶点数。数组的每个元素都是链表的头指针,用来存储每个顶点的邻接点。

定义

#define maxn 100;
struct arcnode {
	int target;
	arcnode* nextarc;
};
struct vnode {
	int data;
	arcnode* firstarc;
};
struct tu {
	vnode lb[100];
	int vnum, anum;
};

边存储边的权值,以及边所连接的下一条边,对于数组中的同一个格子,起点都是相同的

节点 存储节点信息,然后有一个指针指向第一条边,通过访问这条边就可以访问到以该节点为起点的所有边

图就是把边和节点串在一起,每个数组里的元素就是一个链表,存储的是链表的头指针,然后链表元素存储指向下一个链表节点的指针

需要注意图的链表数组定义中,最好直接表明,不然会报错

struct arcnode {
	int adj;
	arcnode* nextarc;
};
struct vnode {
	int data;
	arcnode* firstarc;
};
struct tu {
	int vnum, anum;
	vnode vs[20];
};

构建

void creat(tu& g) {
	int i, k, v1, v2;
	cin >> g.vnum >> g.anum;
	for (i = 0; i < g.vnum; i++) {
		cin >> g.lb[i].data;
		g.lb[i].firstarc = nullptr;
	}
	for (k = 0; k < g.anum; k++) {
		cin >> v1 >> v2;
		arcnode* p1 = new arcnode;
		p1->target = v2;
		p1->nextarc = g.lb[v1].firstarc;
		g.lb[v1].firstarc = p1;
		arcnode* p2 = new arcnode;
		p2->target = v1;
		p2->nextarc = g.lb[v2].firstarc;
		g.lb[v2].firstarc = p2;
	}
}

构建就是先输入图的总边数以及结点数,然后初始化链表数组

接着就是输入边,为无向图时,要一次更新两个数组位置;

为有向图时,只更新一个数组位置?

方式就是链表的插入

7-1 数据结构实验三 图的深度优先搜索

采用邻接矩阵

struct tu {
	int vnum, arcnum;
	int arcs[20][20];
};
void creat(tu& a) {
	cin >> a.vnum >> a.arcnum;
	for (int i = 0; i < a.vnum; i++) {
		for (int j = 0; j < a.vnum; j++) {
			a.arcs[i][j] = 0;
		}
	}
	for (int i = 0; i < a.arcnum; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		a.arcs[v1][v2] = a.arcs[v2][v1] = 1;
	}
}
void dfs(tu a, int v) {
	cout << v << " ";
	visited[v] = 1;
	for (int i = 0; i < a.vnum; i++) {
		if (a.arcs[v][i] == 1) {
			if (visited[i] == 0) {
				dfs(a, i);
			}
		}
	}
}

PTA特性,一定需要初始化

不然的话二维数组开大了一定会保存奇怪的值导致得到错误的结果

就会导致在编译器上运行是正确的,但是在PTA上运行是错误的

7-2 抓住那头牛

农夫知道一头牛的位置,想要抓住它。农夫和牛都位于数轴上,农夫起始位于点N(0<=N<=100000),牛位于点K(0<=K<=100000)。农夫有两种移动方式:

1、从X移动到X-1或X+1,每次移动花费一分钟
2、从X移动到2*X,每次移动花费一分钟

假设牛没有意识到农夫的行动,站在原地不动。农夫最少要花多少时间才能抓住牛?

关键词:bfs,队列元素为数对

#include<iostream>
#include<queue>
using namespace std;
int n, k;
const int N = 1e5 + 5;
int arr[N];
bool visited[N];
int capture(int n, int k) {
    queue<pair<int, int>>q;
    q.push(make_pair(n, 0));
    visited[n] = 1;
    while (!q.empty()) {
        int cur = q.front().first;
        int t = q.front().second;
        q.pop();
        if (cur == k) {
            return t;
        }
        int nextpos[3] = { cur - 1,cur + 1,cur * 2 };
        for (int i = 0; i < 3; i++) {
            if (nextpos[i] >= 0 && nextpos[i] <= N && !visited[nextpos[i]]) {
                q.push(make_pair(nextpos[i], t + 1));
                visited[nextpos[i]] = 1;
            }
        }
    }
    return -1;
}
int main() {
    cin >> n >> k;
    cout << capture(n, k);
    return 0;
}

判断题

For a sequentially stored linear list of length N, the time complexities for query and insertion are O(1) and O(N), respectively. 对于长度为N的顺序存储线性列表,查询和插入的时间复杂度分别为O(1)和O(N)。 T
The sum of the degrees of all the vertices in a connected graph must be an even number. 连通图中所有顶点的度数之和必须是偶数。 T

If a graph is represented by an adjacency matrix, then the space taken depends only on the number of vertices, not the number of edges. 如果一个图是用邻接矩阵表示的,那么所占用的空间只取决于顶点的数量,而不是边的数量。 T

In a directed graph, the sum of the in-degrees and out-degrees of all the vertices is twice the total number of edges. 在有向图中,所有顶点的入度和出度之和是总边数的两倍。 T

In a directed graph, the sum of the in-degrees must be equal to the sum of the out-degrees of all the vertices. 在有向图中,入度之和必须等于所有顶点出度之和。 T

?The best “worst-case time complexity” for any algorithm that sorts by comparisons only must be O(NlogN). 对于任何只通过比较排序的算法来说,最好的“最坏情况时间复杂度”必须是O(NlogN)。 T

To sort N records by simple selection sort, the numbers of comparisons and record movements are O(N^2) and O(N), respectively. 对N个记录进行简单选择排序,比较次数和记录移动次数分别为O(N2)和O(N)。T

?

?An AVL tree that all the balance factors of non-leaf nodes are 0 must be a perfect binary tree. 所有非叶节点的平衡因子均为0的AVL树必定是一棵完美二叉树。T

?

归并排序是稳定的

?就是树高,树高为LOGN

For a graph, if each vertex has an even degree, we can find an Euler circuit that visits every vertex exactly once. 对于一个图,如果每个顶点都是偶数度,我们可以找到一个欧拉回路,它恰好访问每个顶点一次。 F
对于一个连通的图,如果每个顶点的度数都是偶数,那么该图一定存在一个欧拉回路(Euler circuit)。欧拉回路是一条经过图中每条边一次且仅一次的回路,它可以从任意顶点开始并回到该顶点。

注意欧拉回路是1.每个顶点的度数都是偶数2.经过每个边一次,而不是每个顶点一次

If a linear list is represented by a 1-dimensional array, the addresses of the elements in the memory must be consecutive. 如果线性列表用一维数组表示,那么内存中元素的地址必须是连续的。T

It is always possible to represent a tree by a one-dimensional integer array. 总是可以用一维整数数组来表示树。 T
The number of leaf nodes in a binary tree is only related to the number of 2-degree nodes , i.e it has nothing to do with the number of 1-degree nodes. 二叉树的叶节点数只与2度节点数相关,与1度节点数无关。 T

In a binary tree, if node A is a descendant of node B, A may precede B in the inorder traversal sequence. 在一棵二叉树中,如果节点a是节点B的后代,则在中序遍历序列中,a可以在B之前。 T

There must be a collision if we insert a new element into a hash table with the loading density being 1. 如果我们在加载密度为1的哈希表中插入一个新元素,就一定会发生碰撞。 T

如果有向图为强连通或弱连通,都至少需要V-1条边,弱连通就是类似于树状;强连通就是连成一个闭合的圆圈?

For the extra space taken by an internal sorting algorithm, we have: heap sort < quick sort < merge sort. 对于内部排序算法占用的额外空间,我们有:堆排序<快速排序<归并排序。 T

NlogN^2 and NlogN^3 have the same speed of growth. T

To sort N records by quick sort, the worst-case time complexity is Ω(NlogN). 对N条记录进行快速排序,最坏情况下时间复杂度为Ω(NlogN)。 T

文章来源:https://blog.csdn.net/m0_73553411/article/details/135038246
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。