#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include<string>
#include <set>
#include <list>
#include <queue>
#include <vector>
#include <map>
#include <iterator>
#include <algorithm>
#include <iostream>
#define MaxVerNum 100 //The maximum number of vertices
#define VexType char //vertex data type
#define EdgeType int //Edge data type, the adjacency matrix is symmetric for an undirected graph, and if it has a value, it means the weight value, and if it is not, 1 is connected to 0 but not connected
#define INF 0x3f3f3f3f//as max
using namespace std;
const int MAXV = 110;
const int MAXE = 10010;
// edge set definition part
struct edge
{
int u, v; //The two endpoint numbers of the edge
int cost; //edge weight
}E[MAXE]; //There are at most MAXE edges
bool cmp(edge a, edge b)
{
return a. cost < b. cost;
}
//and lookup part
int father[MAXV]; //and find the array
int findFather(int x) //and query function
{
int a = x;
while (x != father[x])
{
x = father[x];
}
// path compression
while (a != father[a])
{
int z = a;
a = father[a];
father[z] = x;
}
return x;
}
// graph data structure
typedef struct Graph
{
VexType Vex[MaxVerNum];//vertex table
EdgeType Edge[MaxVerNum][MaxVerNum];//edge table
int vexnum, arcnum;//number of vertices, number of edges
}Graph;
// Dijkstra algorithm global variables
bool S[MaxVerNum]; //Vertex set
int D[MaxVerNum]; //The shortest path to each vertex
int Pr[MaxVerNum]; // record the predecessor
//Data structure used by Prim algorithm
typedef struct closedge
{
int adjvex; //The smallest edge is in the set U (the subscript of the vertex whose smallest edge is in the current subtree vertex set)
int lowcost; //weight on the smallest side
};
//Data structure used by Kruskal algorithm
//**********************************************Basic operation function ***********************************************//
//Initialization function Parameter: graph G Function: initialize the vertex table of the graph, adjacency matrix, etc.
void InitGraph(Graph & G)
{
memset(G.Vex, '#', sizeof(G.Vex));//initialize the vertex table
//Initialize edge table
for (int i = 0; i < MaxVerNum; i ++ )
for (int j = 0; j < MaxVerNum; j++ )
{
G.Edge[i][j] = INF;
if (i == j)G.Edge[i][j] = 0;//In the minimum spanning tree, consider an acyclic simple graph, so set it to 0
}
G.arcnum = G.vexnum = 0; //Initialize the number of vertices and edges
}
// Insert point function Parameters: graph G, vertex v Function: Insert vertex v in graph G, that is, change the vertex table
bool InsertNode(Graph & G, VexType v)
{
if (G.vexnum < MaxVerNum)
{
G.Vex[G.vexnum++] = v;
return true;
}
return false;
}
//Insert edge function Parameters: graph G, v and w at the two ends of a certain edge Function: add an edge between two points v and w in graph G, that is, change the adjacency matrix
bool InsertEdge(Graph & G, VexType v, VexType w, int weight)
{
int p1, p2;//v, w two subscripts
p1 = p2 = -1;//initialization
for (int i = 0; i < G.vexnum; i + + )//find vertex index
{
if (G.Vex[i] == v)p1 = i;
if (G.Vex[i] == w)p2 = i;
}
if (-1 != p1 & amp; & amp; -1 != p2)//Both points can be found in the graph
{
G.Edge[p1][p2] = G.Edge[p2][p1] = weight;//undirected graph adjacency matrix symmetry
G.arcnum++;
return true;
}
return false;
}
//judging whether there is an edge (v,w) function Parameters: graph G, v and w at the two ends of a side Function: judging whether there is an edge (v,w)
bool Adjancent(Graph G, VexType v, VexType w)
{
int p1, p2;//v, w two subscripts
p1 = p2 = -1;//initialization
for (int i = 0; i < G.vexnum; i + + )//find vertex index
{
if (G.Vex[i] == v)p1 = i;
if (G.Vex[i] == w)p2 = i;
}
if (-1 != p1 & amp; & amp; -1 != p2)//Both points can be found in the graph
{
if (G.Edge[p1][p2] == 1)//there is an edge
{
return true;
}
return false;
}
return false;
}
bool visited[MaxVerNum];//Visit mark array, used for mark when traversing
//Breadth traversal function Parameters: graph G, starting node subscript start Function: width traversal
void BFS(Graph G, int start)
{
queue<int> Q;//Auxiliary queue
cout << G.Vex[start];//access node
visited[start] = true;
Q.push(start);//enqueue
while (!Q.empty())//queue is not empty
{
int v = Q.front();//Get the front element of the queue
Q.pop();//Queue
for (int j = 0; j < G.vexnum; j ++ )//adjacent point
{
if (G.Edge[v][j] < INF & amp; & amp; !visited[j])//is an adjacent point and has not been visited
{
cout << "->";
cout << G.Vex[j];//access node
visited[j] = true;
Q.push(j);//enqueue
}
}
}//while
cout << endl;
}
//Deep traversal function (recursive form) parameters: graph G, starting node subscript start Function: depth traversal
void DFS(Graph G, int start)
{
cout << G.Vex[start];//access
visited[start] = true;
for (int j = 0; j < G.vexnum; j++ )
{
if (G.Edge[start][j] < INF & amp; & amp; !visited[j])//is an adjacent point and has not been visited
{
cout << "->";
DFS(G, j);//Recursive depth traversal
}
}
}
//Shortest path - Dijkstra algorithm Parameters: graph G, source point v
void Dijkstra(Graph G, int v)
{
//initialization
int n = G.vexnum;//n is the number of vertices in the graph
for (int i = 0; i < n; i ++ )
{
S[i] = false;
D[i] = G.Edge[v][i];
if (D[i] < INF)Pr[i] = v; //v is connected to i, v is the precursor
else Pr[i] = -1;
}
S[v] = true;
D[v] = 0;
//The initialization is over, find the shortest path, and add the S set
for (int i = 1; i < n; i ++ )
{
int min = INF;
int temp;
for (int w = 0; w < n; w ++ )
if (!S[w] & amp; & amp; D[w] < min) //A certain point temp has not been added to the s set, and it is the current shortest path
{
temp = w;
min = D[w];
}
S[temp] = true;
//Update the shortest path from the source point to other points via temp
for (int w = 0; w < n; w ++ )
if (!S[w] & amp; & amp; D[temp] + G.Edge[temp][w] < D[w])
{
D[w] = D[temp] + G.Edge[temp][w];
Pr[w] = temp;
}
}
}
// output the shortest path
void Path(Graph G, int v)
{
if (Pr[v] == -1)
return;
Path(G, Pr[v]);
cout << G.Vex[Pr[v]] << "->";
}
//********************************************** Function Realization function*****************************************//
// print the vertex table of the graph
void PrintVex(Graph G)
{
for (int i = 0; i < G.vexnum; i ++ )
{
cout << G.Vex[i] << " ";
}
cout << endl;
}
// print the edge matrix of the graph
void PrintEdge(Graph G)
{
for (int i = 0; i < G.vexnum; i ++ )
{
for (int j = 0; j < G.vexnum; j++ )
{
if (G.Edge[i][j] == INF)cout << "∞ ";
else cout << G.Edge[i][j] << " ";
}
cout << endl;
}
}
//Create graph function implementation function Parameter: graph G InsertNode Function: create graph
void CreateGraph(Graph & G)
{
VexType v, w;
int vn, an;//number of vertices, number of edges
cout << "Please enter the number of vertices:" << endl;
cin >> vn;
cout << "Please enter the number of sides:" << endl;
cin >> an;
cout << "Please enter all vertex names:" << endl;
for (int i = 0; i < vn; i ++ )
{
cin >> v;
if (InsertNode(G, v)) continue;//insert point
else {
cout << "Input error!" << endl; break;
}
}
cout << "Please enter all edges (two vertices and weights connected by each input edge):" << endl;
for (int j = 0; j < an; j ++ )
{
int weight;
cin >> v >> w >> weight;
if (InsertEdge(G, v, w, weight)) continue;//insert edge
else {
cout << "Input error!" << endl; break;
}
}
PrintVex(G);
PrintEdge(G);
}
//Breadth traversal function implementation function Parameter: graph G Function: width traversal
void BFSTraverse(Graph G)
{
for (int i = 0; i < MaxVerNum; i ++ )//initialize access tag array
{
visited[i] = false;
}
for (int i = 0; i < G.vexnum; i ++ )//traverse each connected component
{
if (!visited[i])BFS(G, i);
}
}
//Deep traversal function implementation function Parameter: graph G Function: depth traversal
void DFSTraverse(Graph G)
{
for (int i = 0; i < MaxVerNum; i ++ )//initialize access tag array
{
visited[i] = false;
}
for (int i = 0; i < G.vexnum; i ++ )//traverse each connected component
{
if (!visited[i])
{
DFS(G, i); cout << endl;
}
}
}
//Call the shortest path-Dijkstra algorithm Parameters: graph G, source point v
void Shortest_Dijkstra(Graph & G)
{
char vname;
int v = -1;
cout << "Please enter the source name:" << endl;
cin >> vname;
for (int i = 0; i < G.vexnum; i ++ )
if (G.Vex[i] == vname)v = i;
if (v == -1)
{
cout << "No input point found!" << endl;
return;
}
Dijkstra(G, v);
cout << "target point" << "\t" << "shortest path value" << "\t" << "shortest path" << endl;
for (int i = 0; i < G.vexnum; i ++ )
{
if (i != v)
{
cout << " " << G.Vex[i] << "\t" << " " << D[i] << "\t";
Path(G, i);
cout << G.Vex[i] << endl;
}
}
}
//Minimum spanning tree-Prim algorithm Parameters: graph G
void Prim(Graph G)
{
int v = 0;//initial node
closedge C[MaxVerNum];
int mincost = 0; //Record the sum of the weights of each side of the minimum spanning tree
//initialization
for (int i = 0; i < G.vexnum; i ++ )
{
C[i].adjvex = v;
C[i].lowcost = G.Edge[v][i];
}
cout << "All edges of the minimum spanning tree:" << endl;
//Initialization is complete, start G.vexnum-1 cycle
for (int i = 1; i < G.vexnum; i ++ )
{
int k;
int min = INF;
// Find the point with the smallest weight to the set U. The representative with a weight of 0 is in the set U
for (int j = 0; j < G.vexnum; j++ )
{
if (C[j].lowcost != 0 & amp; & amp; C[j].lowcost < min)
{
min = C[j].lowcost;
k = j;
}
}
//Output the selected edge and accumulate the weight
cout << "(" << G.Vex[k] << "," << G.Vex[C[k].adjvex] << ") ";
mincost + = C[k].lowcost;
//Update the smallest edge
for (int j = 0; j < G.vexnum; j++ )
{
if (C[j].lowcost != 0 & amp; & amp; G.Edge[k][j] < C[j].lowcost)
{
C[j].adjvex = k;
C[j].lowcost = G.Edge[k][j];
}
}
}
cout << "Sum of minimum spanning tree weights:" << mincost << endl;
}
//kruskal part, return the sum of the edge weights of the minimum spanning tree, the parameter n is the number of vertices, m is the number of edges of the graph
int kruskal(int n, int m)
{
//ans is the sum of the requested edge weights, and Num_Edge is the number of edges in the current spanning tree
int ans = 0, Num_Edge = 0;
for (int i = 0; i < n; i ++ ) //vertex range is [0,n-1]
{
father[i] = i; //and check set initialization
}
sort(E, E + m, cmp); //All edges are sorted by edge weight from small to large
for (int i = 0; i < m; i ++ ) //enumerate all edges
{
int faU = findFather(E[i].u); //Query the root node of the set where the two endpoints of the test edge are located
int faV = findFather(E[i].v);
if (faU != faV) //if not in a collection
{
father[faU] = faV; //Merge sets (that is, add the test edge to the minimum spanning tree)
ans + = E[i].cost; //The sum of edge weights increases the edge weight of the test edge
Num_Edge ++ ; //Increase the number of edges of the current spanning tree by 1
if (Num_Edge == n - 1)
break; //End the algorithm when the number of edges is equal to the number of vertices minus 1
}
}
if (Num_Edge != n - 1)
return -1; //Return -1 when unable to connect
else
return ans; //Return the sum of edge weights of the minimum spanning tree
}
//Minimum Spanning Tree-Kruskal Algorithm (Kruskal) Parameters: Figure
void Kruskal01() {
cout << "Welcome to Kruskal Algorithm" << endl;
int n, m;
cout << "Please enter the number of vertices and edges" << endl;
scanf_s("%d%d", & amp;n, & amp;m); //number of vertices, number of edges
for (int i = 0; i < m; i ++ )
{
cout << "Please enter the weight of the first" << i + 1 << "edge" << endl;
scanf_s("%d%d%d", & amp;E[i].u, & amp;E[i].v, & amp;E[i].cost); //Two endpoint numbers, sides right
}
int ans = kruskal(n, m); //kruskal algorithm entry
printf_s("The shortest path is: %d\
", ans);
}
//Shortest path problem - Floyd's algorithm
void Floyd() {
cout << "Welcome to Floyd's Algorithm!" << endl;
int a[21][21], m, n, i, j, w;
for (int i = 1; i <= 20; i ++ ) {
for (int j = 1; j <= 20; j ++ ) {
if (i == j) { a[i][j] = 0; }
else a[i][j] = INF;
}
}
cin >> n >> m;
cout << "The number of vertices and edges has been entered" << endl;
for (int k = 1; k <= m; k ++ ) {
cin >> i >> j >> w;
a[i][j] = w;
a[j][i] = w;
}
for (int p = 1; p <= n; p ++ ) {
for (int i = 1; i <= n; i ++ ) {
if (a[i][p] == INF) continue;
for (int j = 1; j <= n; j ++ ) {
if (i == j)continue;
a[i][j] = min(a[i][j], a[i][p] + a[p][j]);
}
}
}
for (int i = 1; i <= n; i ++ ) {
for (int j = 1; j <= n; j ++ ) {
cout << a[i][j] << " ";
}
cout << endl;
}
}
//menu
void menu()
{
cout << "************1. Create graph 2. Breadth traversal *******************" << endl;
cout << "************3. Depth Traversal 4. Shortest Path (Dijkstra)****************" << endl;
cout << "************5. Minimum spanning tree (Prim) 6. Minimum spanning tree (Kruskal) *****************" < < endl;
cout << "************7. Shortest path (Floyd) 8. Exit program *****************" << endl;
// cout << "9. Exit the program *****************" << endl;
}
//main function
int main()
{
int choice = 0;
Graph G;
InitGraph(G);
while (1)
{
menu();
printf("Please enter the menu number:\
");
scanf_s("%d", &choice);
if (8 == choice) break;
switch (choice)
{
case 1:CreateGraph(G); break;
case 2: BF Traverse(G); break;
case 3:DFSTraverse(G); break;
//case 4:Shortest_Dijkstra(G); break;
case 4: Dijkstra(G,2); break;
case 5: Prim(G); break;
case 6: Kruskal01(); break;
case 7: Floyd(); break;
case 8: break;
default:printf("Input error!!!\
"); break;
}
}
return 0;
}