学步园

1. 图的表示：邻接矩阵，邻接表

2. 图的遍历：广度优先遍历，深度优先遍历（非递归）

3. 注：BFS通常用于从某个源节点开始，寻找最短路径距离，DFS通常作为另一个算法的一个子程序。

1) Edge.h

#ifndef EDGE_H_<br /> #define EDGE_H_<br /> #include <iostream><br /> using namespace std;<br /> class Edge {<br /> public:<br /> int from;<br /> int to;<br /> Edge *next;<br /> // Edge(int f = -1, int t = -1, Edge* n = NULL) :<br /> // from(f), to(t), next(n) {<br /> // }<br /> };<br /> ostream& operator <<(ostream& os, Edge *q){<br /> if(!q){<br /> cerr << "null Edge!" << endl;<br /> }else{<br /> os << "(" << q->from << ", " << q->to << ")";<br /> }<br /> return os;<br /> }<br /> class Edges {<br /> public:<br /> void insert(Edge* e) {<br /> e->next = head;<br /> head = e;<br /> }<br /> static Edges* getInstance(){<br /> if(!_instance){<br /> _instance = new Edges();<br /> }<br /> return _instance;<br /> }<br /> Edge* head;<br /> private:<br /> Edges(Edge* h = NULL):head(h){</p> <p> }<br /> static Edges* _instance;<br /> };<br /> // static variable initialization<br /> Edges* Edges::_instance = NULL;<br /> ostream& operator <<(ostream& os, Edges *q){<br /> if(!q){<br /> cerr << "null Edges!" << endl;<br /> }else{<br /> Edge* p = q->head;<br /> while(p){<br /> os << p << " ";<br /> p = p->next;<br /> }<br /> os << endl;<br /> }<br /> return os;<br /> }<br /> #endif /*EDGE_H_*/<br />

2) Graph.h

