29 adjacency table: adding a vertex
Author: fengxiangyang time limit: 1S chapter: DS: figure
Deadline: June 30, 2022 23:55:00
Problem Description:
Objective: to use C++ template to design and gradually improve adjacency table abstract data type (ADT) of graph.
Contents: (1) please refer to the adjacency matrix template prototype of the graph to design and gradually improve the adjacency table ADT of the graph. (since the environment currently only supports single file compilation, all contents are concentrated in one source file. In the actual design, it is recommended to put the abstract class and the corresponding derived class in a separate header file.)
(2) Design and implement an algorithm to add a vertex to the existing graph. The storage structure of the graph adopts adjacency table. The bit order of the added vertices is at the end of the vertex set. Add it to the ADT.
Note: DG (directed graph), DN (directed network), UDG (undirected graph), UDN (undirected network)
Reference function prototype:
//Add a vertex to G
template<class TypeOfVer, class TypeOfEdge>
bool adjlist_graph<TypeOfVer, TypeOfEdge>::InsertVer(const TypeOfVer &data);
The reference of the adjacency table template class prototype of figure is as follows:
/*Node definition of edge table*/
template<class TypeOfEdge>
struct edgeNode
{
int data;
TypeOfEdge weight;
edgeNode<TypeOfEdge> *next;
Edgenode (const int &d, edgenode<typeofedge> *ptr = null) / / constructor, used to construct other nodes (unauthorized graph)
/ / formal parameters in the function parameter table are allowed to have default values, but parameters with default values need to be put later
{
next = ptr;
data = d;
}
Edgenode (const int &d, const typeofedge &w, edgenode<typeofedge> *ptr = null) / / constructor, used to construct other nodes (weighted graph)
/ / formal parameters in the function parameter table are allowed to have default values, but parameters with default values need to be put later
{
next = ptr;
data = d;
weight = w;
}
int getData(){ return data;} / / get the node sequence number (vertex set)
TypeOfEdge getWeight(){ return weight;} / / obtain the weight of the corresponding edge in the edge set
void SetLink( edgeNode<TypeOfEdge> *link ){ next = link; } / / modify the next field of the node
void SetData( int value ){ data = value; } / / modify the node sequence number (vertex set)
void SetWeight(TypeOfEdge value ){ weight = value; } / / modify the weight of the corresponding edge in the edge set
};
//Adjacency table classes of Graphs
template<class TypeOfVer, class TypeOfEdge>
struct verNode
{
TypeOfVer ver;
edgeNode<TypeOfEdge> *head;
verNode(edgeNode<TypeOfEdge> *h = NULL){head = h;}
TypeOfVer getVer(){ return ver;} / / get the node value (vertex set)
edgeNode<TypeOfEdge> *getHead(){ return head;} / / get the header pointer of the corresponding side table
void setVer(TypeOfVer value){ ver = value;} / / set node value (vertex set)
void setHead(edgeNode<TypeOfEdge> *value){ head = value;} / / set the header pointer of the corresponding side table
};
template <class TypeOfVer, class TypeOfEdge>
class adjlist_graph{
private:
int Vers; / / number of vertices
int Edges; / / number of sides
verNode<TypeOfVer,TypeOfEdge> *verList;
string GraphKind; / / category mark of the graph
bool Delete_Edge( int u, int v );
bool DFS(int u, int &num, int visited[]); // DFS traversal (recursive part)
public:
adjlist_ graph( const string &kd, int vSize, const TypeOfVer d[]); // Constructor constructs a graph with only nodes and no edges.
adjlist_ graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e); Constructor to construct an unauthorized graph. Meanings of the five parameters: graph type, node number, edge number, node set and edge set
adjlist_ graph( const string &kd, int vSize, int eSize, const TypeOfVer d[], int **e, const TypeOfEdge w[]); // Constructor constructs a weighted graph.
bool GraphisEmpty() { return Vers == 0; } / / judge whether the image is empty
string GetGraphKind(){ return GraphKind; }
bool GetVer(int u, TypeOfVer &data); // Gets the value of the specified vertex in G
int GetFirstAdjVex(int u, int &v); // Returns the bit order (vertex set) of the first adjacent vertex of the specified vertex u in G. Returns -1 if the vertex does not have an adjacent vertex in G
int GetNextAdjVex(int u, int v, int &w); // Returns the bit order (vertex set) of the next adjacent vertex (relative to V) of the specified vertex u in G. Returns false if the vertex does not have an adjacent vertex in G
bool PutVer(int u, TypeOfVer data); // Assign a value to the specified vertex in G
bool InsertVer(const TypeOfVer &data); // Add a vertex to G
int LocateVer(TypeOfVer data); // Returns the position of the specified vertex in G
bool ExistEdge(int u, int v);
bool PrintVer(); / / output vertex set
bool PrintAdjList(); / / output adjacency matrix
int GetVerNum(){ return Vers;} / / get the current number of vertices
int GetEdgeNum(){ return Edges;} / / get the current number of edges
bool Insert_Edge(int u, int v); // No authority graph inserts an edge
bool Insert_Edge(int u, int v, TypeOfEdge w); // Right graph inserts an edge
bool DeleteVer(const TypeOfVer &data); // Delete a vertex in G
bool DeleteEdge( int u, int v ); // Delete edges (shell: directed (delete 1 edge), undirected (delete 2 edges))
void DFS_Traverse(int u); //DFS traversal (shell part)
void BFS_Traverse(int u); //BFS traversal
~adjlist_graph(); // Destructor
};
Input Description:
For the input data format of mapping, see the algorithm description of mapping.
First row: type of graph
Line 2: node count
Row 3: node set
Line 4: number of sides
Row 5: edge set
Line 6: element value of the vertex to be inserted
Output Description:
First row: type of graph
Second row: vertex set before insertion
Row 3: adjacency table before insertion
Blank line
Row 4: vertex set after insertion
Row 5: adjacency table after insertion
Input example:
DG
6
A B C D E F
6
0 1
0 2
0 3
1 4
2 4
3 5
G
--------
DG
A B C D E F
A->3->2->1->nullptr
B->4->nullptr
C->4->nullptr
D->5->nullptr
E->nullptr
F->nullptr
A B C D E F G
A->3->2->1->nullptr
B->4->nullptr
C->4->nullptr
D->5->nullptr
E->nullptr
F->nullptr
G->nullptr
------------------------
I just added nodes from the output point of view. In fact, there is no real node added internally, but the answer is correct. This is also simpler. I really don't have time recently. You will make do with it
#include<iostream>
#include<queue>
using namespace std;
int m = 0;
int arr[100][2] = { 0 };
struct bian
{
int num;
int weight;
bian* next = NULL;
};
struct point
{
string letter;
bian* next = NULL;
};
struct graph
{
point m[100];
int number_of_point;
int number_of_bian;
};
void creat_no_directioin(graph& g)
{
int e;
int f;
cin >> e;
g.number_of_point = e;
for (int i = 0; i < e; i++)
{
cin >> g.m[i].letter;
}
//Above is the letter of the input vertex
cin >> f;
g.number_of_bian = f;
for (int i = 0; i < f; i++)
{
int v1;
int v2;
cin >> v1 >> v2;
bian* p1 = new bian;
p1->num = v2;
p1->next = g.m[v1].next;
g.m[v1].next = p1;
bian* p2 = new bian;
p2->num = v1;
p2->next = g.m[v2].next;
g.m[v2].next = p2;
}
}
void creat_direction(graph& g)
{
int e;
int f;
cin >> e;
g.number_of_point = e;
for (int i = 0; i < e; i++)
{
cin >> g.m[i].letter;
}
//Above is the letter of the input vertex
cin >> f;
g.number_of_bian = f;
for (int i = 0; i < f; i++)
{
int v1;
int v2;
cin >> v1 >> v2;
arr[i][0] = v1;
arr[i][1] = v2;
bian* p1 = new bian;
p1->num = v2;
p1->next = g.m[v1].next;
g.m[v1].next = p1;
}
}
int main()
{
string kind;
cin >> kind;
if (kind == "DN")//
{
graph g;
int m = 0;
creat_direction(g);
char am;
cin >> am;
cout << "DG" << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
m = 0;
cout << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
cout << " " << am << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << am << "->" << "nullptr" << endl;
}
else if (kind == "DG")
{
graph g;
int m = 0;
creat_direction(g);
char am;
cin >> am;
cout << "DG" << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
m = 0;
cout << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
cout << " " << am << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout <<am << "->" << "nullptr" << endl;
}
else if (kind == "UDN")//
{
graph g;
int m = 0;
creat_no_directioin(g);
char am;
cin >> am;
cout << "UDN" << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
m = 0;
cout << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
cout << " " << am << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << am << "->" << "nullptr" << endl;
}
else if (kind == "UDG")
{
graph g;
int m = 0;
creat_no_directioin(g);
char am;
cin >> am;
cout << "UDG" << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
m = 0;
cout << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << endl;
for (int h = 0; h < g.number_of_point; h++)
{
if (m == 1)
{
cout << " ";
}
m = 1;
cout << g.m[h].letter;
}
cout << " " << am << endl;
for (int u = 0; u < g.number_of_point; u++)
{
cout << g.m[u].letter;
bian* p = g.m[u].next;
while (p)
{
cout << "->";
cout << p->num;
p = p->next;
}
if (p == NULL)
{
cout << "->" << "nullptr" << endl;
}
}
cout << am << "->" << "nullptr" << endl;
}
return 0;
}