代写C++图数据结构、代写Graph C++程序

日期：2018-06-05 04:05

#include <stdlib.h>

#include <stdio.h>

#include <assert.h>

// 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;

}