数据结构的上机真是太没人性了，最近一周关于图的题更是恼人。代码量600+还在其次，主要是算法这东西真的很费脑子啊。
拼了老命终于在周末两天写出来这玩意儿。写完这玩意儿我就生病了。
直接把代码贴上来吧，注释应该够详细了。
代码里包含图的邻接表写法、DFS、BFS、Prim算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、寻找回路算法。
#include<iostream>
#include<queue>
#define VISITED 1
#define UNVISITED 0
#define AFFINITY 10000
#define INFINITY 10000
using namespace std;
class UFSets{
private:
int n; //等价类中元素个数
int * root; //root[i]表示元素i所在的等价类的代表元素编号
int * next; //next[i]表示在等价类中，i的后面元素编号
int * length; //length[i]表示i所代表的等价类的元素个数
public:
UFSets(int size){ //初始size个元素的等价类
n = size;
root = new int[n];
next = new int[n];
length = new int[n];
for(int i = 0; i < n; i++){
root[i] = next[i] = i;
length[i] = 1;
}
}
int Find(int v){
return root[v];
}
void Union(int v, int u){ //合并v和u所在的等价类，将元素多的合并到元素少的等价类中
int rt;
if(root[u] == root[v])
return;
else if(length[root[v]] < length[root[u]]){ //将v并到u内，让u成为代表
rt = root[v];
length[root[u]] += length[rt];
root[rt] = root[u];
for(int j = next[rt]; j != rt; j = next[j]){
root[j] = root[u];
}
swap(next[rt], next[root[u]]);
}else{
rt = root[u];
length[root[v]] += length[rt];
root[rt] = root[v];
for(int j = next[rt]; j != rt; j = next[j]){
root[j] = root[u];
}
swap(next[rt], next[root[v]]);
}
}
};
template<class EdgeType>
class Edge{
public:
int start,end;
EdgeType weight;
Edge(){
}
Edge(int st, int en, EdgeType wei){
start = st;
end = en;
weight = wei;
}
};
template<class EdgeType>
class Graph{
public:
int vertexNum;
int edgeNum;
int *Mark;
Graph(int verticesNum){
vertexNum = verticesNum;
edgeNum = 0;
Mark = new int[vertexNum];
for(int i = 0; i < vertexNum; i++){
Mark[i] = UNVISITED;
}
}
~Graph(){
delete [] Mark;
}
int StartVertex(Edge<EdgeType> oneEdge){
return oneEdge.start;
}
int EndVertex(Edge<EdgeType> oneEdge){
return oneEdge.end;
}
bool IsEdge(Edge<EdgeType> oneEdge){
if(oneEdge.end > -1)
return true;
else
return false;
}
virtual Edge<EdgeType> FirstEdge(int oneVertex) = 0;
virtual Edge<EdgeType> NextEdge(Edge<EdgeType> oneEdge) = 0;
virtual void setEdge(int start, int end, int weight) = 0;
//virtual void delEdge(int start, int end) = 0;
};
template<class EdgeType>
class listData{
public:
int vertex;
EdgeType weight;
};
template<class Elem>
class ListNode{
public:
Elem element;
ListNode<Elem> *next;
ListNode(const Elem& elemval, ListNode<Elem> *nextVal = NULL){
element = elemval;
next = nextVal;
}
ListNode(ListNode<Elem> *nextVal = NULL){
next = nextVal;
}
};
template<class Elem>
class EdgeList{
public:
char data;
ListNode<Elem>* head;
EdgeList(){
head = new ListNode<Elem>;
}
void removeAll(){
ListNode<Elem> *tmp;
while(head != NULL){
tmp = head;
head = head->next;
delete tmp;
}
}
~EdgeList(){
removeAll();
}
};
template<class EdgeType>
class ListGraph:public Graph<EdgeType>{
public:
EdgeList<listData<EdgeType> > *graList;
ListGraph(int verticesNum):Graph<EdgeType>(verticesNum){
graList = new EdgeList<listData<EdgeType> >[verticesNum];
for(int i = 0; i < verticesNum; i++){
int start, end, weight;
ListNode<listData<EdgeType> >* temp = graList[i].head;
cout<<"请输入该顶点的数据："<<endl;
cin>>graList[i].data;
cout<<"请输入边的数据，包含end, weight。当end输入-1时结束："<<endl;
cin>>end>>weight;
if(end < 0){
graList[i].head->next = NULL;
}
while(end > -1){
setEdge(i, end, weight);
cin>>end>>weight;
}
}
}
~ListGraph(){
delete [] graList;
}
Edge<EdgeType> FirstEdge(int oneVertex){
Edge<EdgeType> tmpEdge;
tmpEdge.start = oneVertex;
ListNode<listData<EdgeType> > *temp = graList[oneVertex].head;
if(temp->next != NULL){
tmpEdge.end = temp->next->element.vertex;
tmpEdge.weight = temp->next->element.weight;
}else{
tmpEdge.end = -1;
tmpEdge.weight = -1;
}
return tmpEdge;
}
Edge<EdgeType> NextEdge(Edge<EdgeType> oneEdge){
Edge<EdgeType> tmpEdge;
tmpEdge.start = oneEdge.start;
ListNode<listData<EdgeType> > *temp = graList[oneEdge.start].head;
while(temp->next!= NULL && temp->next->element.vertex <= oneEdge.end){
temp = temp->next;
}
if(temp->next != NULL){
tmpEdge.end = temp->next->element.vertex;
tmpEdge.weight = temp->next->element.weight;
}else{
tmpEdge.end = -1;
tmpEdge.weight = -1;
}
return tmpEdge;
}
void setEdge(int start, int end, EdgeType weight){
ListNode<listData<EdgeType> > *temp = graList[start].head;
while(temp->next != NULL && temp->next->element.vertex < end){
temp = temp->next;
}
if(temp->next == NULL){
temp->next = new ListNode<listData<EdgeType> >;
temp->next->element.vertex = end;
temp->next->element.weight = weight;
temp->next->next = NULL;
this->edgeNum++;
return;
}
if(temp->next->element.vertex == end){
temp->next->element.weight = weight;
return;
}
if(temp->next->element.vertex > end){
ListNode<listData<EdgeType> > *other = temp->next;
temp->next = new ListNode<listData<EdgeType> >;
temp->next->element.vertex = end;
temp->next->element.weight = weight;
temp->next->next = other;
this->edgeNum++;
}
}
/*void delEdge(int start, int end){
ListNode<listData<EdgeType> > *temp = graList[start].end;
while(temp->next != NULL && temp->next->element.vertex < end){
temp = temp->next;
}
if(temp->next == NULL){
return;
}
if(temp->next->element.vertex == end){
ListNode<listData<EdgeType> > *other = temp->next->next;
delete temp->next;
temp->next = other;
this->edgeNum--;
}
}*/
void print(){
for(int i = 0; i < this->vertexNum; i++){
cout<<i<<graList[i].data<<endl;
ListNode<listData<EdgeType> >* temp = graList[i].head;
while(temp->next != NULL){
cout<<temp->next->element.vertex<<' '<<temp->next->element.weight<<endl;
temp = temp->next;
}
}
}
void visit(int ver){
cout<<graList[ver].data<<' ';
}
void DFS(int ver){
this->Mark[ver] = VISITED;
//cout<<graList[ver].data<<endl;
visit(ver);
for(Edge<EdgeType> e = FirstEdge(ver); this->IsEdge(e); e = NextEdge(e)){
//cout<<e.start<<' '<<e.end<<' '<<e.weight<<endl;
if(this->Mark[this->EndVertex(e)] == UNVISITED){
DFS(this->EndVertex(e));
}
}
}
void BFS(int ver){
queue<int> aQueue;
int tmp;
this->Mark[ver] = VISITED;
visit(ver);
aQueue.push(ver);
while(!aQueue.empty()){
ver = aQueue.front();
aQueue.pop();
for(Edge<EdgeType> e = FirstEdge(ver); this->IsEdge(e); e = NextEdge(e)){
tmp = this->EndVertex(e);
if(this->Mark[this->EndVertex(e)] == UNVISITED){
visit(tmp);
this->Mark[this->EndVertex(e)] = VISITED;
aQueue.push(tmp);
}
}
}
for(int i = 0; i < this->vertexNum; i++){
this->Mark[i] = UNVISITED;
}
}
Edge<EdgeType> * Prim(Graph<EdgeType>& G, int s){ //应用Prim算法从s顶点出发得到的最小生成树
int i,j;
Edge<EdgeType> *MST; //存储最小生成树的边
//各个顶点到生成树中的各个顶点的最短的边
EdgeType *nearest; //nearest[i]表示生成树中点到i点的最小边权值
int *neighbor; //neighbor[i]表示生成树中与i点最近的点编号，-1表示i点已经在生成树集合中
int n = G.vertexNum; //图的顶点个数
nearest = new EdgeType[n];
neighbor = new int[n];
MST = new Edge<EdgeType>[n-1];
for(int i = 0; i < n; i++){ //初始化neighbor数组和nearest数组
neighbor[i] = s;
nearest[i] = AFFINITY;
}
for(Edge<EdgeType> e = G.FirstEdge(s); G.IsEdge(e);e = G.NextEdge(e)){ //与s相邻接的顶点的边权值作为这些点距离生成树集合的最短边长
nearest[e.end] = e.weight;
}
neighbor[s] = -1;
for(i = 1; i < n; i++){ //i标记已经加入到生成树中的点的个数
EdgeType min = AFFINITY;
int v = -1;
for(j = 0; j < n; j++){ //确定一个顶点在生成树集合，另一个点不在生成树集合，且权值最小的边所关联的顶点
if(nearest[j] < min && neighbor[j] > -1){
min = nearest[j];
v = j;
}
//cout<<i<<": "<<nearest[j]<<endl;
}//for(j)
//cout<<"v: "<<v<<endl;
if(v >= 0){ //将v加入到生成树结合中，更新到生成树外的各个点最小权值的边信息
Edge<EdgeType> tempEdge(neighbor[v], v, nearest[v]);
neighbor[v] = -1;
MST[i] = tempEdge; //将边加入到生成树集合中
for(Edge<EdgeType> e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)){
int u = e.end;
if(neighbor[u] != -1 && nearest[u] > e.weight && e.weight > -1){ //用与v关联的边更新生成树之外顶点到生成树集合的最小边权值的边
neighbor[u] = v;
nearest[u] = e.weight;
}
}//for(e)
}//if(v >= 0)
}//for(i)
delete []neighbor;
delete []nearest;
return MST;
}
Edge<EdgeType> * Kruskal(Graph<EdgeType> & G){ //求含有n个顶点、e条边的连通图G的最小生成树
//cout<<"test0"<<endl;
int n = G.vertexNum;
//cout<<"ddd"<<endl;
UFSets set(n);
//cout<<"aaa"<<endl;
Edge<EdgeType> *MST = new Edge<EdgeType>[n-1]; //记录最小生成树的边
Edge<EdgeType> Heap[20];//最小堆
//cout<<"bbb"<<endl;
int Hcount = 0;
Edge<EdgeType> edge;
//cout<<"test1"<<endl;
for(int i = 0; i < G.vertexNum; i++){ //将图的所有边记录在数组e中
for( edge = G.FirstEdge(i); G.IsEdge(edge); edge = G.NextEdge(edge)){
//if(G.StartVertex(edge) < G.EndVertex(edge)){ //避免无向图中的边被重复考察
Heap[Hcount++] = edge;
//cout<<"edge: "<<edge.start<<' '<<edge.end<<' '<<edge.weight<<endl;
//}
}
}
//cout<<"test2"<<endl;
int edgeNum = 0;
Edge<EdgeType> min;
int minNum = 0;
//cout<<"test3"<<endl;
while(edgeNum < n-1){
int noEmpty = 0;
for(int l = 0; l < Hcount; l++){
if(Heap[l].weight > -1){
noEmpty++;
}
}
//cout<<noEmpty<<endl;
if(noEmpty){
for(int i = 0; i < Hcount; i++){
if(Heap[i].weight != -1){
min = Heap[i];
break;
}
}
for(int i = 0; i < Hcount; i++){
if(Heap[i].weight < min.weight && Heap[i].weight != -1){
min = Heap[i];
//cout<<"min: "<<min.start<<' '<<min.end<<' '<<min.weight<<endl;
minNum = i;
}
}
edge = min; //找到权重最小的未处理的边
//cout<<"edge1: "<<edge.start<<' '<<edge.end<<' '<<edge.weight<<endl;
Heap[minNum].weight = -1;
for(int i = 0; i < Hcount; i++){
if(Heap[i].weight < min.weight && Heap[i].weight != -1){
min = Heap[i];
minNum = i;
}
}
int v = edge.start;
int u = edge.end;
//cout<<"edge2: "<<edge.start<<' '<<edge.end<<' '<<edge.weight<<endl;
if(set.Find(v) != set.Find(u)){ //判断该边关联的顶点是否在一个连通分量
set.Union(v,u);
MST[edgeNum++] = edge;
//cout<<"MST: "<<MST[0].start<<' '<<MST[0].end<<' '<<MST[0].weight<<endl;
}
}else{
cout<<"不存在最小生成树"<<endl;
return NULL;
}
}
//cout<<"test4"<<endl;
return MST;
}
void Dijkstra(Graph<EdgeType> &G, int s, EdgeType D[], int Path[]){
int n = G.vertexNum;
int i, j;
//cout<<"test1"<<endl;
for(i = 0; i < n; i++){
G.Mark[i] = UNVISITED;
D[i] = INFINITY;
Path[i] = -1; //标记此时不存在从s到i的路径
}
//cout<<"test2"<<endl;
G.Mark[s] = VISITED;
D[s] = 0;
Path[s] = s;
//cout<<"test3"<<endl;
for(i = 0; i < n; i++){
//找到一条最短特殊路径，即min{D[j]|G.Mark[j]==UNVISITED,0<=j<n}
EdgeType min = INFINITY;
//cout<<"test4"<<i<<endl;
int k = 0;
for(j = 1; j < n; j++){
if(G.Mark[j] == UNVISITED && min>D[j]){
min = D[j];
k = j;
}
}
//cout<<"test5"<<endl;
G.Mark[k] = VISITED; //已确定从s到k的最短路径
for(Edge<EdgeType> e = G.FirstEdge(k); G.IsEdge(e); e = G.NextEdge(e)){ //利用k点更新到其余未访问顶点的最短特殊路径
int endVertex = e.end;
if(G.Mark[endVertex] == UNVISITED && D[endVertex] > (D[k] + e.weight)){ //更新到endVertex的最短特殊路径
D[endVertex] = D[k] + e.weight;
Path[endVertex] = k;
}
}
//cout<<"test6"<<endl;
}
}
void Floyd(Graph<EdgeType>& G,EdgeType Adj[20][20], int Path[20][20]){
int i, j, v; //i,j是计数器，v记录相应顶点
int n = G.vertexNum;
for(i = 0; i < n; i++){ //初始化D数组和Path数组
for(j = 0; j < n; j++){
if(i == j){
Adj[i][j] = 0;
Path[i][j] = i;
}else{
Adj[i][j] = INFINITY;
Path[i][j] = -1;
}
}//for(j)
}//for(i)
for(v = 0; v < n; v++){ //检查各条边，将边（v, u）的值作为Adj[v,u]的值，将v作为Path[u]的值
for(Edge<EdgeType> e = G.FirstEdge(v); G.IsEdge(e); e = G.NextEdge(e)){
Adj[v][e.end] = e.weight;
}
}
//如果两个顶点i,j间的最短路径经过顶点v，
//且有Adj[i][j]>(Adj[i][v]+Adj[v][j]，则更新Adj[i][j]，Path[i][j])
for(v = 0; v < n; v++)
for(i = 0; i < n; i++)
for(j = 0; j < n; j++){
if( Adj[i][j]>(Adj[i][v]+Adj[v][j]) ){
Adj[i][j] = Adj[i][v] + Adj[v][j]; //更新i,j之间经过的点编号不超过v的最短路径长度
Path[i][j] = v; //更新i,j之间经过的点编号不超过v的最短路径上j的前去
}
}
}
bool DFL(int ver,int arr[],int &counter){
this->Mark[ver] = VISITED;
arr[counter++] = ver;
for(Edge<EdgeType> e = FirstEdge(ver); this->IsEdge(e); e = NextEdge(e)){
if(this->Mark[this->EndVertex(e)] == VISITED){
arr[counter++] = ver;
return true;
}else if(this->Mark[this->EndVertex(e)] == UNVISITED){
DFL(this->EndVertex(e), arr, counter);
}
}
counter--;
return false;
}
void isLoop(){
for(int i = 0; i < this->vertexNum; i++){
this->Mark[i] = UNVISITED;
}
int arr[10],counter = 0;
for(int v = 0; v < this->vertexNum; v++){
if(DFL(v, arr, counter)){
cout<<endl;
for(int i = 0; i < counter; i++){
cout<<arr[i]<<' ';
}
return;
}
for(int i = 0; i < this->vertexNum; i++){
this->Mark[i] = UNVISITED;
}
counter = 0;
}
}
void deLoop(){
for(int i = 0; i < this->vertexNum; i++){
this->Mark[i] = UNVISITED;
}
int arr[10],counter = 0;
for(int v = 0; v < this->vertexNum; v++){
if(DFL(v, arr, counter)){
cout<<endl;
for(int i = 0; i < counter; i++){
cout<<arr[i]<<' ';
}
return;
}
for(int i = 0; i < this->vertexNum; i++){
this->Mark[i] = UNVISITED;
}
counter = 0;
}
}
};
int main(){
ListGraph<int> graph(4);
//graph.print();
//cout<<"----------------"<<endl;
cout<<"深度优先搜索：";
graph.DFS(0);
for(int i = 0; i < graph.vertexNum; i++){
graph.Mark[i] = UNVISITED;
}
cout<<"\n----------------"<<endl;
cout<<"广度优先搜索：";
graph.BFS(0);
cout<<"\n----------------"<<endl;
Edge<int> * MST = graph.Prim(graph, 3); //运行正常
//cout<<endl<<graph.vertexNum<<endl;
cout<<"Prim算法："<<endl;
for(int i = 1; i < graph.vertexNum; i++){
cout<<MST[i].start<<' '<<MST[i].end<<' '<<MST[i].weight<<endl;
}
cout<<"\n----------------"<<endl;
cout<<"Kruskal算法："<<endl;
MST = graph.Kruskal(graph); //运行正常
for(int i = 0; i < graph.vertexNum-1; i++){
cout<<MST[i].start<<' '<<MST[i].end<<' '<<MST[i].weight<<endl;
}
cout<<"\n----------------"<<endl;
int D[100];
int Path[100];
graph.Dijkstra(graph, 0, D, Path);
cout<<"从0到各点的最短路径长度："<<endl; //运行正常
for(int i = 0; i < graph.vertexNum; i++){
cout<<i<<":"<<D[i]<<' ';
}
cout<<"\n----------------"<<endl;
//int(**p)[2]=new (int(*[3])[2]);
int adj[20][20];
int path[20][20];
graph.Floyd(graph, adj, path);
cout<<"各顶点对之间最短路径长度："<<endl;
for(int i = 0; i < graph.vertexNum; i++){
for(int j = 0; j < graph.vertexNum; j++){
if(adj[i][j] != INFINITY)
cout<<adj[i][j]<<' ';
else{
cout<<'#'<<' ';
}
}
cout<<endl;
}
cout<<"--------------"<<endl;
cout<<"若存在回路，输出任一回路的顶点序列：";
graph.isLoop();
cout<<"\n--------------"<<endl;
return 0;
}