#ifndef GRAPH_H_<br /> #define GRAPH_H_<br /> #include "Edge.h"<br /> #include "List.h"<br /> #include "GraphBuilder.h"<br /> #include <queue><br /> #include <stack><br /> #include <limits><br /> enum COLOR {<br /> WHITE,<br /> GRAY,<br /> BLACK<br /> };<br /> // the current visit vertex v and its edge n<br /> class Frame {<br /> public:<br /> int v;<br /> Node* n;<br /> Frame(int _v = -1, Node *_n = NULL) :<br /> v(_v), n(_n) {<br /> }<br /> };<br /> class Graph {<br /> public:<br /> Graph(int _v = 0, Edges* _e = NULL, bool directed = false) :<br /> v(_v), edges(_e), isDirected(directed) {<br /> }<br /> Edges* getEdges() const {<br /> return edges;<br /> }<br /> virtual Graph* getTranspose() = 0;<br /> virtual Graph* getSquare() = 0;<br /> virtual void build(GraphBuilder *b) = 0;<br /> virtual void display() = 0;<br /> virtual int bfs(int s) = 0;<br /> virtual void diameter() = 0;<br /> virtual void dfs() = 0;<br /> protected:<br /> int v;<br /> Edges* edges;<br /> bool isDirected;<br /> };<br /> class AdjMatrixGraph : public Graph {<br /> public:<br /> friend class MatrixGraphBuilder;<br /> AdjMatrixGraph(int _v = 0, Edges* _e = NULL, bool directed = false) :<br /> Graph(_v, _e, directed) {<br /> A = new int[_v*_v];<br /> // reset the matrix<br /> for (int i = 0; i < _v; i++) {<br /> for (int j = 0; j < _v; j++) {<br /> A[i * _v + j] = 0;<br /> }<br /> }<br /> }<br /> void build(GraphBuilder *b) {<br /> b->buildMatrix(this);<br /> }<br /> void display() {<br /> for (int i = 0; i < v; i++) {<br /> for (int j = 0; j < v; j++) {<br /> cout << A[i * v + j]<< " ";<br /> }<br /> cout << endl;<br /> }<br /> cout << endl;<br /> }<br /> Graph* getTranspose() {<br /> AdjMatrixGraph *g = new AdjMatrixGraph(v);<br /> for (int i = 0; i < v; i++) {<br /> for (int j = 0; j < v; j++) {<br /> g->A[j * v + i] = A[i * v + j];<br /> }<br /> }<br /> return g;<br /> }<br /> Graph* getSquare() {<br /> AdjMatrixGraph *g = new AdjMatrixGraph(v);<br /> for (int i = 0; i < v; i++) {<br /> for (int j = 0; j < v; j++) {<br /> for (int k = 0; k < v; k++) {<br /> if ( (i != j) && A[i * v + k ]&& A[k * v + j]) {<br /> g->A[i * v + j] = 1;<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> return g;<br /> }<br /> int bfs(int s) {<br /> COLOR *c = new COLOR[v];<br /> int *d = new int[v];<br /> int *p = new int[v];<br /> for (int i = 0; i < v; i++) {<br /> c[i] = WHITE;<br /> d[i] = numeric_limits<int>::max();<br /> p[i] = -1;<br /> }<br /> c[s] = GRAY;<br /> d[s] = 0;<br /> p[s] = -1;<br /> queue<int> q;<br /> q.push(s);<br /> while (!q.empty()) {<br /> int u = q.front();<br /> q.pop();<br /> for (int j = 0; j < v; j++) {<br /> if ((j != u ) && (A[u * v + j] > 0)&& (c[j] == WHITE)) {<br /> c[j] = GRAY;<br /> d[j] = d[u] + 1;<br /> p[j] = u;<br /> q.push(j);<br /> }<br /> }<br /> c[u] = BLACK;<br /> }<br /> for (int i = 0; i < v; i++) {<br /> cout << i << " : "<< c[i]<< " "<< d[i]<< " "<< p[i]<< endl;<br /> if (p[i] == -1) {<br /> cout << "no path from "<< s << " to "<< i << endl;<br /> } else {<br /> int pp = p[i];<br /> while (pp != -1) {<br /> cout << pp << " ";<br /> pp = p[pp];<br /> }<br /> }<br /> cout << endl;<br /> }<br /> return 0;<br /> }<br /> void diameter() {<br /> }<br /> void dfs() {<br /> }<br /> private:<br /> int *A;<br /> };<br /> class AdjListGraph : public Graph {<br /> friend class ListGraphBuilder;<br /> private:<br /> List* A;<br /> public:<br /> AdjListGraph(int _v = 0, Edges* _e = NULL, bool directed = false) :<br /> Graph(_v, _e, directed) {<br /> A = new List[_v];<br /> }<br /> void build(GraphBuilder *b) {<br /> b->buildList(this);<br /> }<br /> void display() {<br /> for (int i = 0; i < v; i++) {<br /> List l = A[i];<br /> Node* p = l.head;<br /> cout << "["<< i << "] ";<br /> while (p) {<br /> cout << "->"<< p->v<< " ";<br /> p = p->next;<br /> }<br /> cout << endl;<br /> }<br /> cout << endl;<br /> }<br /> Graph* getTranspose() {<br /> AdjListGraph *g = new AdjListGraph(v);<br /> for (int i = 0; i < v; i++) {<br /> List l = A[i];<br /> Node* p = l.head;<br /> while (p) {<br /> int to = p->v;<br /> Node * node = new Node(i);<br /> (g->A[to]).insertBack(node);<br /> p = p->next;<br /> }<br /> }<br /> return g;<br /> }<br /> Graph* getSquare() {<br /> AdjListGraph *g = new AdjListGraph(v);<br /> for (int i = 0; i < v; i++) {<br /> List p = A[i];<br /> Node* pn = p.head;<br /> while (pn) {<br /> int to = pn->v;<br /> List q = A[to];<br /> Node* qn = q.head;<br /> while (qn) {<br /> int qv = qn->v;<br /> Node *node = new Node(qv);<br /> (g->A[i]).insertBack(node);<br /> qn = qn->next;<br /> }<br /> pn = pn->next;<br /> }<br /> }<br /> return g;<br /> }<br /> int bfs(int s) {<br /> COLOR *c = new COLOR[v];<br /> int *d = new int[v];<br /> int *p = new int[v];<br /> for (int i = 0; i < v; i++) {<br /> c[i] = WHITE;<br /> d[i] = numeric_limits<int>::max();<br /> p[i] = -1;<br /> }<br /> c[s] = GRAY;<br /> d[s] = 0;<br /> p[s] = -1;<br /> queue<int> q;<br /> q.push(s);<br /> while (!q.empty()) {<br /> int u = q.front();<br /> q.pop();<br /> List l = A[u];<br /> Node* h = l.head;<br /> while (h) {<br /> int v = h->v;<br /> if (c[v] == WHITE) {<br /> c[v] = GRAY;<br /> d[v] = d[u] + 1;<br /> p[v] = u;<br /> q.push(v);<br /> }<br /> h = h->next;<br /> }<br /> c[u] = BLACK;<br /> }<br /> // for (int i = 0; i < v; i++) {<br /> // cout << i << " : " << c[i] << " " << d[i] << " " << p[i] << endl;<br /> // if (p[i] == -1){<br /> // cout << "no path from " << s << " to " << i << endl;<br /> // }else{<br /> // int pp = p[i];<br /> // while(pp != -1){<br /> // cout << pp << " ";<br /> // pp = p[pp];<br /> // }<br /> // }<br /> // cout << endl;<br /> // }<br /> // distance is the height of tree<br /> int distance = 0;<br /> for (int i = 0; i < v; i++) {<br /> if (distance < d[i]) {<br /> distance = d[i];<br /> }<br /> }<br /> return distance;<br /> }<br /> void diameter() {<br /> int d = 0, j = -1, i = 0;<br /> for (; i < v; i++) {<br /> int distance = bfs(i);<br /> if (d < distance) {<br /> d = distance;<br /> j = i;<br /> }<br /> }<br /> cout << "the diameter is "<< d << ", from "<< i << endl;<br /> }<br /> void dfs() {<br /> COLOR *c = new COLOR[v];<br /> int *p = new int[v];<br /> // discover time<br /> int *d = new int[v];<br /> // finish time<br /> int *f = new int[v];<br /> // connection component<br /> int *cc = new int[v];<br /> int time = 0;<br /> int com = 0;<br /> for (int i = 0; i < v; i++) {<br /> c[i] = WHITE;<br /> p[i] = -1;<br /> d[i] = 0;<br /> f[i] = 0;<br /> cc[i] = -1;<br /> }<br /> // begin search<br /> stack<Frame*> s;<br /> for (int i = 0; i < v; i++) {<br /> if (c[i] == WHITE) {<br /> c[i] = GRAY;<br /> time++;<br /> com++;<br /> d[i] = time;<br /> cc[i] = com;<br /> Node* h = A[i].head;<br /> s.push(new Frame(i, h));<br /> while (!s.empty()) {<br /> Frame *fm = s.top();<br /> Node* curEdge = fm->n;<br /> if (curEdge) {<br /> int cur = curEdge->v;<br /> switch (c[cur]) {<br /> case WHITE:<br /> cout << "(" << fm->v << ", " << cur << ") tree edge" << endl;<br /> c[cur] = GRAY;<br /> time++;<br /> cc[cur] = com;<br /> d[cur] = time;<br /> p[cur] = fm->v;<br /> s.push(new Frame(cur, A[cur].head));<br /> break;<br /> case GRAY:<br /> cout << "(" << fm->v << ", " << cur << ") back edge" << endl;<br /> // find a back edge<br /> s.pop();<br /> s.push(new Frame(fm->v, fm->n->next));<br /> break;<br /> case BLACK:<br /> // find a front edge or cross edge<br /> if (cc[fm->v] == cc[cur]){<br /> cout << "(" << fm->v << ", " << cur << ") front edge" << endl;<br /> }else{<br /> cout << "(" << fm->v << ", " << cur << ") cross edge" << endl;<br /> }<br /> s.pop();<br /> s.push(new Frame(fm->v, fm->n->next));<br /> break;<br /> default:<br /> break;<br /> }<br /> }<br /> else {<br /> s.pop();<br /> // finish visit f.v<br /> c[fm->v] = BLACK;<br /> f[fm->v] = ++time;<br /> }<br /> }<br /> }<br /> }<br /> for (int j = 0; j < v; j++) {<br /> cout << "vertex "<< j << " : component " << cc[j] << " ("<< d[j]<< ", "<< f[j] << ")" << endl;<br /> }<br /> }<br /> };<br /> void MatrixGraphBuilder::buildMatrix(Graph* _g) {<br /> AdjMatrixGraph* g = dynamic_cast<AdjMatrixGraph*>(_g);<br /> if (!g) {<br /> return;<br /> }<br /> Edges* e = g->getEdges();<br /> Edge* p = e->head;<br /> while (p) {<br /> int from = p->from - 1;<br /> int to = p->to - 1;<br /> int v = g->v;<br /> g->A[from * v + to] = 1;<br /> p = p->next;<br /> }<br /> }<br /> void ListGraphBuilder::buildList(Graph* _g) {<br /> AdjListGraph* g = dynamic_cast<AdjListGraph*>(_g);<br /> if (!g) {<br /> return;<br /> }<br /> Edges* e = g->getEdges();<br /> Edge* p = e->head;<br /> List* A = g->A;<br /> while (p) {<br /> int from = p->from - 1;<br /> int to = p->to - 1;<br /> Node *node = new Node(to);<br /> (A[from]).insertBack(node);<br /> p = p->next;<br /> }<br /> }<br /> #endif /*GRAPH_H_*/<br />

