Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
4elus
0 / 0 / 0
Регистрация: 30.06.2017
Сообщений: 104
1

Поиск в графе

28.12.2018, 23:30. Просмотров 922. Ответов 2

Здравствуйте, есть следующая задача:

Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.

Есть код:



Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Graph{
    private final int MAX_VERTS = 9;
    public Vertex vertexList[]; // Список вершин
    private int adjMat[][]; // Матрица смежности
    private int nVerts; // Текущее количество вершин
    private StackX theStackX;
 
    public Graph(){
        vertexList = new Vertex[MAX_VERTS];
        adjMat = new int[MAX_VERTS][MAX_VERTS];
        nVerts = 0;
 
        for (int i = 0; i < MAX_VERTS; i++)
            for (int j = 0; j < MAX_VERTS; j++)
                adjMat[i][j] = 0;
            theStackX = new StackX();
 
    }
 
 
 
    // Метод возвращает непосещенную вершину, смежную по отношению к v
    public int getUnvisitedVertex(int v){
        for (int i = 0; i < nVerts; i++) {
            if (adjMat[v][i] == 1 && vertexList[i].wasVisited == false)
                return i;
        }
 
        return -1;
    }
 
    // обход в глубину
    public void dfs(){
        vertexList[0].wasVisited = true;
        displayVertex(0);
        theStackX.push(0);
 
        while (!theStackX.isEmpty()){
            int v = getUnvisitedVertex(theStackX.peek());
 
            if (v == -1)
                theStackX.pop();
            else{
                vertexList[v].wasVisited = true;
                displayVertex(v);
                theStackX.push(v);
            }
        }
        //System.out.println(c);
        // Стек пуст, работа закончена
        for (int i = 0; i < nVerts; i++) {
            vertexList[i].wasVisited = false;
        }
    }
 
    // Добавляем вершину
    public void addVertex(int val){
        vertexList[nVerts++] = new Vertex(val);
    }
 
    // Добавляем края
    public void addEdge(int start, int end){
        adjMat[start][end] = 1;
        adjMat[end][start] = 1;
    }
 
    public void displayVertex(int v){
        System.out.print(vertexList[v].value + " ");
 
    }
}
Java
1
2
3
4
5
6
7
8
9
public class Vertex {
    public int value;
    public boolean wasVisited;
 
    public Vertex(int value){
        this.value = value;
        wasVisited = false;
    }
}
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class StackX {
    private final int SIZE = 20;
    private int[] st;
    private int top;
 
    public StackX(){
        st = new int[SIZE];
        top = -1;
    }
 
    // Размещение элемента в стеке
    public void push(int j){
        st[++top] = j;
    }
 
    // Извлечение элемента из стека
    public int pop(){
        return st[top--];
    }
 
    // Чтение с вершины стека
    public int peek(){
        return st[top];
    }
 
    // Если стек пуст
    public boolean isEmpty(){
        return top == -1;
    }
}
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Runner {
    private static ArrayList<Integer> list = new ArrayList<>();
 
    public static void main(String[] args) {
        Graph theGraph = new Graph();
 
        theGraph.addVertex(3);
        theGraph.addVertex(5);
        theGraph.addVertex(3);
        theGraph.addVertex(10);
        theGraph.addVertex(7);
        theGraph.addVertex(4);
        theGraph.addVertex(0);
        theGraph.addVertex(2);
        theGraph.addVertex(4);
        
        theGraph.addEdge(0, 1);
        theGraph.addEdge(1, 2);
        theGraph.addEdge(2, 3);
        theGraph.addEdge(3, 4);
        theGraph.addEdge(4, 5);
        theGraph.addEdge(4, 6);
        theGraph.addEdge(4, 7);
        theGraph.addEdge(4, 8);
 
 
        System.out.println("Visits: ");
        theGraph.dfs();
        System.out.println();
    }
 
}
Сделал обход в глубину, посещаю все вершины, но как прописать условие что встретился повторяющиеся элемент ?
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2018, 23:30
Ответы с готовыми решениями:

Поиск в ширину в графе
У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и полчается список...

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин...

Поиск критических элементов в графе
Критической вершиной в графе называется вершина, удаление которой приводит к разделению графа на 2...

2
Shamil1
Модератор
2304 / 1598 / 358
Регистрация: 26.03.2015
Сообщений: 5,815
29.12.2018, 12:01 2
Цитата Сообщение от 4elus Посмотреть сообщение
Дан массив A длины (n+1), содержащий натуральные числа от 1 до n. Найти любой повторяющийся элемент за время O(n), не изменяя массив и не используя дополнительной памяти.
В этой задаче нельзя использовать графы.
0
Shamil1
Модератор
2304 / 1598 / 358
Регистрация: 26.03.2015
Сообщений: 5,815
29.12.2018, 12:18 3
На первый взгляд подойдёт что-нибудь типа этого:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Solve(int[] a)
{
    int i = 0;
    while(true)
    {
        int j = a[i] - 1;
        if(i == j)
        {
            i++;
            continue;
        }
        if(a[i] == a[j])
        {
            return a[i];
        }
        (a[i],a[j]) = (a[j],a[i]);
        i = j;
    }
}
Ставим все числа на свои места.
Если число уже на своём месте, то переходим к следующему.
Если место уже занято, то это и есть повторяющийся элемент.

з.ы. Работу алгоритма не проверял. Возможно, нужно добавить обработку каких-то специальных случаев.
1
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
29.12.2018, 12:18

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...

поиск цикла максимальной длинны в графе
Никто не подскажет как в неориентированном графе можно найти цикл максимальной длинны, включающий...

Поиск нескольких кратчайших путей в графе
Добрый день всем! Такая казалось бы тривиальная задача для гуру программистов, но ничего толкового...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru