graph

#include

#include

using namespace std;

#define MAXN 20

struct edge

{

int v1, v2;

int weight;

};/*定义边*/

struct node

{

int v;

struct node*next;

}Alist;//邻接表

class graph

{

public:

graph();

~graph();

void create_graph1();//邻接矩阵的方式创建无向图

void create_graph1_2();//邻接矩阵的方式创建有向图

void create_graph2();//邻接表的方式创建图

void getedge1();//用邻接矩阵的方式得到无向图边的数目

void getedge1_2();//用邻接矩阵的方式得到有向图边的数目

//*****************************

//下面算法是用邻接矩阵的方式写的

int firstadj(int v);

int nextadj(int v, int m);

int degree(int v);

//*****************************

void dfs(int v);

void Travel_dfs();

void bfs(int v);

void Travel_bfs();

//下面算法是判断有向图是否是一颗有向树

void dfs_1(int v);

bool IS_diTree(int v);

//

void prim(int v);

bool inprinm(int v, int a[]);

int kruskal();

//Dijkstra算法

void dijk(int v);

int getmin(int a[]);

private:

int vnum;/*图的顶点数*/

int Arcs[MAXN][MAXN];/*邻接矩阵*/

edge e[MAXN*(MAXN - 1) / 2];//具有n顶点的无向图变得最大条数不超过n（n-1）/2

node vertex[MAXN];

bool visited[MAXN]; //顶点的访问标志

bool judege;

int vnum_1;//访问结点操作计数

};

graph::graph()

{

}

graph::~graph()

{

}

void graph::create_graph1()

{

int i, j;

int v1, v2, w;

char c;

cout << \"请输入顶点数\" << endl;

cin >> vnum;

for (i = 0; i {

for (j = 0; j < MAXN; j++)

{

Arcs[i][j] = 1000;

}

}

for (i = 0; i {

for (j = 0; j < vnum; j++)

{

if (i == j)

Arcs[i][j] = 0;

}

}

Arcs[0][0] = 0;

cout << \"需不需要输入边的权值?(即创建边)(y or n)\" << endl;

cin >> c;

while (c == 'y')

{

cout << \"vi=(vi为第i个顶点)\" << \"vj(vj为第j个顶点\" << \"w(w为vi和vj的权值)\" << endl;

cin >> v1 >> v2 >> w;

Arcs[v1-1][v2-1] = Arcs[v2-1][v1-1] = w;

cout << \"需不需要输入边的权值?(y or n)\" << endl;

cin >> c;

}

}

void graph::create_graph1_2()

{

int i, j;

int v1, v2, w;

char c;

cout << \"请输入顶点数\" << endl;

cin >> vnum;

for (i = 0; i {

for (j = 0; j < MAXN; j++)

{

Arcs[i][j] = 1000;

}

}

for (i = 0; i {

for (j = 0; j < vnum; j++)

{

if (i==j)

Arcs[i][j] = 0;

}

}

Arcs[0][0] = 0;

cout << \"需不需要输入边的权值?(即创建边)(y or n)\" << endl;

cin >> c;

while (c == 'y')

{

cout << \"vi=(vi为第i个顶点)\" << \"vj(vj为第j个顶点\" << \"w(w为vi和vj的权值)\" << endl;

cin >> v1 >> v2 >> w;

Arcs[v1 - 1][v2 - 1] = w;

cout << \"需不需要输入边的权值?(y or n)\" << endl;

cin >> c;

}

}

void graph::create_graph2()

{

int k = 0;

int n;

int v1,v2;

int w;

char c;

cout << \"请输入图的顶点数\" << endl;

cin >> n;

vnum = n;

do

{

cout << \"请输入边（v1,v2,权值）\" << endl;

cin >> v1 >> v2 >> w;

if (v1 >= 0 && v1 < n&&v2 >= 0 && v2 < n)

{

e[k].v1 = v1;

e[k].v2 = v2;

e[k].weight = 2;

k++;

}

cout << \"你还需要输入边嘛？(y ore n)\" << endl;

} while (tolower(c = getchar()) == 'y');

}

void graph::getedge1()

{

int e = 0;

for (int i = 0; i < vnum; i++)

{

for (int j = i; j < vnum; j++)

{

if (Arcs[i][j]>0 && Arcs[i][j] != 1000)

{

e = e + 1;

}

}

}

cout << \"图中边的数目为\" << e << endl;

}

void graph::getedge1_2()

{

int e = 0;

for (int i = 0; i < vnum; i++)

{

for (int j = 0; j < vnum; j++)

{

if (Arcs[i][j]>0&&Arcs[i][j]!=1000)

{

e = e + 1;

}

}

}

cout << \"图中边的数目为\" << e << endl;

}

int graph::firstadj(int v)

{

int x = 0;

for (int i = 0; i < vnum; i++)

{

if (Arcs[v - 1][i] != 0 && Arcs[v-1][i] != 1000)

{

x = i+1;

break;

}

}

return x;

}

int graph::nextadj(int v, int w)

{

int x = 0;

for (int i = w; i < vnum; i++)

{

if (Arcs[v - 1][i] != 0 && Arcs[v - 1][i] != 1000)

{

x = i+1;

break;

}

}

return x;

}

int graph::degree(int v)

{

int x = 0;

for (int i = 0; i < vnum; i++)

{

if (Arcs[v - 1][i] != 0 && Arcs[v - 1][i] != 1000)

{

x = x + 1;

}

}

return x;

}

void graph::dfs(int v)

{

int w;

cout << v << endl;

visited[v - 1] = true;

w = firstadj(v);

while (w != 0)

{

if (visited[w - 1] == false)

dfs(w);

w = nextadj(v, w);

}

}

void graph::Travel_dfs()

{

int i;

for (i = 1; i <= vnum; i++)

visited[i-1] = false;

for (i = 1; i <= vnum; i++)

{

if (visited[i - 1] == false)

dfs(i);

}

}

void graph::bfs(int v)

{

int w,V; int n;

queue q;

//满足队列为空

if (q.empty() == false)

{

n = q.size();

for (int i = 0; i < n; i++)

{

q.pop();

}

}

cout << v << endl;

visited[v - 1] = true;

q.push(v);

while (q.empty() == false)

{

V = q.front();

w = firstadj(V);

while (w != 0)

{

if (!visited[w - 1])

{

cout << v << endl;

visited[w - 1] = true;

q.push(w);

}

w = nextadj(V, w);

}

}

}

void graph::Travel_bfs()

{

int i;

for (i = 1; i <= vnum; i++)

visited[i-1] = false;

for (i = 1; i <= vnum; i++)

{

if (!visited[i-1])

bfs(i);

}

}

void graph::dfs_1(int v)

{

int w;

visited[v - 1] = true;

vnum_1++;

w = firstadj(v);

while (w != 0)

{

if (visited[w - 1] == false)

dfs_1(w);

else judege = false; //顶点W 被重复范文，设置失败标志

w = nextadj(v, w);

}

}

bool graph::IS_diTree(int v)

{

int i; judege = true;

for (i = 1; i <= vnum; i++)

visited[i - 1] = false;

vnum_1 = 0;

dfs_1(v);

return vnum_1 && judege;

}

void graph::dijk(int v)

{

int path[MAXN];

int dist[MAXN];

int w, x;

int min;

for (int i = 0; i < vnum; i++)

visited[i] = false;

visited[v - 1] = true;

for (int i = 0; i < vnum; i++)

{

if (i == v - 1)

{

dist[i] = 0;

path[i] = v;

}

else if (Arcs[v - 1][i] != 1000)

{

dist[i] = Arcs[v - 1][i];

path[i] = v*10+i+1;

}

else

{

dist[i] = 1000;

path[i] = 0;

}

}

int dist_2[MAXN];

for (int i = 0; i < vnum; i++)

{

dist_2[i] = dist[i];

}

for (int i = 0; i < vnum; i++)

{

min = 1000;

x = getmin(dist_2) ;

visited[x-1] = true;

//w = 1;

w = firstadj(x);

while (w!=0)

{

if (dist[x - 1] + Arcs[x - 1][w - 1] < dist[w - 1])

{

dist[w - 1] = dist[x - 1] + Arcs[x - 1][w - 1];

dist_2[w - 1] = dist[w - 1];

path[w - 1] = path[x - 1] * 10 +w;

}

w = nextadj(x, w);

}

dist_2[x - 1] = 1001;

}

for (int i = 0; i < vnum; i++)

{

cout << \"该顶点到\" << i+1<< \"个顶点的最短距离为\" << dist[i] << \" 路径为 \"<< path[i]<}

}

int graph::getmin(int a[])

{

int x=0;

for (int i = 0; i < vnum; i++)

{

if (a[x] >a[i ])

x = i;

}

return x+1;

}

void graph::prim(int v)

{

int vnum_1[MAXN];

for (int i = 0; i < vnum; i++)

{

visited[i] = false;

vnum_1[i] = 0;

}

vnum_1[0] = v;

int MIN, min[2];

MIN = 0;

int x,y,w;

for (int i = 1; i < vnum; i++)

{

min[0] = 1000;

for (int j = 0; j < vnum-1; j++)

{

if (vnum_1[j] != 0)

{

x = vnum_1[j];

y = 1;

w = firstadj(x);

y = nextadj(x, w);

if (y == 0)

{

if (min[0]>Arcs[x - 1][w - 1])

{

min[0] = Arcs[x - 1][w - 1];

min[1] = w;

}

}

else while (y != 0)

{

//w = firstadj(x);

//y = nextadj(x, w);

if (inprinm(w, vnum_1) == false && inprinm(y, vnum_1) == false)

{

if (Arcs[x - 1][w - 1] < Arcs[x - 1][y - 1])

{

if (min[0]>Arcs[x - 1][w - 1])

{

min[0] = Arcs[x - 1][w - 1];

min[1] = w;

}

}

else

{

if (min[0] > Arcs[x - 1][y - 1])

{

min[0] = Arcs[x - 1][y - 1];

min[1] = y;

}

}

}

else if (inprinm(w, vnum_1) == true && inprinm(y, vnum_1) == false)

{

if (min[0] > Arcs[x - 1][y - 1])

{

min[0] = Arcs[x - 1][y - 1];

min[1] = y;

}

}

y = nextadj(x, y);

}

}

}

MIN = MIN + min[0];

vnum_1[i] = min[1];

visited[min[1]] = true;

}

cout << \"最小生成树的权值为\" << MIN << endl;

}

bool graph::inprinm(int v, int a[])

{

for (int i = 0; i < vnum; i++)

{

if (v == a[i])

return true;

}

return false;

}

//*******************************************************

#include

#include

#include

#include\"graph.h\"

using namespace std;

void show_1()

{

cout << \"***************************\" << endl;

cout << \"1-建立新的无向图\" << endl;

cout << \"2-建立新的有向图\" << endl;

cout << \"0-EDND\" << endl;

cout << \"***************************\" << endl;

}

int main()

{

cout << \"数据结构第六次实验\" << endl;

cout << endl;

int choice_1,choice_2,v;

choice_1=choice_2=1;

graph R;

while (choice_1 != 0)

{

show_1();

cout << \"请选择项目:\";

cin >> choice_1;

switch (choice_1)

{

case 1:

R.create_graph1();

R.getedge1();

cout << \"下面是图的深度遍历\" << endl;

R.Travel_dfs();

R.prim(1);

break;

case 2:

R.create_graph1_2();

R.getedge1_2();

cout << \"请输入一个点，改点用于求与其他顶点的最小路径\" << endl;

cin >> v;

R.dijk(v);

if (R.IS_diTree(1) == false)

cout << \"该图是一颗有向树\" << endl;

else

cout << \"该图不是是一颗有向树\" << endl;

break;

default:

break;

}

}

cout << \"谢谢使用\" << endl;