如何使用BFS或DFS算法设计算法以确定非连通图的连通分量,该算法必须能够表示每个连通分量的顶点集.
这是我的方法:
1)将所有顶点初始化为未访问.
2)从任意顶点开始对图进行DFS遍历v.如果DFS遍历不访问所有顶点,则返回false.
3)反转所有弧(或找到图的转置或反转)
4)在反转图中将所有顶点标记为未访问.
5)从相同的顶点v开始执行反向图的DFS遍历(与步骤2相同).如果DFS遍历不访问所有顶点,则返回false.否则返回true.
这个想法是,如果每个节点都可以从顶点v到达,并且每个节点都可以到达v,那么图形就是强连接的.在步骤2中,我们检查是否可以从v到达所有顶点.在步骤4中,我们检查所有顶点是否都可以到达v(在反向图中,如果所有顶点都可以从v到达,那么所有顶点都可以到达原始图中的v).
知道如何改进这个解决方案吗？
如何设计一种算法,在线性时间内计算(图理论)无向,全边有重量1树的直径？树的直径由两个顶点之间的最长路径的长度给出.
知道如何解决这个问题吗？
我怎么能生成和打印最快的情况设置为快速排序考虑作为枢轴中间元素？这是我对quicksort算法的实现:
void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
if (left < index - 1)
quickSort(arr, left, index - 1);
if (index < right)
quickSort(arr, index, right);
}
int partition(int arr[], int left, int right){
int i = left, j = right;
int tmp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
tmp = …我坚持这个问题(2周).任何想法如何处理它？
令L是n个不同整数的列表,假设L的x的元素在[1,750]的范围内.设计线性排序算法以排序L的元素
我已经尝试过插入排序.但我不确定我的做法是否正确:
Construct an array of bits. Initialize them to zero.
Read the input, for each value you see set the respective bit in the array to 1.
Scan the array, for each bit set, output the respective value.
复杂度=> O(2n)= O(n)