#include<iostream>
#include<string>
using namespace std;struct Graph {int** data;int vertex_num;//顶点数量int edge_num;//边数
};//基于邻接矩阵表示的有向带权图的建立算法void CreateGraph(Graph &g) {int n, first, second;cout << "请输入边的数量";cin >> g.edge_num;cout << "请输入dingdian的数量";cin >> g.vertex_num;g.data = new int* [g.vertex_num];for (n = 0; n < g.vertex_num; n++)g.data[n] = new int[g.vertex_num];for (first = 0; first < g.vertex_num; first++)for (second = 0; second < g.vertex_num; second++)g.data[first][second] = INFINITY;for ( n = 0; n < g.edge_num; n++){cout << "请输入第" << n + 1 << "条弧的弧头顶点的序号";cin >> first;cout << "请输入第" << n + 1 << "条弧的弧尾顶点的序号";cin >> second;cout << "请输入权";cin >> g.data[first][second];}
}//邻接表的实现typedef int InfoType;struct AdjNode {int another_vertex;//该条边另一个顶点在表头节点数组中的下标InfoType info;//AdjNode* next;//下一个节点地址
};typedef int EType;struct AdjList {EType data;AdjNode* head;
};struct AdjGraph {AdjList * head_list;int vertex_num;//顶点数量int edge_num;//边数
};//基于邻接表表示的图的建立算法void CreateGraph(AdjGraph &g) {int n, first, second, weight;AdjNode* p;cout << "请输入边的数量";cin >> g.edge_num;cout << "请输入dingdian的数量";cin >> g.vertex_num;g.head_list = new AdjList[g.vertex_num];for (n = 0; n < g.vertex_num; n++)g.head_list[n].head = NULL;for (n = 0; n < g.edge_num; n++){cout << "请输入第" << n + 1 << "条弧的弧头顶点的序号";cin >> first;cout << "请输入第" << n + 1 << "条弧的弧尾顶点的序号";cin >> second;cout << "请输入权";cin >> weight;p = new AdjNode;p->info = weight;p->another_vertex = second;p->next = g.head_list[first].head;g.head_list[first].head = p;}
}//有向图的十字链表结构
#define MAX_VERTEX_NUM 20struct ArcBox
{int tailvex, headvex;//该弧的尾和头节点的位置struct ArcBox* hlink, * tlink;//分别为弧头相同和弧尾相同的弧的链接域InfoType info;
};typedef char VertexType;
struct VexNode {VertexType vertex;ArcBox fisrin, firstout;//分别指向该顶点第一条入弧和出弧
};struct OLGraph {VexNode xlist[MAX_VERTEX_NUM];//表头向量int vexnum, //有向图的定点数arcnum; //有向图的弧数
};#define MAX_VERTEX_NUM 20
typedef enum{ unvisited,visited
}VisitIf;struct EBox {VisitIf mark; //访问标记int ivex, jvex;//该边衣服的两个顶点的位置EBox *ilink;//分别指向依附这两顶点的下一条边EBox *jlink;InfoType info;
};struct VexBox {VertexType data;EBox fistedge;//指向第一条依附该顶点的边
};struct AMLGraph {VexBox adjmulist[MAX_VERTEX_NUM];int vexnu, edgenum;//无向图的当前顶点数和边数
};//深度优先搜索的递归实现算法
//基于邻接表表示的有向图的深度优先搜索递归算法
void DFS(AdjGraph g, int v, int* visited) {AdjNode* w;visited[v] = 1;cout << v << "->";for (w = g.head_list[v].head; w; w = w->next) {if (!visited[w->another_vertex])DFS(g,w->another_vertex,visited);}
}void DFSTrans(AdjGraph g) {int *visited, i;visited = new int[g.vertex_num];memset(visited, 0, sizeof(int) * g.vertex_num);for (i = 0; i < g.vertex_num; i++) {if (!visited[i]) {DFS(g, i, visited);}}delete[]visited;
}//基于邻接表表示的有向图的深度优先搜索非递归算法
//算法复杂度为O(n^2)
void DFS(AdjGraph g, int v, int* visited) {int stack[1000];int top;//栈顶指针int i;AdjNode* pt;cout << v << "->";top = 0;visited[v] = 1;//已经访问标志stack[top] = v;//栈顶元素while (top >= 0) {pt = g.head_list[stack[top]].head;//访问元素的头部while ((pt != NULL) && visited[pt->another_vertex])pt = pt->next;//找到一个未被访问的邻接顶点if (!pt)top--;//没有找到,返回到前一次访问过的顶点else {i = pt->another_vertex;//进行访问cout << i << "->";visited[i] = 1;//访问完成标志top++;stack[top] = i;}}
}void DFSTrans(AdjGraph g) {int* visited, i;visited = new int[g.vertex_num];memset(visited, 0, sizeof(int) * g.vertex_num);for (i = 0; i < g.vertex_num; i++) {if (!visited[i]) {DFS(g, i, visited);}}delete[]visited;
}//基于邻接表表示的有向图的宽度优先搜索非递归算法
#define MAXIMUM 1000
void BFS(AdjGraph g, int v, int* visited) {int queue[MAXIMUM];int head, tail, t; AdjNode* p;head = 0;tail = 0;cout << v << "->";visited[v] = 1;queue[head] = v;while (head<=tail) {p = g.head_list[queue[head]].head;//从队首取顶点while (!p) {t = p->another_vertex;if (!visited[t]) {cout << t << "->";visited[t] = 1;tail++;queue[tail] = t;//入队}p = p->next;}//出队head++;}}void DFSTrans(AdjGraph g) {int* visited, i;visited = new int[g.vertex_num];memset(visited, 0, sizeof(int) * g.vertex_num);for (i = 0; i < g.vertex_num; i++) {if (!visited[i]) {DFS(g, i, visited);}}delete[]visited;
}//无向图的连通性
void DFSTrans(AdjGraph g) {int* visited, i;int count = 0;//计数变量visited = new int[g.vertex_num];memset(visited, 0, sizeof(int) * g.vertex_num);for (i = 0; i < g.vertex_num; i++) {if (!visited[i]) {count++;//每调用一次dfs,count+1DFS(g, i, visited);}}delete[]visited;
}//基于邻接矩阵表示的图的prim算法实现——连通网络的最小代价生成树
//时间复杂度O(n^3)
void Prim(Graph g, int v)
{int* flag;int i, m, n, min, temp_m, temp_n;memset(flag, 0, sizeof(int) * g.vertex_num);flag[v] = 1;//把顶点v放入集合Ufor (i = 0; i < g.vertex_num; i++) {min = INFINITY;for (m = 0; m < g.vertex_num; m++) {for (n = 0; n < g.vertex_num; n++) {if ((flag[m] + flag[n]) == 1 &&g.data[m][n] < min) {//(flag[m]+flag[n])==1表示连个顶点只有一个在集合U中min = g.data[m][n];temp_m = m;temp_n = n;}}}cout << temp_m << "-" << temp_m << endl;g.data[temp_m][temp_n] = INFINITY;//不考虑此边flag[temp_m] = 1;flag[temp_n] = 1;}delete[]flag;
}//基于邻接矩阵表示的图的kruakal算法实现——连通网络的最小代价生成树void Kruskal(Graph g, int v) {int* set_number;int i, j, m, n, min, temp_m, temp_n;set_number = new int[g.vertex_num];for (i = 0; i < g.vertex_num; i++)set_number[i] = i;//设置联通分量号for (i = 0; i < g.vertex_num; i++) {min = INFINITY;for (m = 0; m < g.vertex_num; m++) {for (n = 0; n < g.vertex_num; n++) {if ((set_number[m] != set_number[n]) &&g.data[m][n] < min) {min = g.data[m][n];temp_m = m;temp_n = n;}}}cout << temp_m << "-" << temp_m << endl;g.data[temp_m][temp_n] = INFINITY;//不考虑此边for (j = 0; j < g.vertex_num; j++) {if (set_number[j] == set_number[temp_n])set_number[j] == set_number[temp_m];}}delete[]set_number;
}//单源最短路径
void Dijkstra(Graph g, int v) {int* dist;//顶点v到各顶点的当前最短距离int* S;char** path, temp[20];int i, j, k, min;dist = new int[g.vertex_num];S = new int[g.vertex_num];path = new char* [g.vertex_num];for (i = 0; i < g.vertex_num; i++)path[i] = new char[100];for (i = 0; i < g.vertex_num; i++) {//初始化dist[i] = g.data[v][i];//v到i是路劲长短if (dist[i] < INFINITY)sprintf(path[i], "%d->%d", v, i);elsestrcpy(path[i], "");S[i] = 0;}S[v] = 1;//把源点放入集合S中for (i = 1; i < g.vertex_num; i++) {min = INFINITY;j = 0;for (k = 0; k < g.vertex_num; k++) {//在V—S中找到dist[]值最小的顶点if (!S[k] && dist[k] < min) {//S[k]不为零,且dist[k]小于最小值min = dist[k];//最小值就是dist[k]j = k;}}S[j] = 1;//把找到的顶点放入S集合中for (k = 0; k < g.vertex_num; k++) {//修改V—S各顶点的dist[]值if (!S[k] && dist[j]+g.data[j][k] < dist[k]) {//S[k]不为零,且dist[j]+g.data[j][k]小于dist[k]dist[k] = dist[j] + g.data[j][k];sprintf(temp, "->%d", k);strcpy(path[k],path[j]);strcpy(path[k],temp);}} } for (i = 1; i < g.vertex_num; i++) {cout << dist[i] << " " << path[i] << endl;}delete[]dist;delete[]S;for (i = 1; i < g.vertex_num; i++) {delete[]path[i];}delete[]path;
}//任意两顶点之间的路径
//时间复杂度O(n^3)
void AllShortPath(Graph g) {int** m;char*** path;int n, i, j, k;m = new int*[g.vertex_num];path = new char** [g.vertex_num];for (n = 0; n < g.vertex_num; n++) {m[n] = new int[g.vertex_num];path[n]= new char* [g.vertex_num];for (i = 0; i < g.vertex_num; i++) {path[n][i] = new char [100];}}for (i = 0; i < g.vertex_num; i++) {for ( j= 0; j < g.vertex_num; j++) {m[i][j] = g.data[i][j];if (i != j && m[i][n] < INFINITY) {sprintf(path[i][j], "%d->%d", i, j);}else {path[i][j][0] = 0;}}}for (k = 0; k < g.vertex_num; k++) {for (i = 0; i < g.vertex_num; i++) {for (j = 0; j < g.vertex_num; j++) {if (i != j && m[i][k] + m[k][j] < m[i][j]) {m[i][j] = m[i][k] + m[k][j];strcpy(path[i][j], path[i][k]);strcpy(path[i][j], ",");strcpy(path[i][j], path[k][j]);}}}}for (i = 0; i < g.vertex_num; i++) {for (j = 0; j < g.vertex_num; j++) {printf(" %d",m[i][j]);}cout << endl;}for (i = 0; i < g.vertex_num; i++) {for (j = 0; j < g.vertex_num; j++) {printf(" %s", path[i][j]);}cout << endl;}for (i = 0; i < g.vertex_num; i++)for (j = 0; j < g.vertex_num; j++)delete[]path[i][j];for (i = 0; i < g.vertex_num; i++) {delete []m[i];delete[]path[i];}delete[]m;delete[]path;
}
详细解决方案
深入理解数据结构——图
热度:8 发布时间:2024-01-17 05:08:11.0
相关解决方案
- 算法效率(数据结构),该如何解决
- 数据结构,很无力~该怎么处理
- 数据结构,该怎么处理
- java 数据结构,该如何解决
- 数据库 数据结构 关于索引解决办法
- 数据结构,离散数学什么的重要吗。该怎么解决
- 数据结构 - 线性表学习(php模拟)
- 【数据结构】【归并排序】
- 数据结构 05——树与二叉树
- 数据结构——01数据结构绪论
- 数据结构——02算法简介
- 《数据结构(C语言版)》课程学习(15)——实验项目名称:矩阵的转置
- 数据结构--连续内存分配的实现
- n叉树 数据结构
- 链表 数据结构
- Hash表 数据结构
- 数据结构——红黑数学习
- c(数据结构)下树的创建的非递归算法
- 数据结构-时间复杂度大O排名
- 数据结构---顺序表
- 数据结构----顺序栈
- 【数据结构】#数据结构复习提纲
- 数据结构 递归遍历二叉树 C/C++
- 数据结构 C/C++ 冒泡排序
- 数据结构 C/C++ 关键路径
- 数据结构 C/C++ 链栈
- 数据结构 C/C++ 链式队列
- 数据结构 C/C++ 对角矩阵
- 数据结构 C/C++ 对称矩阵
- C/C++ 数据结构 单链表