3) GraphBuilder.h

#ifndef GRAPHBUILDER_H_<br /> #define GRAPHBUILDER_H_<br /> class Graph;<br /> class AdjMatrixGraph;<br /> class AdjListGraph;<br /> class GraphBuilder {<br /> public:<br /> virtual void buildMatrix(Graph* g) {<br /> }<br /> ;<br /> virtual void buildList(Graph* g) {<br /> }<br /> ;<br /> };<br /> class MatrixGraphBuilder : public GraphBuilder {<br /> public:<br /> static MatrixGraphBuilder* getInstance() {<br /> if (!_instance) {<br /> _instance = new MatrixGraphBuilder();<br /> }<br /> return _instance;<br /> }<br /> void buildMatrix(Graph* g);<br /> private:<br /> MatrixGraphBuilder() {<br /> }<br /> static MatrixGraphBuilder* _instance;<br /> };<br /> MatrixGraphBuilder* MatrixGraphBuilder::_instance= NULL;<br /> class ListGraphBuilder : public GraphBuilder {<br /> public:<br /> static ListGraphBuilder* getInstance() {<br /> if (!_instance) {<br /> _instance = new ListGraphBuilder();<br /> }<br /> return _instance;<br /> }<br /> void buildList(Graph* g);<br /> private:<br /> ListGraphBuilder() {<br /> }<br /> static ListGraphBuilder* _instance;<br /> };<br /> ListGraphBuilder* ListGraphBuilder::_instance= NULL;<br /> #endif /*GRAPHBUILDER_H_*/<br />

