数据结构之图（6）

一、概念

图G有顶点集V和边集E组成，记为G=(V,E),其中V（G）表示图G中顶点的有限非空集；

E(G)表示图G中顶点之间的关系（边）集合。

若V={v1,v2,…，vn}，则用|V|表示图G中顶点的个数。也称为图G的阶，

E={（u,v)|u ∈V},用|E|表示图G中边的条数

图不可以是空，V一定是非空集

无向图

E是无向边（简称边）的有限集合

有向图

E是有向边（弧）的有限集合

弧是顶点的有序对，记为<v,w>,

v为弧尾，w为弧头

简单图

不存在重复边

不存在顶点到自身的边

多重图

某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联

顶点的度、入度、出度

无向图：TD(v)

$\sum_{i=1}^{n}TD(v_i)=2e$

有向图：入度：ID（v) 出度：OD（v) TD(v)=ID(v)+OD（v)

$\sum_{i=1}^{n}ID(v_i)=\sum_{i=1}^{n}OD(v_i)=e$

顶点—顶点的关系描述

路径

回路

简单路径—顶点不重复出现

简单回路—除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

路径长度

点到点的距离

从顶点u出发到顶点w有路径存在，则此路径的长度称为从u到v的距离

若不存在路径，则为∞

连通

无向图v到w存在路径，v和w连通

强连通

y有向图，v到w和w到v都有路径

子图

V’是V的子集，E‘是E的子集

生成子图：若有满足V（G’）=V（G）的子图G‘

连通分量

