מאמר זה הוא המשך לסקירה הקצרה שלי על אלגוריתמים. הנה הקישור לחלק הראשון . בעבר, בדקנו אלגוריתמים שונים של מיון מערכים ומה שנקרא אלגוריתם חמדן . היום נדבר על גרפים ואלגוריתמים הקשורים אליהם. גרף הוא אחד המבנים הגמישים והאוניברסליים ביותר בתכנות. גרף G מצוין בדרך כלל באמצעות זוג קבוצות G = (V, R) , כאשר:
- V הוא קבוצת הקודקודים;
- R הוא קבוצת הקווים המחברים בין זוגות קודקודים.
3. אלגוריתמים לחיפוש נתיבים (עומק, רוחב)
אחת הפעולות הבסיסיות שמתבצעות על גרפים היא לקבוע את כל הקודקודים שניתן להגיע אליהם מקודקוד נתון. תארו לעצמכם שאתם מנסים לקבוע כיצד להגיע מעיר אחת לאחרת עם העברות אפשריות. לחלק מהערים ניתן להגיע ישירות, בעוד שאחרות דורשות עיקוף דרך ערים אחרות. ישנם מצבים רבים אחרים בהם ייתכן שיהיה צורך למצוא את כל הקודקודים אליהם ניתן למצוא נתיב מקודקוד נתון. לכן, ישנן שתי דרכים עיקריות לחצות גרפים: מעבר עומק-ראשון ומעבר רוחב-ראשון , אותם נשקול. שתי השיטות יבטיחו איטרציה על כל הקודקודים המחוברים. לבחינה נוספת של אלגוריתמים של עומק-ראשון ושל רוחב-ראשון , קחו את הגרף הבא:מעבר עומק ראשון
זוהי אחת השיטות הנפוצות ביותר למעבר גרפים. אסטרטגיית חיפוש עומק -ראשון זו מורכבת מכניסה "עמוק" לתוך הגרף ככל האפשר, ועם הגעה למבוי סתום, חזרה לקודקוד הקרוב ביותר שיש לו קודקודים סמוכים שלא ביקרו בהם קודם לכן. אלגוריתם זה מאחסן מידע על המחסנית לגבי היכן לחזור כשמגיעים למבוי סתום. כללים למעבר עומק ראשון:- בקר בקודקוד סמוך, שלא ביקר בעבר, סמן אותו והנח אותו על הערימה.
- עבור אל הקודקוד הזה.
- חזור על שלב 1.
- אם אי אפשר להשלים את שלב 1, חזרו לקודקוד הקודם ונסו לחזור על כלל 1. אם זה בלתי אפשרי, חזרו לקודקוד שלפניו וכן הלאה, עד שנמצא קודקוד שממנו נוכל להמשיך את המעבר.
- המשך עד שכל הקודקודים על הערימה.
public class Graph {
private final int MAX_VERTS = 10;
private Vertex vertexArray[]; //массив вершин
private int adjMat[][]; // матрица смежности
private int nVerts; // текущее количество вершин
private Stack<integer> stack;
public Graph() { // инициализация внутрених полей
vertexArray = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int j = 0; j < MAX_VERTS; j++) {
for (int k = 0; k < MAX_VERTS; k++) {
adjMat[j][k] = 0;
}
}
stack = new Stack<>();
}
public void addVertex(char lab) {
vertexArray[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v) {
System.out.println(vertexArray[v].getLabel());
}
public void dfs() { // обход в глубину
vertexArray[0].setWasVisited(true); // берётся первая вершина
displayVertex(0);
stack.push(0);
while (!stack.empty()) {
int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
if (v == -1) { // если непройденных смежных вершин нету
stack.pop(); // элемент извлекается из стека
}
else {
vertexArray[v].setWasVisited(true);
displayVertex(v);
stack.push(v); // элемент попадает на вершину стека
}
}
for (int j = 0; j < nVerts; j++) { // сброс флагов
vertexArray[j].wasVisited = false;
}
}
private int getAdjUnvisitedVertex(int v) {
for (int j = 0; j < nVerts; j++) {
if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
return j; //возвращает первую найденную вершину
}
}
return -1;
}
}
</integer>
החלק העליון נראה כך:
public class Vertex {
private char label; // метка А например
public boolean wasVisited;
public Vertex(final char label) {
this.label = label;
wasVisited = false;
}
public char getLabel() {
return this.label;
}
public boolean isWasVisited() {
return this.wasVisited;
}
public void setWasVisited(final boolean wasVisited) {
this.wasVisited = wasVisited;
}
}
בוא נריץ את האלגוריתם הזה עם קודקודים ספציפיים ונראה אם הוא עובד כמו שצריך:
public class Solution {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex('A'); //0
graph.addVertex('B'); //1
graph.addVertex('C'); //2
graph.addVertex('D'); //3
graph.addVertex('E'); //4
graph.addVertex('F'); //5
graph.addVertex('G'); //6
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(0,3);
graph.addEdge(1,4);
graph.addEdge(3,5);
graph.addEdge(5,6);
System.out.println("Visits: ");
graph.dfs();
}
}
פלט מסוף:
ביקורים: A B E C D F G
מכיוון שיש לנו מטריצת סמיכות ובשיטת ההליכה אנו משתמשים בלולאה המקננת בתוך לולאה, מורכבות הזמן תהיה O(N²) .
ללכת לרוחב
אלגוריתם זה, כמו חציית עומק-ראשון, הוא אחת השיטות הפשוטות והבסיסיות ביותר למעבר בגרף. המהות שלו היא שיש לנו קודקוד זרם מסוים, שממנו אנחנו מכניסים את כל הקודקודים הסמוכים, לא חצויים לתוך תור ובוחרים את האלמנט הבא (שמאוחסן ראשון בתור) כדי להפוך אותו לעדכני... אם נשבור את האלגוריתם הזה לתוך בשלבים, נוכל להדגיש את הכללים הבאים:- בקרו בקודקוד הבא, שלא ביקר בעבר, בצמוד לקודקוד הנוכחי, סמנו אותו מראש והוסיפו אותו לתור.
- אם לא ניתן למלא את כלל מס' 1, הסר את הקודקוד מהתור והפוך אותו לקודקוד הנוכחי.
- אם כללים #1 ו-#2 בלתי אפשריים, המעבר הושלם וכל הקודקודים עברו (אם הגרף שלנו מחובר).
public class Graph {
private final int MAX_VERTS = 10;
private Vertex vertexList[]; //массив вершин
private int adjMat[][]; // матрица смежности
private int nVerts; // текущее количество вершин
private Queue<integer> queue;
public Graph() {
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
nVerts = 0;
for (int j = 0; j < MAX_VERTS; j++) {
for (int k = 0; k < MAX_VERTS; k++) { // заполнение матрицы смежности нулями
adjMat[j][k] = 0;
}
}
queue = new PriorityQueue<>();
}
public void addVertex(char lab) {
vertexList[nVerts++] = new Vertex(lab);
}
public void addEdge(int start, int end) {
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}
public void displayVertex(int v) {
System.out.println(vertexList[v].getLabel());
}
public void bfc() { // обход в глубину
vertexList[0].setWasVisited(true);
displayVertex(0);
queue.add(0);
int v2;
while (!queue.isEmpty()) {
int v = queue.remove();
while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
vertexList[v2].wasVisited =true;
displayVertex(v2);
queue.add(v2);
}
}
for (int j = 0; j < nVerts; j++) { // сброс флагов
vertexList[j].wasVisited = false;
}
}
private int getAdjUnvisitedVertex(int v) {
for (int j = 0; j < nVerts; j++) {
if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
return j; //возвращает первую найденную вершину
}
}
return -1;
}
}
</integer>
מחלקת Vertex זהה למחלקה מאלגוריתם החיפוש העומק-ראשון . בואו נפעיל את האלגוריתם הזה:
public class Solution {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex('A'); //0
graph.addVertex('B'); //1
graph.addVertex('C'); //2
graph.addVertex('D'); //3
graph.addVertex('E'); //4
graph.addVertex('F'); //5
graph.addVertex('G'); //6
graph.addEdge(0,1);
graph.addEdge(0,2);
graph.addEdge(0,3);
graph.addEdge(1,4);
graph.addEdge(3,5);
graph.addEdge(5,6);
System.out.println("Visits: ");
graph.bfc();
}
}
פלט מסוף:
ביקורים: A B C D E F G
שוב: יש לנו מטריצת סמיכות ומשתמשים בלולאה המקוננת בתוך לולאה, כך ש- O(N²) היא מורכבות הזמן של האלגוריתם שלמעלה.
4. האלגוריתם של דיקסטרה
כפי שהוזכר קודם לכן, גרפים יכולים להיות מכוונים או בלתי מכוונים . וכפי שאתה זוכר, הם עדיין יכולים להיות משוקללים . גרפים משוקללים ומכוונים נמצאים לרוב בחיים האמיתיים: למשל, מפת ערים, שבהן הערים הן קודקודים, השבילים ביניהן כבישים, בכבישים יכולים להיות תנועה חד-כיוונית - כיוון הגרף. נניח שאתה עוסק בהובלת מטענים ואתה צריך ליצור את המסלול הקצר ביותר בין שתי ערים רחוקות. איך תעשה זאת? אחת הבעיות הנפוצות ביותר הכוללות גרפים משוקללים היא הבעיה של בחירת הנתיב הקצר ביותר בין שני קודקודים. כדי לפתור בעיה זו אנו משתמשים באלגוריתם של דיקסטרה . ברצוני לציין מיד שעל ידי ביצוע האלגוריתם של דיקסטרה נגלה את הנתיבים הקצרים ביותר לכל הקודקודים מהנתיב ההתחלתי נתון. אילו שלבים יש לאלגוריתם הזה? אנסה לענות על השאלה הזו. שלבי האלגוריתם של דיקסטרה:- שלב 1 : חפש את הצומת, שהמעבר אליו יהיה העלות הנמוכה ביותר. אתה עומד ממש בהתחלה ותוהה לאן ללכת: לצומת א' או לצומת ב' . כמה זמן ייקח להגיע לכל אחד מהצמתים הללו?
- שלב 2 : חישוב כמה זמן לוקח להגיע לכל השכנים של B שעדיין לא הושפעו מהאלגוריתם בעת תנועה לאורך קצה מ- B. אם הזמן החדש הזה יתברר כפחות מהישן, השביל דרך קצה B יהפוך לנתיב הקצר החדש ביותר עבור קודקוד זה.
- שלב 3 : סמן את קודקוד B כעבר.
- שלב 4 : עבור לשלב 1.
- לקודקוד A ישנם שלושה נתיבים אפשריים: ל- B במשקל 3, ל- C במשקל 5 ול- D במשקל 7. לפי הנקודה הראשונה של האלגוריתם, נבחר את הצומת עם המעבר הנמוך ביותר עלות - כלומר ל- B.
- מכיוון שהקודקוד השכן היחיד שאינו עובר ל- B הוא קודקוד E , אנו בודקים מה יהיה הנתיב במעבר דרך קודקוד זה. 3( AB ) + 6( BE ) = 9.
לפיכך, נציין שהנתיב הקצר ביותר הנוכחי ל-AE = 9.
- מכיוון שהעבודה שלנו עם קודקוד B כבר הושלמה, אנו עוברים לבחירת הקודקוד הבא עם המשקל המינימלי של הקצה לפניו.
מקודקודים A ו- B אלה יכולים להיות קודקודים D (7), C (5), E (6).
ל- C יש את משקל הקצה הקטן ביותר , אז נמשיך לקודקוד הזה.
- לאחר מכן, כמו קודם, אנו מגלים את הדרך הקצרה ביותר לקודקודים שכנים כאשר אנו עוברים דרך C:
- AD = 5( AC ) + 3( CD ) = 8, אך מכיוון שהנתיב הקצר ביותר הקודם AC = 7, כלומר פחות מזה דרך C , נשאיר את הנתיב הקצר ביותר AD = 7 ללא שינוי.
- CE = 5( AC ) + 4( CE ) = 9, הנתיב הקצר ביותר החדש הזה שווה לקודם ולכן נשאיר אותו ללא שינוי.
- מהקודקודים הזמינים הקרובים ביותר, E ו- D , אנו בוחרים את הקודקוד עם משקל הקצה הקטן ביותר, כלומר D (3).
- אנו מגלים את הדרך הקצרה ביותר לשכנתה - F.
AF = 7( AD ) + 3( DF ) = 10
- מהקודקודים הזמינים הקרובים ביותר E ו- F , אנו בוחרים את הקודקוד עם המשקל הנמוך ביותר של הקצה אליו, כלומר F (3).
- אנו מגלים את הדרך הקצרה ביותר לשכנתה - ג'.
AG = 7( AD ) + 3( DF ) + 4( FG ) = 14
למעשה, כאן מצאנו את הנתיב מ- A ל- G.
אבל כדי לוודא שהוא הקצר ביותר, עלינו להפעיל את הצעדים שלנו גם עבור קודקוד E.
- מכיוון שלקודקוד G אין קודקודים סמוכים אליהם יוביל נתיב מכוון, נותר לנו רק קודקוד E : אנו בוחרים בו.
- אנחנו מגלים את הדרך הקצרה ביותר אל השכן - ג' .
AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, נתיב זה ארוך מה-AG(14) הקצר ביותר, לכן נשאיר את הנתיב הזה ללא שינוי.
מכיוון שאין קודקודים המובילים מ- G , אין זה הגיוני להריץ שלבים עבור קודקוד נתון. לכן, עבודת האלגוריתם יכולה להיחשב שלמה.
public class Vertex {
private char label;
private boolean isInTree;
public Vertex(char label) {
this.label = label;
this.isInTree = false;
}
public char getLabel() {
return label;
}
public void setLabel(char label) {
this.label = label;
}
public boolean isInTree() {
return isInTree;
}
public void setInTree(boolean inTree) {
isInTree = inTree;
}
}
מחלקת הקודקוד זהה למעשה למחלקת הקודקוד מחיפוש עומק-ראשון ורוחב-ראשון. כדי להציג את הנתיבים הקצרים ביותר, אנו זקוקים למחלקה חדשה שתכיל את הנתונים הדרושים לנו:
public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
private int distance; // текущая дистанция от начальной вершины
private List<integer> parentVertices; // текущий родитель вершины
public Path(int distance) {
this.distance = distance;
this.parentVertices = new ArrayList<>();
}
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
public List<integer> getParentVertices() {
return parentVertices;
}
public void setParentVertices(List<integer> parentVertices) {
this.parentVertices = parentVertices;
}
}
</integer></integer></integer>
בשיעור זה נוכל לראות את המרחק הכולל של השביל ואת הקודקודים שיכוסו במעבר בשביל הקצר ביותר. ועכשיו אני רוצה לשקול את המחלקה שבה, למעשה, מתרחשת המעבר הקצר ביותר של הגרף. אז, מחלקת הגרפים:
public class Graph {
private final int MAX_VERTS = 10;// максимальное количество вершин
private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
private Vertex vertexList[]; // список вершин
private int relationMatrix[][]; // матрица связей вершин
private int countOfVertices; // текущее количество вершин
private int countOfVertexInTree; // количество рассмотренных вершин в дереве
private List<path> shortestPaths; // список данных кратчайших путей
private int currentVertex; // текущая вершина
private int startToCurrent; //расстояние до currentVertex
public Graph() {
vertexList = new Vertex[MAX_VERTS]; // матрица смежности
relationMatrix = new int[MAX_VERTS][MAX_VERTS];
countOfVertices = 0;
countOfVertexInTree = 0;
for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
shortestPaths = new ArrayList<>();// задается пустым
}
}
}
public void addVertex(char lab) {// задание новых вершин
vertexList[countOfVertices++] = new Vertex(lab);
}
public void addEdge(int start, int end, int weight) {
relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
}
public void path() { // выбор кратчайшего пути
// задание данных для стартовой вершины
int startTree = 0; // стартуем с вершины 0
vertexList[startTree].setInTree(true); // включение в состав дерева первого element
countOfVertexInTree = 1;
// заполнение коротких путей для вершин смежных с стартовой
for (int i = 0; i < countOfVertices; i++) {
int tempDist = relationMatrix[startTree][i];
Path path = new Path(tempDist);
path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
shortestPaths.add(path);
}
// пока все вершины не окажутся в дереве
while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве
if (minDist == INFINITY) {
System.out.println("В графе пристувствуют недостижимые вершины");
break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
} else {
currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
}
vertexList[currentVertex].setInTree(true); //включение текущей вершины в дерево
countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
updateShortestPaths(); // обновление списка кратчайших путей
}
displayPaths(); // выводим в консоль результаты
}
public void clean() { // очиска дерева
countOfVertexInTree = 0;
for (int i = 0; i < countOfVertices; i++) {
vertexList[i].setInTree(false);
}
}
private int getMin() {
int minDist = INFINITY; // за точку старта взята "бесконечная" длина
int indexMin = 0;
for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
}
}
return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
}
private void updateShortestPaths() {
int vertexIndex = 1; // стартовая вершина пропускается
while (vertexIndex < countOfVertices) { // перебор столбцов
if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
vertexIndex++;
continue;
}
// вычисление расстояния для одного element sPath
// получение ребра от currentVert к column
int currentToFringe = relationMatrix[currentVertex][vertexIndex];
// суммирование всех расстояний
int startToFringe = startToCurrent + currentToFringe;
// определение расстояния текущего element vertexIndex
int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();
// сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
}
vertexIndex++;
}
}
private void displayPaths() { // метод для вывода кратчайших путей на экран
for (int i = 0; i < countOfVertices; i++) {
System.out.print(vertexList[i].getLabel() + " = ");
if (shortestPaths.get(i).getDistance() == INFINITY) {
System.out.println("0");
} else {
String result = shortestPaths.get(i).getDistance() + " (";
List<integer> parents = shortestPaths.get(i).getParentVertices();
for (int j = 0; j < parents.size(); j++) {
result += vertexList[parents.get(j)].getLabel() + " -> ";
}
System.out.println(result + vertexList[i].getLabel() + ")");
}
}
}
}
</integer></integer></path>
למעשה, זה כל הקסם =) ובכן, עכשיו, בואו נסתכל על האלגוריתם הזה בפעולה:
public class Solution {
public static void main(String[] args) {
Graph graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');
graph.addVertex('F');
graph.addVertex('G');
graph.addEdge(0, 1, 3);
graph.addEdge(0, 2, 5);
graph.addEdge(0, 3, 7);
graph.addEdge(1, 4, 6);
graph.addEdge(2, 4, 4);
graph.addEdge(2, 3, 3);
graph.addEdge(3, 5, 3);
graph.addEdge(4, 6, 6);
graph.addEdge(5, 6, 4);
System.out.println("Элементы имеют кратчайшие пути из точки A: ");
graph.path();
graph.clean();
}
}
והפלט בקונסולה:
לאלמנטים יש את הנתיבים הקצרים ביותר מנקודה A: A = 0 B = 3 (A -> B) C = 5 (A -> C) D = 7 (A -> D) E = 9 (A -> B -> E) F = 10 (A -> D -> F) G = 14 (A -> D -> F -> G)
מורכבות הזמן של אלגוריתם זה היא לא יותר מ- O(N²) מכיוון שיש לנו לולאות מקוננות בתוך לולאה. ובכן, זה הכל בשבילי היום, תודה על תשומת הלב שלך!
GO TO FULL VERSION