辅导C++图数据结构、辅导Graph C++程序解析C/C++编程|辅导Python程序

#include
#include
#include

// A vertex is a 2D point
typedef struct Vertex {
int x; // x-coordinate
int y; // y-coordinate
} Vertex;
// each edge is a pair of vertices (end-points)
typedef struct Edge {
Vertex *p1; // first end point
Vertex *p2; // second end point
} Edge;
typedef struct VertexNode {
Vertex *v;
} VertexNode;
typedef struct GraphRep *Graph;
typedef struct GraphRep { // graph header
VertexNode *vertices; // an array of vertices or a linked list of vertices
int nV; // #vertices
int nE; // #edges
} GraphRep;
// A vertex node stores a vertex and other information, and you need to expand this type

//The above types serve as a starting point only. You need to expand them and add more types.
// Watch the lecture video between 7:50pm-8:20 or so for my discussion about this assignment

// Add the time complexity analysis of CreateEmptyGraph() here
Graph CreateEmptyGraph()
{
}

// Add the time complexity analysis of InsertEdge() here
int InsertEdge(Graph g, Edge *e)
{
}

// Add the time complexity analysis of DeleteEdge() here
void DeleteEdge(Graph g, Edge *e)
{
}

// Add the time complexity analysis of ReachableVertices() here
void ReachableVertices(Graph g, Vertex *v)
{
}

// Add the time complexity analysis of ShortestPath() here
void ShortestPath(Graph g, Vertex *u, Vertex *v)
{
}

// Add the time complexity analysis of FreeGraph() here
void FreeGraph(Graph g)
{
}

// Add the time complexity analysis of ShowGraph() here
void ShowGraph(Graph g)
{
}

int main() //sample main for testing
{
Graph g1;
Edge *e_ptr;
Vertex *v1, *v2;

// Create an empty graph g1;
g1=CreateEmptyGraph();

// Create first connected component
// Insert edge (0,0)-(0,10)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=0;
v2->y=10;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (0,0)-(5,6)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=5;
v2->y=6;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (0, 10)-(10, 10)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=10;
v2->x=10;
v2->y=10;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (0,10)-(5,6)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=10;
v2->x=5;
v2->y=6;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (0,0)-(5,4)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=5;
v2->y=4;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (5, 4)-(10, 4)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=5;
v1->y=4;
v2->x=10;
v2->y=4;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (5,6)-(10,6)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=5;
v1->y=6;
v2->x=10;
v2->y=6;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (10,10)-(10,6)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=10;
v1->y=10;
v2->x=10;
v2->y=6;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (10, 6)-(10, 4)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=10;
v1->y=6;
v2->x=10;
v2->y=4;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Create second connected component
// Insert edge (20,4)-(20,10)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=20;
v1->y=4;
v2->x=20;
v2->y=10;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (20,10)-(30,10)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=20;
v1->y=10;
v2->x=30;
v2->y=10;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
// Insert edge (25,5)-(30,10)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=25;
v1->y=5;
v2->x=30;
v2->y=10;
e_ptr->p1=v1;
e_ptr->p2=v2;
if (InsertEdge(g1, e_ptr)==0) printf("edge exists\n");
//Display graph g1
ShowGraph(g1);
// Find the shortest path between (0,0) and (10,6)
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=10;
v2->y=6;
ShortestPath(g1, v1, v2);
free(v1);
free(v2);

// Delete edge (0,0)-(5, 6)
e_ptr = (Edge*) malloc(sizeof(Edge));
assert(e_ptr != NULL);
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=5;
v2->y=6;
e_ptr->p1=v1;
e_ptr->p2=v2;
DeleteEdge(g1, e_ptr);
free(e_ptr);
free(v1);
free(v2);
// Display graph g1
ShowGraph(g1);
// Find the shortest path between (0,0) and (10,6)
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=10;
v2->y=6;
ShortestPath(g1, v1, v2);
free(v1);
free(v2);
// Find the shortest path between (0,0) and (25,5)
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v2=(Vertex *) malloc(sizeof(Vertex));
assert(v2 != NULL);
v1->x=0;
v1->y=0;
v2->x=25;
v2->y=5;
ShortestPath(g1, v1, v2);
free(v1);
free(v2);
// Find reachable vertices of (0,0)
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v1->x=0;
v1->y=0;
ReachableVertices(g1, v1);
free(v1);
// Find reachable vertices of (20,4)
v1=(Vertex*) malloc(sizeof(Vertex));
assert(v1 != NULL);
v1->x=20;
v1->y=4;
ReachableVertices(g1, v1);
free(v1);
// Free graph g1
FreeGraph(g1);
return 0;
}

辅导C++图数据结构、辅导Graph C++程序 解析C/C++编程|辅导Python程序

辅导C++图数据结构、辅导Graph C++程序解析C/C++编程|辅导Python程序