无向图中的极大连通子图(子图必须连通，且包含尽可能多的顶点和边）

强连通分量

有向图

生成树

连通图的生成树是包含图中全部顶点的一个极小连通图

若图中顶点数为n，则它的生成树含有n-1条边

对于生成树而言，砍去它的一条边，则会变成非连通图，加上一条边则会形成一个回路

边尽可能的少，但要保持连通

边的权、带权图/网

几种特殊形态的图

无向完全图：

无向图任意两个顶点之间都存在边

若无向图的顶点数|V|=n,则|E|[0, $\binom{n}{2}$ ]=[0,n(n-1)/2]

有向完全图:

有向图中任意两个顶点之间都存在方向相反的两条弧

若有向图的顶点数|V|=n,则|E|[0,2 $\binom{n}{2}$ ]=[0,n(n-1)]

稀疏图

稠密图

树——不存在回路，且连通的无向图

n个顶点的树，必有n-1条边

考点：n个顶点的图，若|E|>n-1,则一定有回路

有向树

一个顶点的入度为0、其余顶点的入度为1的有向图

二、图的结构

Graph.h

#define DefaultVertices 50
template <class T>
class Graph {
protected:int maxVertices;int numEdges;int numVertices;public:Graph(int sz = DefaultVertices) :maxVertices(sz), numEdges(0), numVertices(0) {}~Graph() {}bool GraphEmpty() {if (numEdges == 0) return true;else return false;}bool GraphFull() {if (numVertices == maxVertices || numEdges == maxVertices * (maxVertices - 1) / 2) return true;else return false;}int NumberOfVertices() { return numVertices; }int NumberOfEdges() { return numEdges; }virtual T getValue(int i) = 0;virtual int getVertexPos(T vertex) = 0;virtual int getFirstNeighbor(int v) = 0;virtual int getNextNeighbor(int v, int w) = 0;virtual int getWeight(int v1, int v2) = 0;virtual bool insertVertex(T& vertex) = 0;virtual bool insertEdge(int v1, int v2, int choice) = 0;virtual bool removeVertex(int v) = 0;virtual bool removeEdge(int v1, int v2) = 0;
};

三、邻接矩阵法

Graphmtx.h

1、定义图的结构

template <class T>
class Graphmtx :public Graph<T> {
private:T* VerticesList;int** Edge;public:Graphmtx(int sz = DefaultVertices);~Graphmtx() {delete[] VerticesList;delete[] Edge;}T getValue(int i) {return i >= 0 && i <= this->numVertices ? VerticesList[i] : NULL;}int getVertexPos(T vertex) {for (int i = 0; i < this->numVertices; i++) {if (VerticesList[i] == vertex) return i;}return -1;}int getWeight(int v1, int v2) {return v1 != -1 && v2 != -1 ? Edge[v1][v2] : 0;}int getFirstNeighbor(int v);int getNextNeighbor(int v, int w);bool insertVertex(T& vertex);bool insertEdge(int v1, int v2, int choice);bool removeVertex(int v);bool removeEdge(int v1, int v2);
};

2、创建图

template <class T>
Graphmtx<T>::Graphmtx(int sz) :Graph<T>(sz) {int i, j;VerticesList = new T[this->maxVertices];Edge = (int**)new int*[this->maxVertices];for (i = 0; i < this->maxVertices; i++) {Edge[i] = new int[this->maxVertices];}for (i = 0; i < this->maxVertices; i++) {for (j = 0; j < this->maxVertices; j++) {Edge[i][j] = 0;}}
}

3、添加点和边

template <class T>
bool Graphmtx<T>::insertVertex(T& vertex) {if (this->numVertices == this->maxVertices) return false;VerticesList[this->numVertices++] = vertex;return true;
}template <class T>
bool Graphmtx<T>::insertEdge(int v1, int v2, int choice) {if (v1 > -1 && v1<this->numVertices && v2>-1 && v2 < this->numVertices && Edge[v1][v2] == 0) {Edge[v1][v2] = 1;if (!choice) {Edge[v2][v1] = 1;}this->numEdges++;return true;}else return false;
}

4、删除

template <class T>
bool Graphmtx<T>::removeVertex(int v) {if (v<0 || v>this->numVertices) return false;if (this->numVertices == 1) return false;int i, j;VerticesList[v] = VerticesList[this->numVertices - 1];for (i = 0; i < this->numVertices; i++) {if (Edge[i][v] == 1) this->numEdges--;}for (i = 0; i < this->numVertices; i++) {Edge[i][v] = Edge[i][this->numVertices - 1];}this->numVertices--;for (j = 0; j < this->numVertices; j++) {Edge[v][j] = Edge[this->numVertices][j];}return true;
}template <class T>
bool Graphmtx<T>::removeEdge(int v1, int v2) {if (v1 > -1 && v1<this->numVertices && v2>-1 && v2 < this->numVertices && Edge[v1][v2] == 1) {Edge[v1][v2] = Edge[v2][v1] = 0;this->numEdges--;return true;}else return false;
}

5、获取值

template <class T>
int Graphmtx<T>::getFirstNeighbor(int v) {if (v != -1) {for (int col = 0; col < this->numVertices; col++) {if (Edge[v][col] == 1)return col;}}return -1;
}template <class T>
int Graphmtx<T>::getNextNeighbor(int v, int w) {if (v != -1 && w != -1) {for (int col = w + 1; col < this->numVertices; col++) {if (Edge[v][col] == 1)return col;}}return -1;
}

四、邻接表法

Graphlnk.h

1、定义图的结构

#include "graph.h"
template<class T>
struct Edge {int dest;//目标顶点int cost;//边的权重Edge<T>* link;//指向下一条边的指针Edge(){}Edge(int num,int weight):dest(num),cost(weight),link(NULL){}bool operator != (Edge<T>& R)const {//基于目标顶点比较两个Edge对象是否不同return (dest != R.dest) ? true : false;}
};template<class T>
struct Vertex {T data;Edge<T>* adj;//指向顶点的第一条边
};

template <class T>
class Graphlnk :public Graph<T> {
private:Vertex<T>* NodeTable;public:Graphlnk(int sz = DefaultVertices);~Graphlnk();T getValue(int i) {return (i >= 0 && i < this->numVertices) ? NodeTable[i].data : 0;}int getVertexPos(T vertex) {for (int i = 0; i < this->numVertices; i++) {if (NodeTable[i].data == vertex) return i;}return -1;}int getFirstNeighbor(int v);int getNextNeighbor(int v, int w);int getWeight(int v1, int v2);bool insertVertex(T& vertex);bool insertEdge(int v1, int v2, int choice);bool removeVertex(int v);bool removeEdge(int v1, int v2);
};

2、创建和销毁图

template <class T>
Graphlnk<T>::Graphlnk(int sz) :Graph<T>(sz) {NodeTable = new Vertex<T>[this->maxVertices];if (NodeTable == NULL) {cerr << "存储分配错误" << endl; exit(1);}for (int i = 0; i < this->maxVertices; i++) {NodeTable[i].adj = NULL;}
}template <class T>
Graphlnk<T>::~Graphlnk() {for (int i = 0; i < this->numVertices; i++) {Edge<T>* p = NodeTable[i].adj;while (p != NULL) {NodeTable[i].adj = p->link;delete p;p = NodeTable[i].adj;}}delete[] NodeTable;
}

3、添加点和边

template <class T>
bool Graphlnk<T>::insertVertex(T& vertex) {if (this->numVertices == this->maxVertices) return false;NodeTable[this->numVertices].data = vertex;this->numVertices++;return true;
}template <class T>
bool Graphlnk<T>::insertEdge(int v1, int v2, int choice) {//choice 是否创建有向边if (v1 >= 0 && v1 < this->numVertices && v2 >= 0 && v2 < this->numVertices) {Edge<T>* q, * p = NodeTable[v1].adj;while (p != NULL && p->dest != v2) p = p->link;//找到从顶点v1出发的最后一条边if (p != NULL) return false;p = new Edge<T>;p->dest = v2;p->cost = 1;p->link = NodeTable[v1].adj;NodeTable[v1].adj = p;q = new Edge<T>;if (!choice) {q->dest = v1;q->cost = 1;q->link = NodeTable[v2].adj;NodeTable[v2].adj = q;}this->numEdges++;return true;}return false;
}

4、删除

template <class T>
bool Graphlnk<T>::removeVertex(int v) {if (this->numVertices == 1 || v < 0 || v >= this->numVertices) return false;Edge<T>* p, * s, * t;int k;while (NodeTable[v].adj != NULL) {p = NodeTable[v].adj;k = p->dest;s = NodeTable[k].adj;t = NULL;while (s != NULL && s->dest != v) {t = s;s = s->link;}if (s != NULL) {if (t == NULL) NodeTable[k].adj = s->link;else t->link = s->link;delete s;}NodeTable[v].adj = p->link;delete p;this->numEdges--;}this->numVertices--;NodeTable[v].data = NodeTable[this->numVertices].data;p = NodeTable[v].adj = NodeTable[this->numVertices].adj;while (p != NULL) {s = NodeTable[p->dest].adj;while (s != NULL) {if (s->dest == this->numVertices) {s->dest = v; break;}else {s = s->link;}}}return true;
}template <class T>
bool Graphlnk<T>::removeEdge(int v1, int v2) {if (v1 != -1 && v2 != -1) {Edge<T>* p = NodeTable[v1].adj, * q = NULL, * s = p;while (p != NULL && p->dest != v2) {q = p;p = p->link;}if (p != NULL) {if (p == s) NodeTable[v1].adj = p->link;else q->link = p->link;delete p;}else return false;p = NodeTable[v2].adj;q = NULL;s = p;while (p->dest != v1) {q = p;p = p->link;}if (p == s) NodeTable[v2].adj = p->link;else q->link = p->link;delete p;return true;}return false;
}

5、获取值

template <class T>
int Graphlnk<T>::getFirstNeighbor(int v) {if (v != -1) {Edge<T>* p = NodeTable[v].adj;if (p != NULL) return p->dest;}return -1;
}template <class T>
int Graphlnk<T>::getNextNeighbor(int v, int w) {if (v != -1) {Edge<T>* p = NodeTable[v].adj;while (p != NULL && p->dest != w) p = p->link;if (p != NULL && p->link != NULL) return p->link->dest;}return -1;
}template <class T>
int Graphlnk<T>::getWeight(int v1, int v2) {if (v1 != -1 && v2 != -1) {Edge<T>* p = NodeTable[v1].adj;while (p != NULL && p->dest != v2) p = p->link;if (p != NULL) return p->cost;}return 0;
}

五、搜索

1、深度优先搜索

//深度优先遍历
template <class T>
void DFS(Graph<T>& G, const T& v) {int i, loc, n = G.NumberOfVertices();bool* visited = new bool[n];for (i = 0; i < n; i++) {visited[i] = false;}loc = G.getVertexPos(v);//找到结点的索引DFS(G, loc, visited);cout << endl;delete[] visited;
}
template <class T>
void DFS(Graph<T>& G, int v, bool visited[]) {cout << G.getValue(v) << " ";	//访问顶点visited[v] = true;int w = G.getFirstNeighbor(v);//第一个点while (w != -1) {if (visited[w] == false) DFS(G, w, visited);w = G.getNextNeighbor(v, w);//接下来的点}
}

2、广度优先搜索

template <class T>
void BFS(Graph<T>& G, const T& v)
{int i, w, n = G.NumberOfVertices();bool* visited = new bool[n];for (i = 0; i < n; i++) {visited[i] = false;}int loc = G.getVertexPos(v);//找到结点的索引cout << G.getValue(loc) << " ";visited[loc] = true;queue<int>Q;Q.push(loc);while (!Q.empty()){loc = Q.front();Q.pop();w = G.getFirstNeighbor(loc);while (w != -1){if (visited[w] == false) {cout << G.getValue(w) << " ";visited[w] = true;Q.push(w);}w = G.getNextNeighbor(loc, w);}}cout << endl;delete[] visited;
}