生活随笔
收集整理的這篇文章主要介紹了
数据结构——图的深度遍历
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
圖的遍歷方式有兩種，
深度優先廣度優先深度優先采用的是遞歸的方式來來實現，思想如下：
假設給定圖G的初態是所有頂點均未曾訪問過。在G中任選一頂點v為初始出發點(源點)，
**則深度優先遍歷可定義如下：
首先訪問出發點v，并將其標記為已訪問過；然后依次從v出發搜索v的每個鄰接點w。若w未曾訪問過，則以w為新的出發點繼續進行深度優先遍歷，直至圖中所有和源點v有路徑相通的頂點(亦稱為從源點可達的頂點)均已被訪問為止。若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復上述過程，直至圖中所有頂點均已被訪問為止。**
流程圖如下：
因為采用的是遞歸調用，那就需要有兩個函數，主要的遞歸調用的函數是放在private中的；在public有一個函數來調用這個遞歸函數，
public函數流程圖如下：
private 函數如下：
在這里用的臨界表的形式來存儲無向圖；
圖的結構體的定義和我圖的十字鏈表表示法中圖的結構體定義差不多，只是增加了一個標記位。用來標記這個結點是不是被訪問過。圖示如下：
還是要定義兩個結構體，圖的鄰接表是采用數組+鏈表的方式來實現的。那鏈表的結構體定義如下：
數組的結構體定義如下：
在這里是用無向圖圖的實現的，其實有向圖的實現和這個差不多少，還是也可以采用圖的鄰接表來實現，其實基本一樣，大體是一樣的，還是要設置標記位。我是采用下面的圖的測試的。
代碼如下：
// GraphList.cpp
// 深度優先遍歷
//
// Created by 橘子和香蕉 on 2018/11/25.
// Copyright ? 2018 橘子和香蕉. All rights reserved.
///*遇到的問題：1:首先是添加邊；用戶輸入的兩個結點，先要判斷哪個結點是新添加的，是倆都是，還是一個是，，然后設置位置。添加結點先是將數據放在數組，然后要將它添加到相應的鏈表中去，那就要申請新結點，我就是在初始化結點的時候沒有將結點中指針設置為NULL，才導致了我之后的錯誤，想想就覺得自己蠢。
2:在刪除結點的時候要判斷這個結點還有沒有鄰結點，若是沒有，就要刪除這個結點，*/#include <iostream>
using namespace std;
#define dataType char
#define MAXSIZE 100
typedef struct node{int position;node *next;
}node;
typedef struct Box{dataType data;node *out;bool isAccess;
}Box;
class Graph{
private:Box base[MAXSIZE];int vertexNum;int edgeNum;int locate(dataType data);void deleteEdgePrivate(int startPosition,int endPositon);void def(int position);bool isNotHaveNevNode(dataType data);void moveNode(dataType data);public:~Graph();void init(int vertexNum,int edgeNum);void create();void printNode(dataType data);void printGraph();void addEdge(dataType start,dataType end);void deleteEdge(dataType start,dataType end);void depthErgodic(dataType data);};
Graph::~Graph(){for (int i = 0; i<vertexNum; i++) {node *p= base[i].out;node *h = p;while ( p != NULL) {h = p->next;if(h == NULL) return;delete p;p = h->next;}}// delete []base;
}
void Graph::init(int vertexNum, int edgeNum){this->vertexNum = vertexNum;this->edgeNum = edgeNum;
}
int Graph::locate(dataType data){for (int i = 0; i<vertexNum; i++) {if(base[i].data == data){return i;}}return -1;
}
void Graph::create(){cout<<"create Graph begin\n";for (int i = 0; i<vertexNum; i++) {cout<<"input node data\n";cin>>base[i].data;base[i].out = NULL;base[i].isAccess = false;}node *startNode,*endNode;int startPosition;int endPosition;dataType start;dataType end;for (int i = 0; i<edgeNum; i++) {cout<<"input edge start and end\n";cin>>start>>end;startPosition = locate(start);endPosition = locate(end);//創建鏈表。先是創建start指向end;//在創建end指向start；endNode = new node;endNode->position = endPosition;endNode->next = base[startPosition].out;base[startPosition].out = endNode;startNode = new node;startNode->position = startPosition;startNode->next = base[endPosition].out;base[endPosition].out = startNode;}}
void Graph::printNode(dataType data){int position = locate(data);if(position == -1){cout<<"data is not exist\n";return;}else{node *h = base[position].out;cout<<"the data of"<<data<<":\t";while (h!=NULL) {cout<<base[h->position].data<<"\t";h=h->next;}}cout<<"\n";
}
void Graph::printGraph(){for (int i = 0; i<vertexNum; i++) {printNode(base[i].data);}
}
void Graph::addEdge(dataType start, dataType end){int startPosition = locate(start);int endPosition = locate(end);if(startPosition == -1){base[vertexNum].data = start;base[vertexNum].out = NULL;startPosition = vertexNum;init(vertexNum +1 , edgeNum+1);}if(endPosition == -1){base[vertexNum].data = end;base[vertexNum].out = NULL;endPosition = vertexNum;init(vertexNum +1 , edgeNum+1);}if(startPosition == -1 && endPosition == -1){base[vertexNum].data = start;startPosition = vertexNum;init(vertexNum +1 , edgeNum+1);base[vertexNum].data = end;endPosition = vertexNum;init(vertexNum +1 , edgeNum+1);}node* endNode = new node;endNode->position = endPosition;endNode->next = base[startPosition].out;base[startPosition].out = endNode;node* startNode = new node;startNode->position = startPosition;startNode->next = base[endPosition].out;base[endPosition].out = startNode;}void Graph::deleteEdge(dataType start, dataType end){/*a：刪除的時候要判斷倆結點的位置，然后一個一個的刪除，先是刪除start 到end這條表然后接著刪除end到start這條邊；其實刪除的操作都是一樣的，然后我就將刪除的操作獨立了出來，寫了一個函數，放到private中去，刪除start 到end和刪除end到start只不過就是在函數調用的時候顛倒就好了，但是這只限于無向圖。*/int startPosition= locate(start);int endPositon = locate(end);if(startPosition ==-1 || endPositon == -1){cout<<"node is not exist\n";return;}deleteEdgePrivate( startPosition,endPositon);deleteEdgePrivate(endPositon, startPosition);if( isNotHaveNevNode(start) == true){moveNode(start);}if(isNotHaveNevNode(end) == true){moveNode(end);}
}void Graph::deleteEdgePrivate(int startPosition,int endPositon){int n = 0;node * p = base[startPosition].out;node *h = base[startPosition].out;while (p != NULL) {if(n ==0 && p->position == endPositon ) {base[startPosition].out = p->next;delete p;return;}n++;if(n != 0 && p->position == endPositon){h->next = p->next;cout<<" "<<base[p->position].data<<endl;delete p;return ;}h = p;p = p->next;}
}void Graph::depthErgodic(dataType data){int position = locate(data);position == -1?cout<<"the data is not exist\n":cout<<"";def(position);}
void Graph::def(int position){node *p;cout<<base[position].data<<endl;base[position].isAccess = true;p = base[position].out;while (p != NULL) {if(base[p->position].isAccess == false){def(p->position);}p = p->next;}
}
/*p判斷還有沒有鄰結點*/
bool Graph::isNotHaveNevNode(dataType data){int position = locate(data);return base[position].out == NULL?true:false;
}
/*移動數據*/
void Graph::moveNode(dataType data){int position = locate(data);for (int i = position; i<vertexNum ; i++) {base[i].data = base[i+1].data;base[i].out = base[i+1].out;base[i].isAccess = base[i+1].isAccess;}this->vertexNum -= 1;
}
int main(){Graph a;a.init(4, 4);a.create();
// a.printNode('b');
// a.printGraph();a.addEdge('d', 'e');a.printNode('d');a.printNode('e');a.deleteEdge('d', 'e');a.printNode('e');return 1;
}
總結
以上是生活随笔為你收集整理的数据结构——图的深度遍历的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
