c语言 数据结构编程 图状结构的应用

Python013

c语言 数据结构编程 图状结构的应用,第1张

#include <iostream>

#include <fstream>

using namespace std

class edgeset{

public:

int from//边起始点

int end//边终止点

int w//边的权值

}//定义一个类用来存放图的边的信息（kruskal算法中用到）

//==============prim算法=============================

void prim(int a[11][11],int (&path)[11][11]){

cout<<"运用prim算法"<<endl

int i,j,k

int mini,minj,min,sum=0

a[0][0]=-1

cout<<"通道铺设情况：(0-10分别对应点a-k)"<<endl

for(k=1k<11k++){

min=100

for(i=0i<11i++){

for(j=0j<11j++){

if(a[i][i]+a[j][j]==-1 &&a[i][j]>0 &&a[i][j]<min){

min=a[i][j]

mini=i

minj=j

}

}

}

if(a[mini][mini]==-1){

cout<<"("<<mini<<","<<minj<<")"

path[mini][minj]=a[mini][minj]

path[minj][mini]=a[mini][minj]

a[minj][minj]=-1

}

else{

cout<<"("<<mini<<","<<minj<<")"

path[mini][minj]=a[mini][minj]

a[mini][mini]=-1

path[minj][mini]=a[mini][minj]

}

sum=sum+min

}

cout<<endl

cout<<"建设费用为:"<<sum<<endl

//=============最小生成树的邻接矩阵输出==============

cout<<"最小生成树对应的邻接矩阵为："<<endl

for(int x=0x<11x++){

for(int y=0y<11y++){

cout<<path[x][y]<<" "

}

cout<<endl

}

}

//===================================================

//===========kruskal算法=============================

void kruskal(int a[11][11],int(&kpath)[11][11]){

cout<<"运用kruskal算法"<<endl

int i,j,k,d

int num=0

edgeset edge[18]

//将邻接矩阵中权值大于1的边对应的点及权值存到一个边类

for(i=0i<11i++){

for(j=i+1j<11j++){

if(!a[i][j]==0){

edge[num].from=i

edge[num].end=j

edge[num].w=a[i][j]

num++

}

}

}

edgeset tmp

//===================================================

//=======将边按权值大小排序==========================

for(i=1i<18i++){

for(j=0j<18-ij++){

if(edge[j].w>edge[j+1].w){

tmp=edge[j]

edge[j]=edge[j+1]

edge[j+1]=tmp

}

}

}

//===================================================

int m1,m2

edgeset c[11]

int s[11][11]

for(i=0i<11i++)

for(j=0j<11j++){

if(i==j)

s[i][j]=1

else

s[i][j]=0

}

k=1

d=0

int sum=0

cout<<"通道铺设情况：(0-10分别对应点a-k)"<<endl

while(k<11){

for(i=0i<11i++){

if(s[i][edge[d].from]==1)

m1=i

if(s[i][edge[d].end]==1)

m2=i

}

if(m1!=m2){

c[k-1]=edge[d]

cout<<"("<<c[k-1].from<<","<<c[k-1].end<<")"

kpath[c[k-1].from][c[k-1].end]=c[k-1].w

kpath[c[k-1].end][c[k-1].from]=c[k-1].w

sum=sum+c[k-1].w

k++

for(j=0j<11j++){

if(s[m2][j]!=0){

s[m1][j]=s[m2][j]

s[m2][j]=0

}

}

}

d++

}

cout<<endl

cout<<"建设费用为："<<sum<<endl

//=============最小生成树的邻接矩阵输出==============

cout<<"最小生成树对应的邻接矩阵为："<<endl

for(int x=0x<11x++){

for(int y=0y<11y++){

cout<<kpath[x][y]<<" "

}

cout<<endl

}

}

void main(){

int h,z

int a[11][11]

int path[11][11]={0}

//==============数据读入（图的邻接矩阵）=============

ifstream in("picture.txt")

for(h=0h<11h++){

for(z=0z<11z++){

in>>a[h][z]

}

}

//===================================================

cout<<"图的邻接矩阵："<<endl

for(int i=0i<11i++){

for(int j=0j<11j++){

cout<<a[i][j]<<" "

}

cout<<endl

}

int kpath[11][11]={0}

int b[11][11]

ifstream in2("picture.txt")

for(h=0h<11h++){

for(z=0z<11z++){

in2>>b[h][z]

}

}

int ch

cout<<"请选择算法(1:prim算法/2:kruskal算法):"

cin>>ch

cout<<endl

switch(ch){

case 1:prim(a,path)//调用prim算法函数

break

case 2:kruskal(b,kpath)

break

}

}

