1. Interface (Graph.h, listQueue.h)
#ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED class Graph { private: struct adjListNode{ int node; adjListNode* next; adjListNode(int x, adjListNode* t) : node(x), next(t) {} }; typedef adjListNode* vtx; vtx* adjList; // adjacency list int countV; // number of vertices in the graph void dfsUtil(int, bool*); // recursive procedure in DFS public: Graph(int); ~Graph(); void addEdge(int, int); void removeEdge(int, int); bool isConnected(int, int); void showConnected(int); void dfs(int); void bfs(int); }; #endif // GRAPH_H_INCLUDED #ifndef LISTQUEUE_H_INCLUDED #define LISTQUEUE_H_INCLUDED template <class Item> class Queue { private: struct node{ Item item; node *next; node(Item x) : item(x), next(0) {} }; typedef node *link; link head, tail; // enqueue to the tail, dequeue from the head public: Queue(); ~Queue(); bool isEmpty() const; void enqueue(Item); // push item into the queue Item dequeue(); // retrieve item back from the queue }; template <class Item> Queue<Item>::Queue() { head = 0; tail = 0; } template <class Item> Queue<Item>::~Queue() { delete head; } template <class Item> bool Queue<Item>::isEmpty() const { return head == 0; } template <class Item> void Queue<Item>::enqueue(Item x) { link t = tail; tail = new node(x); if (head == 0) head = tail; else t->next = tail; } template <class Item> Item Queue<Item>::dequeue() { Item v = head->item; link t = head->next; delete head; head = t; return v; } #endif // LISTQUEUE_H_INCLUDED 2. Implementation (Graph.cpp) /* Represent graphs by adjacency list without dummy head node. */ #include"Graph.h" #include"listQueue.h" #include<iostream> using namespace std; Graph::Graph(int N) { countV = N; adjList = new vtx[countV]; for (int i = 0; i < N; ++i){ adjList[i] = new adjListNode(i, 0); } } Graph::~Graph() { for (int i = 0; i < countV; ++i) delete[] adjList[i]; delete[] adjList; } void Graph::addEdge(int x, int y) { if (x >= 0 && x < countV && y >= 0 && y < countV){ adjList[x] = new adjListNode(y, adjList[x]); } } bool Graph::isConnected(int x, int y) { int check = 0; if (x >= 0 && x < countV && y >= 0 && y < countV){ vtx newNode = adjList[x]; while (newNode->next != 0){ if (newNode->node == y){ check = 1; break; } else newNode = newNode->next; } } return check; } void Graph::removeEdge(int x, int y) { if (x >= 0 && x < countV && y >= 0 && y < countV){ vtx newNode1 = adjList[x], newNode2 = adjList[x]; int countLoop = 0; while (newNode1->node != y && newNode1->next != 0){ newNode2 = newNode1; newNode1 = newNode2->next; ++countLoop; } if (!countLoop){ newNode2 = newNode1->next; adjList[x] = newNode2; } else{ newNode2->next = newNode1->next; adjList[x] = newNode2; } } } void Graph::showConnected(int x) { cout << "The connection of vertex " << x << ":" << endl; vtx newNode = adjList[x]; while (newNode->next != 0){ cout << newNode->node << " -> "; newNode = newNode->next; } cout << x << endl; } void Graph::dfsUtil(int v, bool* visited) { visited[v] = true; vtx newNode1 = adjList[v]; while (newNode1->next != 0){ if (!visited[newNode1->node]){ // output the node (v, newNode1->node) cout << "(" << v << ", " << newNode1->node << ")" << endl; // recursion dfsUtil(newNode1->node, visited); } else{ newNode1 = newNode1->next; } } } void Graph::dfs(int v) { bool* visited = new bool[countV]; for (int i = 0; i < countV; ++i) visited[i] = false; dfsUtil(v, visited); } void Graph::bfs(int v) { Queue<int> q; bool* visited = new bool[countV]; for (int i = 0; i < countV; ++i) visited[i] = false; q.enqueue(v); visited[v] = true; while (!q.isEmpty()){ int temp = q.dequeue(); while (adjList[temp]->next != 0){ if (!visited[adjList[temp]->node]){ q.enqueue(adjList[temp]->node); visited[adjList[temp]->node] = true; cout << "(" << temp << ", " << adjList[temp]->node << ")" << endl; } adjList[temp] = adjList[temp]->next; } } delete[] visited; } 3. Client (main.cpp) #include<iostream> #include"Graph.h" using namespace std; int main(int argc, char* argv[]) { int V = atoi(argv[1]); Graph *g = new Graph(V); for (int i = 0; i < V; ++i){ cout << "Enter the connections of vertex " << i << ":" << endl; int j; while (cin >> j){ if (j >= 0 && j < V && j != i){ g->addEdge(i, j); } else if (j == i){ // if the input vertex is the same as the given vertex break; } else cout << "Out of range." << endl; } } for (int i = 0; i < V; ++i) g->showConnected(i); // DFS int start = 0; cout << "Enter the DFS starting node:"; cin >> start; g->dfs(start); // BFS cout << "Enter the BFS starting node:"; cin >> start; g->bfs(start); return 0; }测试用图：
执行：
Enter the connections of vertex 0: 1 0 Enter the connections of vertex 1: 0 2 3 4 1 Enter the connections of vertex 2: 1 2 Enter the connections of vertex 3: 1 4 3 Enter the connections of vertex 4: 1 3 4 The connection of vertex 0: 1 -> 0 The connection of vertex 1: 4 -> 3 -> 2 -> 0 -> 1 The connection of vertex 2: 1 -> 2 The connection of vertex 3: 4 -> 1 -> 3 The connection of vertex 4: 3 -> 1 -> 4 Enter the DFS starting node:0 (0, 1) (1, 4) (4, 3) (1, 2) Enter the BFS starting node:4 (4, 3) (4, 1) (1, 2) (1, 0)