4) List.h

#ifndef LIST_H_<br /> #define LIST_H_<br /> class Node {<br /> public:<br /> Node(int _v = -1, Node* _next = NULL) :<br /> v(_v), next(_next) {<br /> }<br /> int v;<br /> Node* next;<br /> };<br /> class List {<br /> public:<br /> List() {<br /> head = NULL;<br /> }<br /> void insertFront(Node* p) {<br /> p->next = head;<br /> head = p;<br /> }<br /> // check duplicate<br /> void insertBack(Node* p) {<br /> Node* q = head, *pre= NULL;<br /> while (q) {<br /> if (q->v == p->v) {<br /> return;<br /> }<br /> pre = q;<br /> q = q->next;<br /> }<br /> p->next = NULL;<br /> if (!pre) {<br /> // head is NULL<br /> head = p;<br /> } else {<br /> pre->next = p;<br /> }<br /> }<br /> public:<br /> Node* head;<br /> };<br /> #endif /*LIST_H_*/<br />

5) Test.cpp

#include "Graph.h"<br /> int main(){<br /> // Edge e[] = {{1,2}, {1,5}, {2,1}, {2,3}, {2,4}, {2,5}, {3,2}, {3,4}, {4,2}, {4,3}, {4,5}, {5,1}, {5,2}, {5,4}};<br /> Edge e[] = {{1,2}, {1,4}, {2,5}, {3,5}, {3,6}, {4,2}, {5,4}};</p> <p> Edges* edges = Edges::getInstance();<br /> for(int i = 0; i < sizeof(e)/sizeof(Edge); i++){<br /> edges->insert(&(e[i]));<br /> }</p> <p>// AdjMatrixGraph *g1 = new AdjMatrixGraph(5, edges);<br /> // MatrixGraphBuilder* mgb = MatrixGraphBuilder::getInstance();<br /> // g1->build(mgb);<br /> // g1->display();<br /> // g1->bfs(0);<br /> // Graph *g1t = g1->getTranspose();<br /> // g1t->display();<br /> // g1t = g1->getSquare();<br /> // g1t->display();</p> <p> AdjListGraph *g2 = new AdjListGraph(6, edges);<br /> ListGraphBuilder *lgb = ListGraphBuilder::getInstance();<br /> g2->build(lgb);<br /> g2->display();<br /> // Graph *g2t = g2->getTranspose();<br /> // g2t->display();<br /> // g2t = g2->getSquare();<br /> // g2t->display();<br /> // g2->bfs(0);<br /> // g2->diameter();<br /> g2->dfs();</p> <p> return 0;<br /> }<br />

6) 测试结果

[0] ->3 ->1<br /> [1] ->4<br /> [2] ->5 ->4<br /> [3] ->1<br /> [4] ->3<br /> [5]<br /> (0, 3) tree edge<br /> (3, 1) tree edge<br /> (1, 4) tree edge<br /> (4, 3) back edge<br /> (1, 4) front edge<br /> (3, 1) front edge<br /> (0, 3) front edge<br /> (0, 1) front edge<br /> (2, 5) tree edge<br /> (2, 5) front edge<br /> (2, 4) cross edge<br /> vertex 0 : component 1 (1, 8)<br /> vertex 1 : component 1 (3, 6)<br /> vertex 2 : component 2 (9, 12)<br /> vertex 3 : component 1 (2, 7)<br /> vertex 4 : component 1 (4, 5)<br /> vertex 5 : component 2 (10, 11)<br />