//希望对你有所帮助

树和图是两种常见的数据结构，在计算机技术应用十分广泛，他们也是两种思考问题的方式，常用于结局实际问题。树最直观的用途就是如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。在数据库系统中，树型结构也是信息的重要组织形式之一，一切具有层次关系的问题都可用树来描述。数据结构的图就是实际情况的抽象，即逻辑模型，然后通过计算机编程来解决问题。比如一个很复杂的地图，有很多城市，有很多路，如何找出最短路径呢？当然是用计算机来算了，你就得用图来表示等等，很多用途，如果你学习数学建模，你会经常遇到他们的好好学吧

#include <iostream>

#include<string.h>

#include<stack>

#include<queue>

const int Max=100

const int VISITED=101010

const int UNVISITED=111111

const int AFFINITY=101010

const int INFINITY=111111

using namespace std

class Edge

{

public:

int start

int end

int weight

Edge(int st=0,int en=0,int w=0):start(st),end(en),weight(w){}

bool operator>(Edge oneEdge){return weight>oneEdge.weight?true:false}

bool operator<(Edge oneEdge){return weight<oneEdge.weight?true:false}

bool operator!=(Edge oneEdge)

{

if(weight!=oneEdge.weight||start!=oneEdge.start||end!=oneEdge.end)

return true

return false

}

}

class AdjGraf

{

private:

int verticesNum

int edgeNum

int **matrix

int *Mark

public:

AdjGraf(int vert)

{

int i=0,j=0

verticesNum=vert

matrix=(int**)new int*[vert]

for(i=0i<verti++)

matrix[i]=new int[vert]

Mark=new int[vert]

for(i=0i<verti++)

for(j=0j<vertj++)

{

matrix[i][j]=0

}

for( int m=0m<verticesNumm++)

Mark[m]=UNVISITED

}

~AdjGraf()

//返回与顶点oneVertex相关联的第一条边

Edge FirstEdge(int oneVertex)

//返回与边PreEdge有相同关联顶点oneVertex的下一条边

Edge NextEdge( Edge preEdge)

//添加一条边

void setEdge(int fromVertex,int toVertex,int weight)

//删一条边

void delEdge(int fromVertex,int toVertex)

//如果oneEdge是边则返回TRUE，否则返回FALSE

bool IsEdge( Edge oneEdge)

{

if(oneEdge.start>=0&&oneEdge.start<verticesNum&&

oneEdge.end>=0&&oneEdge.end<verticesNum)

return true

else return false

}

//返回边oneEdge的始点

int FromVertex(Edge oneEdge){return oneEdge.start}

//返回边oneEdge的终点

int ToVertex(Edge oneEdge){return oneEdge.end}

//返回边oneEdge的权

int Weight(Edge oneEdge){return oneEdge.weight}

void visit(int i){cout<<i+1<<" "}

void BFS(int i=1)

void DFS(int i)

void DFSTraverse(int v)

void DFSNoReverse(int f=1)

Edge UNVISITEDEdge(int f)

}

AdjGraf::~AdjGraf()

{

for(int i=0i<verticesNumi++)

delete[]matrix[i]

delete[]matrix

}

Edge AdjGraf::FirstEdge(int oneVertex)

{int i

Edge tempEdge

tempEdge.start=oneVertex

for( i=0i<verticesNumi++)

if(matrix[oneVertex][i]!=0)

break

tempEdge.end=i

tempEdge.weight=matrix[oneVertex][i]

return tempEdge

}

Edge AdjGraf ::NextEdge( Edge preEdge)

{

Edge tempEdge

tempEdge.start=preEdge.start

int i=0

for(i=preEdge.end+1i<verticesNumi++)

if(matrix[preEdge.start][i]!=0)

break

tempEdge.end=i

tempEdge.weight=matrix[preEdge.start][i]

return tempEdge

}

void AdjGraf::setEdge(int fromVertex,int toVertex,int weight)

{

if(matrix[fromVertex-1][toVertex-1]==0)

edgeNum++

matrix[fromVertex-1][toVertex-1]=weight

}

void AdjGraf::delEdge(int fromVertex,int toVertex)

{

if(matrix[fromVertex][toVertex]==0)

edgeNum--

matrix[fromVertex][toVertex]=0

}

/*************递归实现深度优先****************/

void AdjGraf::DFS(int i)

{

visit(i)

Mark[i]=VISITED

for(Edge e=FirstEdge(i)IsEdge(e)e=NextEdge(e))

if(Mark[ToVertex(e)] == UNVISITED)

DFS(ToVertex(e))

}

void AdjGraf::DFSTraverse(int v)

{

v--

int i

for(i=0i<verticesNumi++)

Mark[i]=UNVISITED

for(i=vi<v+verticesNumi++)

if (Mark[i]== UNVISITED)

DFS(i)

}

Edge AdjGraf::UNVISITEDEdge(int f)

{ int i

for( Edge e=FirstEdge(f)IsEdge(e)e=NextEdge(e))

if(Mark[e.end]==UNVISITED)

return e

return Edge(verticesNum,verticesNum,0)

}

/*************非递归实现深度优先**************/

void AdjGraf::DFSNoReverse(int f)

{

f--

int i,counter=0,j,flag

stack<int>Temp

for(i=0i<verticesNumi++)

Mark[i]=UNVISITED

flag=f

while(counter<12)

{

while(flag!=verticesNum&&IsEdge(UNVISITEDEdge(flag))||!Temp.empty())

{

// Edge tempEdge=UNVISITEDEdge(j)

while(flag!=verticesNum&&Mark[flag]==UNVISITED)

{

visit(flag)

Mark[flag]=VISITED

Temp.push(flag)

flag=UNVISITEDEdge(flag).end

}

if(!Temp.empty())

{

flag=UNVISITEDEdge(Temp.top()).end

Temp.pop()

}

}

if(Mark[counter]==UNVISITED) flag=counter

else counter++

}

}

/*************非递归实现广度优先**************/

void AdjGraf::BFS(int v)

{

int i

v--

for( i=0i<verticesNumi++)

Mark[i]=UNVISITED

queue<int>tempqueue

i=0

/*********v先从指定位置开始，然后从v=0,1,2......

依次检查是否有孤立结点*****************/

while(i<verticesNum)

{

tempqueue.push(v)

while(!tempqueue.empty())

{

v=tempqueue.front()

tempqueue.pop()

if(Mark[v]==UNVISITED)

{

visit(v)

Mark[v]=VISITED

for(Edge e=FirstEdge(v)IsEdge(e)e=NextEdge(e))

{

v=ToVertex(e)

tempqueue.push(v)

}

}

}

/***********防止出现孤立点****************/

if(Mark[i]==VISITED) i++

else v=i

}

}

int main()

{

AdjGraf Graph(12)

Graph.setEdge(1,2,1)

Graph.setEdge(2,1,1)

Graph.setEdge(1,3,5)

Graph.setEdge(3,1,5)/** V1 V12 V11*/

Graph.setEdge(2,4,3)/** /\ / \ */

Graph.setEdge(4,2,3)/** v2v3 V10 V9 */

Graph.setEdge(2,5,7)/** / \ / \ */

Graph.setEdge(5,2,7)/**v4 v5v6-v7 */

Graph.setEdge(4,8,4)/** \ / */

Graph.setEdge(8,4,4)/** v8 */

Graph.setEdge(5,8,3)

Graph.setEdge(8,5,3)

Graph.setEdge(3,6,2)

Graph.setEdge(6,3,2)

Graph.setEdge(3,7,1)

Graph.setEdge(7,3,1)

Graph.setEdge(6,7,6)

Graph.setEdge(7,6,6)

Graph.setEdge(12,9,6)

Graph.setEdge(9,12,6)

Graph.setEdge(12,10,6)

Graph.setEdge(10,12,6)

Graph.setEdge(11,11,6)

cout<<"DFSTraverse:"<<endl

Graph.DFSTraverse(3)

cout<<endl

cout<<"DFSNoReverse:"<<endl

Graph.DFSNoReverse(3)

cout<<endl

cout<<"BFS:"<<endl

Graph.BFS(3)

cout<<endl

return 0

}

以上代码运行环境codeblocks 程序采用DFS递归算法 DFS非递归算法 BFS非递归算法

望采纳~