c++利用邻接矩阵存储方法实现图的存储与输出。
关于图的深度优先遍历代码如下:
#include
#include
#define FALSE 0
#define TURE 1
#define OK 1
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20 //最大顶点个数
typedef struct ArcCell{
int adj; //顶点关系类型。用1或0表示相邻与否
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //二维数组
typedef struct {
char vexs[MAX_VERTEX_NUM]; //顶点向量
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //顶点数和弧数
}MGraph;
int LocateVex(MGraph G,char u)
{ //若图G中存在顶点u,则返回该顶点在图中的位置;否则返回-1
int i;
for(i=0;i<G.vexnum;i++)
if(G.vexs[i]==u)
return i;
else return -1;
}
int CreateDG(MGraph G){ //构造有向图G
int i,j,k;
char va,vb;
printf("请输入有向图G的顶点数 弧数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
printf("请输入%d个顶点的值(<5个字符):
",G.vexnum);
for(i=0;i<G.vexnum;i++) scanf("%s",&G.vexs[i]); //构造顶点向量
for(i=0;i<G.vexnum;i++) //初始化邻接矩阵
for(j=0;j<G.vexnum;j++)
{
G.arcs[i][j].adj=0;
}
printf("请输入%d条弧的弧尾 弧头:
",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%*c",&va,&vb);
i=LocateVex(G,va);
j=LocateVex(G,vb);
G.arcs[i][j].adj=1;
}
return OK;
}
int FirstAdjVex(MGraph G,char v)
{ //返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
int i,k;
k=LocateVex(G,v); //k为顶点v在图G中的序号
for(i=0;i<G.vexnum;i++)
if(G.arcs[k][i].adj!=0)
return i;
else return -1;
return OK;
}
int NextAdjVex(MGraph G,char v,char w)
{ //返回v的相对于(w)的下一个邻接顶点的序号,若w是v的最后一个邻接顶点,则返回-1
int i,k1,k2;
k1=LocateVex(G,v); //k1为顶点v在图G中的序号
k2=LocateVex(G,w); //k2为顶点w在图G中的序号
for(i=k2+1;i<G.vexnum;i++)
if(G.arcs[k1][i].adj!=0)
return i;
else return -1;
return OK;
}
int visited[MAX_VERTEX_NUM];
int DFS(MGraph G,int v)
{ //从第v个顶点出发递归的深度优先遍历图G
int w;
visited[v]=TURE; //设置访问标志为TURE
printf("%s",G.vexs[v]);
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
if(!visited[w])
DFS(G,w); //对尚未访问的序号为w的邻接顶点递归的调用DFS
return OK;
}
int DFSTraverse(MGraph G)
{ //从第一个顶点起,深度优先遍历图G
int v;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE; //访问标志数组初始化
for(v=0;v<G.vexnum;v++)
if(!visited[v])
DFS(G,v); //对尚未访问的顶点v调用DFS
printf("
");
return OK;
}
int main()
{
MGraph G;
CreateDG(G);
DFSTraverse(G);
system("pause");
return OK;
}
广度可以自己参照改写。。
Visual C++的用户界面,通常被称为集成开发环境,具有包括创建源代码、编辑代码、编译、链接和调试等功能。
Visual C++用户界面包括菜单和工具栏、项目工作空间、用来进行文件与资源编辑的主工作空间、下端的输出窗口和状态栏。
Visual C++菜单栏包括九个菜单。调试时,Visual C++还提供各种窗口,包括变量窗口、观察窗口、寄存器、存储器、调试堆栈窗口、反汇编窗口等。
Microsoft Visual C++,(简称Visual C++、MSVC、VC++或VC)是Microsoft公司推出的开发Win64环境程序,面向对象的可视化集成编程系统。它不但具有程序框架自动生成、灵活方便的类管理、代码编写和界面设计集成交互操作、可开发多种程序等优点,而且通过简单的设置就可使其生成的程序框架支持数据库接口、OLE2,WinSock网络、3D控制界面,包括标准版、专业版和企业版。ß它以拥有“语法高亮”,IntelliSense(自动完成功能)以及高级除错功能而著称。比如,它允许用户进行远程调试,单步执行等。还有允许用户在调试期间重新编译被修改的代码,而不必重新启动正在调试的程序。其编译及建置系统以预编译头文件、最小重建功能及累加连结著称。这些特征明显缩短程式编辑、编译及连结花费的时间,在大型软件计划上尤其显著。
希望我能帮助你解疑释惑。
#include <iostream>
using namespace std;
//*****stack.h
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int Status;
template<class QElemType>
class stack
{
public:
void InitStack();
void DestroyStack();
void ClearStack();
Status StackEmpty();
Status StackLength();
void GetTop(QElemType & e);
void Push(QElemType e);
void Pop(QElemType & e);
private:
struct SqStack{
QElemType *base;
QElemType *top;
int stacksize;
}S;
};
//******stack.cpp------
template<class QElemType>
void stack<QElemType>::InitStack()
{
S.base = (QElemType *)malloc(STACK_INIT_SIZE * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
}
template <class QElemType>
void stack<QElemType>::DestroyStack()
{
free(S.base);
}
template <class QElemType>
void stack<QElemType>::ClearStack()
{
S.top = S.base;
}
template <class QElemType>
Status stack<QElemType>::StackEmpty()
{
if(S.top == S.base) return 1;
else return 0;
}
template <class QElemType>
Status stack<QElemType>::StackLength()
{
return (S.top - S.base);
}
template <class QElemType>
void stack<QElemType>::GetTop(QElemType & e)
{
if(S.top != S.base)
e = *(S.top - 1);
else cout << "ERROR" << endl;
}
template <class QElemType>
void stack<QElemType>::Push(QElemType e)
{
if(S.top - S.base >= S.stacksize)
{
S.base = (QElemType *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(QElemType));
if(!S.base) exit(0);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
}
template <class QElemType>
void stack<QElemType>::Pop(QElemType & e)
{
if(S.top == S.base) cout << "ERROR" << endl;
else
e = * --S.top;
}
//**********stack.cpp End
template <class TElemType>
class Graph
{
public:
void CreateUDN();
void DestroyUDN();
void CreateAlgraph();
void DestroyAlgraph();
void DFS(int v,bool *visited);
void DFSTraverse();
void Minispantree_prim(); //PRIM算法求最小生成树
void Shortestpath_DIJ(TElemType data1,TElemType data2); //对环不适用,如从V1到V1就不适用
void Shortestpath_FLOYD(TElemType data1,TElemType data2);
private:
template <class TElemType>
struct Mgraph{
int vexnum;
int arcnum;
TElemType *vertex;
int **AdjMatrix;
};
Mgraph<TElemType> gph; //邻接矩阵存储
struct Arcnode
{
int adjvex;
Arcnode *nextarc;
float weight;
};
template <class TElemType>
struct Vexnode
{
TElemType data;
Arcnode *firarc;
};
struct ALgraph
{
int vexnum;
int arcnum;
bool kind;
Vexnode<TElemType> *vex;
};
ALgraph algraph; //邻接表存储
};
//*********Graph.cpp
template <class TElemType>
void Graph<TElemType>::CreateUDN()
{
cout << "输入无向网的顶点数和边数:" << endl;
cin >> gph.vexnum >> gph.arcnum;
gph.vertex = (TElemType *)malloc(gph.vexnum * sizeof(TElemType));
int i,j,m,n; //m,n表示顶点信息对应的序号,w是权值
int w;
TElemType v1,v2;
cout << "输入顶点信息:" << endl;
for(i = 0;i < gph.vexnum;i++)
cin >> gph.vertex[i];
gph.AdjMatrix = (int **)malloc(gph.vexnum * sizeof(int *));
for(i = 0;i < gph.vexnum;i++)
gph.AdjMatrix[i] = (int *)malloc(gph.vexnum * sizeof(int));
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
gph.AdjMatrix[i][j] = INT_MAX; //INT_MAX
cout << "输入一条边依附的两点及权值:" << endl;
for(int k = 0;k < gph.arcnum;k++)
{
cin >> v1 >> v2 >> w;
for(i = 0;i < gph.vexnum;i++)
{
if(v1 == gph.vertex[i]) m = i;
if(v2 == gph.vertex[i]) n = i;
}
gph.AdjMatrix[m][n] = gph.AdjMatrix[n][m] = w;
}
}
template <class TElemType>
void Graph<TElemType>::DestroyUDN()
{
free(gph.vertex);
for(int i = 0;i < gph.vexnum;i++)
free(gph.AdjMatrix[i]);
free(gph.AdjMatrix);
}
template <class TElemType>
void Graph<TElemType>::CreateAlgraph()
{
int i,j,m,n;
float w;
TElemType v1,v2;
Arcnode *p;
cout << "输入图类型(1是无向图,0是有向图):" << endl;
cin >> algraph.kind;
cout << "输入顶点数和边数:" << endl;
cin >> algraph.vexnum >> algraph.arcnum;
algraph.vex = (Vexnode<TElemType> *)malloc(algraph.vexnum * sizeof(Vexnode<TElemType>));
cout << "输入顶点信息:" << endl;
for(i = 0;i < algraph.vexnum;i++)
{
cin >> algraph.vex[i].data;
algraph.vex[i].firarc = NULL;
}
if(algraph.kind)
{
cout << "输入各边依附的两点和权值:" << endl;
for(i = 0;i < algraph.arcnum;i++)
{
cin >> v1 >> v2 >>w;
for(j = 0;j < algraph.vexnum;j++)
{
if(v1 == algraph.vex[j].data) m = j;
if(v2 == algraph.vex[j].data) n = j;
}
p = (Arcnode *)malloc(2*sizeof(Arcnode));
p[0].adjvex = n;p[0].weight = w;
p[1].adjvex = m;p[1].weight = w;
p[0].nextarc = algraph.vex[m].firarc;algraph.vex[m].firarc = p;
p[1].nextarc = algraph.vex[n].firarc;algraph.vex[n].firarc = ++p;
}
}
else
{
cout << "输入各边的弧尾与弧头结点及有向边的权值:" << endl;
for(i = 0;i < algraph.arcnum;i++)
{
cin >> v1 >> v2 >> w;
for(j = 0;j < algraph.vexnum;j++)
{
if(v1 == algraph.vex[j].data) m = j;
if(v2 == algraph.vex[j].data) n = j;
}
p = (Arcnode *)malloc(sizeof(Arcnode));
p->adjvex = n;p->weight = w;
p->nextarc = algraph.vex[m].firarc;algraph.vex[m].firarc = p;
}
}
} //构造完成
template <class TElemType>
void Graph<TElemType>::DestroyAlgraph()
{
int i;
Arcnode *p,*q;
for(i = 0;i < algraph.vexnum;i++)
{
p = algraph.vex[i].firarc;
if(p)
{
q = p->nextarc;
while(q)
{
free(p);
p = q;
q = q->nextarc;
}
free(p);
}
}
free(algraph.vex);
}
template <class TElemType>
void Graph<TElemType>::DFS(int v,bool *visited)
{
cout << algraph.vex[v].data << endl;
visited[v] = true;
Arcnode *p;
int v1;
for(p = algraph.vex[v].firarc;p;p = p->nextarc)
{
v1 = p->adjvex;
if(!visited[v1]) DFS(v1,visited);
}
}
template <class TElemType>
void Graph<TElemType>::DFSTraverse()
{
int i,v;
bool *visited = (bool *)malloc(algraph.vexnum * sizeof(bool));
for(i = 0;i < algraph.vexnum;i++)
visited[i] = false;
for(v = 0;v < algraph.vexnum;v++)
if(!visited[v]) DFS(v,visited);
free(visited);
} //EndDFSTraverse
template <class TElemType>
void Graph<TElemType>::Minispantree_prim()
{
struct closedge
{
int adjvex;
int lowcost;
};
closedge *edge = (closedge *)malloc(gph.vexnum * sizeof(closedge));
int i,j,k = 0,u;
int min;
for(i = 0;i < gph.vexnum;i++)
{
if(i != k)
{
edge[i].adjvex = 0;
edge[i].lowcost = gph.AdjMatrix[k][i];
}
}
edge[k].lowcost = 0;
cout << "最小生成树的边如下:" << endl;
for(i = 1;i < gph.vexnum;i++)
{
min = INT_MAX;
for(j = 0;j < gph.vexnum;j++)
if(edge[j].lowcost != INT_MAX &&edge[j].lowcost != 0 && edge[j].lowcost < min)
{
min = edge[j].lowcost;
k = j;
}
u = edge[k].adjvex;
edge[k].lowcost = 0;
cout << "(" << gph.vertex[u] << "," << gph.vertex[k] << ")" << " ";
for(j = 0;j < gph.vexnum;j++)
if(gph.AdjMatrix[j][k] < edge[j].lowcost)
{
edge[j].lowcost = gph.AdjMatrix[j][k];
edge[j].adjvex = k;
}
}
free(edge);
cout << endl;
}
template <class TElemType>
void Graph<TElemType>::Shortestpath_DIJ(TElemType data1,TElemType data2)
{
int i,j,v,u,k,min;
stack<int> S;
S.InitStack();
int *spath = (int *)malloc(gph.vexnum * sizeof(int));
int *pathrecord = (int *)malloc(gph.vexnum * sizeof(int));
bool *visited = (bool *)malloc(gph.vexnum * sizeof(bool));
for(i = 0;i < gph.vexnum;i++) visited[i] = false;
for(i = 0;i < gph.vexnum;i++)
{
if(data1 == gph.vertex[i]) v = i;
if(data2 == gph.vertex[i]) u = i;
}
for(i = 0;i < gph.vexnum;i++)
{
spath[i] = gph.AdjMatrix[v][i];
pathrecord[i] = v;
}
spath[v] = 0;visited[v] = true;pathrecord[v] = -1;
for(i = 1;i < gph.vexnum;i++)
{
min = INT_MAX;
for(j = 0;j < gph.vexnum;j++)
{
if(!visited[j])
{
if(spath[j] < min) {min = spath[j];k = j;}
}
}
visited[k] = true;
for(j = 0;j < gph.vexnum;j++)
if(!visited[j] && gph.AdjMatrix[k][j] < INT_MAX && spath[k]+gph.AdjMatrix[k][j] < spath[j])
{
spath[j] = spath[k]+gph.AdjMatrix[k][j];
pathrecord[j] = k;
}
}
free(visited);
cout << spath[u] << endl;
S.Push(u);
for(v = pathrecord[u];v != -1;v = pathrecord[v])
S.Push(v);
while(!S.StackEmpty())
{
S.Pop(i);
cout << gph.vertex[i] << " ";
}
cout << endl;
S.DestroyStack();
free(spath);
free(pathrecord);
}
template <class TElemType>
void Graph<TElemType>::Shortestpath_FLOYD(TElemType data1,TElemType data2)
{
int i,j,k,v,u,m;
int **D = (int **)malloc(gph.vexnum * sizeof(int *));
bool ***path = (bool ***)malloc(gph.vexnum * sizeof(bool **));
for(i = 0;i < gph.vexnum;i++)
{
D[i] = (int *)malloc(gph.vexnum * sizeof(int));
path[i] = (bool **)malloc(gph.vexnum * sizeof(bool *));
if(data1 == gph.vertex[i]) v = i;
if(data2 == gph.vertex[i]) u = i;
}
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
path[i][j] = (bool *)malloc(gph.vexnum *sizeof(bool));
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
{
D[i][j] = gph.AdjMatrix[i][j];
for(k = 0;k < gph.vexnum;k++)
path[i][j][k] = false;
if(D[i][j] < INT_MAX)
{
path[i][j][i] = true;path[i][j][j] = true;
}
}
for(k = 0;k < gph.vexnum;k++)
for(i = 0;i < gph.vexnum;i++)
for(j = 0;j < gph.vexnum;j++)
if(D[i][k] != INT_MAX && D[k][j] != INT_MAX && D[i][k]+D[k][j] < D[i][j])
{
D[i][j] = D[i][k] + D[k][j];
for(m = 0;m < gph.vexnum;m++)
path[i][j][m] = path[i][k][m] || path[k][j][m];
}
cout << "从" << gph.vertex[v] << "到" << gph.vertex[u] << "的最短路径及经过的点如下:" << endl;
cout << D[v][u] << endl;
for(i = 0;i < gph.vexnum;i++)
if(path[v][u][i] == true) cout << i << " ";
cout << endl;
for(i = 0;i < gph.vexnum;i++)
{
free(D[i]);
free(path[i]);
}
free(D);
free(path);
}
//***********end Graph
int main()
{
Graph<int> gph;
gph.CreateUDN();
gph.Minispantree_prim();
int data1,data2;
cout << "输入起点和终点:" << endl;
cin >> data1 >> data2;
gph.Shortestpath_DIJ(data1,data2);
//gph.Shortestpath_FLOYD(data1,data2);
gph.DestroyUDN();
return 0;
}
功能函数都实现了,可以自己在源程序中调用函数实现各种功能。
void dfs(adj,v)
{ visited[v-1]=1;//标志是否被访问过
visit(v);//cout<<v;
for(p=adj[v-1].firstarc;p!=NULL;p=p->nextarc)
if(!visited[p->adjvex-1]) dfs(adj,p->adjvex);
}
//prim
#define MAXINT (1<<(sizeof(int)*8-1) )-1
#define NUM 图顶点数
void prim1(g[][NUM],v0,n)//g-图, v0-起始点(1到n),n-图顶点数
{
for(i=0;i<n;i++) set[i]=0; //memset(set,’\0’,sizeof(set))
set[v0-1]=1;//v0在集合U中
for(k=1;k<=n-1;k++){
min=MAXINT;
for(i=0;i<n;i++)
if(set[i]==1)
for(j=0;j<n;j++)
if(set[j]==0 )
if(g[i][j]<min) { p=i;q=j;min=g[i][j];}
set[q]=1;
cout<<p+1<<‘ ‘<<q+1<<‘ ‘<<min<<endl;
}//for k
}
//djk
#define NUM
void shortpath_dij(g[][NUM],v0) //v0为源点,值为1到NUM
{
for(i=0;i<NUM;i++){
set[i]=0;
dist[i]=g[v0-1][i];}
set[v0-1]=1;
for(i=1;i<NUM;i++)
{ min=MAXINT;
for(w=0;w<NUM;w++)
if(set[w]= =0 && dist[w]<min)
{ v=w; min=dist[w]; }
set[v]=1;
for(w=0;w<NUM;w++)
if(set[w]= =0 && dist[v]+g[v][w]<dist[w])
dist[w]=dist[v]+g[v][w];
}//for i
} //shortpath_dij
/****这些是我数据结构的课件上的内容你稍作修改应该可以了,希望对你有帮助,最短路径的完整代码我这也有。你可以找我***/
有很多现成的代码,不用浪费分数了。
n个顶点e条边的图G用邻接表存储,则求每个顶点入度的时间复杂度为?查了...
O(n+e)是对的,O(n*n)是用邻接矩阵存储时的时间复杂度。算法就是遍历每一条边,然后把每条边的终点的入度+1.在邻接表中,就是要依次访问每个顶点,然后在每个顶点中依次访问每条边,把这些边的终点的入度+1。也就是每个顶点和每条边依次要各访问一遍,所以时间复杂度是O(n+e)。在邻接矩阵中...
...个结点、e 条边且采用数组表示法(即邻接矩阵存储)的无向图进行深度...
【答案】:A图的邻接矩阵是指用一个矩阵来表示图中顶点之间的关系。对有 n 个结点的图,其邻接矩阵是一个n阶方阵。对于无向图来说,其邻接矩阵如下图所示当采用深度优先进行遍历的时候,查找所有邻接点所需要的时间是O(n^2) 。
图的存储结构主要有两种
邻接矩阵可以方便地判断任意两个顶点之间是否有边相连,在求最小生成树和最短路径等算法中具有一定的优势。2、邻接表:邻接表是一种链表的数组,每个顶点对应一个链表,链表中存储与该顶点相邻的顶点信息。邻接表可以方便地找到任意顶点的邻接点,在图的遍历和拓扑排序等算法中具有一定的优势。
图--存储结构(邻接矩阵)
上一节,学习了 图的基本概念或术语 ,本节学习图的存储结构: 邻接矩阵 邻接矩阵 又称数组表示法,图示形如坐标轴,一般的做法是通过 定点表Vexs 记录顶点信息, 邻接矩阵arcs (二维数组)记录各顶点的关系,图示形如坐标轴。在邻接矩阵中, 顶点i和顶点j直接...
图的邻接表的时间复杂度问题
其实是O(n + e),顶点加上边数 那个O(n*e)的意思是每次插入一条边,都需要重新查找边所包含两个顶点信息对应的下标,正常的算法没这么弱智吧,不需要顶点信息即为顶点的下标,用散列等方法可以不用这样的 用邻接矩阵构造图时,若存储的是一个无向图,则时间复杂度为O(n^2 + n*e),其中,...
用邻接矩阵储存图,所占用的储存空间大小只与图中顶点个数
图的邻接矩阵存储所占用空间大小只与顶点个数有关,更准确地说,设顶点n个,则与n^2成正比(n的平方)
2015考研:计算机数据结构常用算法(7)?
遍历图的过程实质上是_对每个顶点查找其邻接点的过程___ 其耗费的时间主要取决于采用的存储结构。当用邻接矩阵存储图时,查找每个顶点的邻接点所需的时间O( ),其中n是图中顶点数。而当用邻接表存储图时,找邻接点的所需时间为O(e),其中e为图中边的个数或有向弧的个数,由此,当以邻接表作为...
图的图的存储表示
数组(邻接矩阵)存储表示(有向或无向)邻接表存储表示有向图的十字链表存储表示无向图的邻接多重表存储表示一个不带权图中若两点不相邻,邻接矩阵相应位置为0,对带权图(网),相应位置为∞。一个图的邻接矩阵表示是唯一的,但其邻接表表示不唯一。在邻接表中,对图中每个顶点建立一个单链表(并...
谁能举一个Pascal中Dijkstra算法求单源最短路径问题的例子并作一些说明...
[问题分析]对于一个含有n个顶点和e条边的图来说,从某一个顶点Vi到其余任一顶点Vj的最短路径,可能是它们之间的边(Vi,Vj),也可能是经过k个中间顶点和k+1条边所形成的路径(1≤k≤n-2)。下面给出解决这个问题的Dijkstra算法思想。设图G用邻接矩阵的方式存储在GA中,GA[i,j]=maxint表示Vi...
数据结构学生来看明白数据结构
是一种通过键值对直接访问数据的结构。散列表的实现原理正是映射的原理,通过设定的一个关键字和一个映射函数,就可以直接获得访问数据的地址,实现O(1)的数据访问效率。邻接矩阵 目前常用的图存储方式为邻接矩阵,通过所有顶点的二维矩阵来存储两个顶点之间是否相连,或者存储两顶点间的边权重。
黎水洁奈:[答案] /* MGraph.cc: 图的邻接矩阵存储表示和实现 */ /* 包含图类型Graph定义;创建图;深度优先遍历;广度优先遍历 */ /* 用到引用型参数,在TC下无法通过编译,VC等C++编译器可通过 */ #include
沙坪坝区13582761679: 如何用c++写出以邻接矩阵构造的无向图的遍历 - ?
黎水洁奈: 你能不能给贴上一个深度遍历错误的用例?你这个输入用例的结果就是1,2,3,4 现在能看出来的就是这个了,int LocateVex (MGraph G,VertexType v){ int i; for(i = 0;i<G.vexnum;i++) if(G.vexs[i] == v){ //这里应该是等于v,而不是等于i return i; } return -1; }
沙坪坝区13582761679: c/c++图的邻接矩阵存储结构 - ?
黎水洁奈: 关于图的深度优先遍历代码如下: #include <stdio.h> #include <stdlib.h> #define FALSE 0 #define TURE 1 #define OK 1 #define INFINITY INT_MAX #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef struct ArcCell{int adj; //顶点关系类型...
沙坪坝区13582761679: C++采用邻接表存储结构,实现无向图的创建和广度优先搜索程序. - ?
黎水洁奈: #include"stdio.h"#include"stdlib.h"#define MaxVertexNum 50 //定义最大顶点数 typedef struct node{ //边表结点 int adjvex; //邻接点域 struct node *next; //链域 }EdgeNode; typedef struct vnode{ //顶点表结点 char vertex; //顶点域 EdgeNode ...
沙坪坝区13582761679: C++实现数据结构 某带权有向图G?
黎水洁奈: dev c++下运行成功 #include #include #define MAXV 50 typedef struct//邻接矩阵存储结构 { int no; int info; }VertexType; typedef struct { int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }MGraph; typedef struct ANode //邻接表存储结构 { int ...
沙坪坝区13582761679: 有向图的邻接矩阵存储 - ?
黎水洁奈: 有向图的邻接矩阵,用类似于二维链表做过,下面是c++的代码: //顶点结构 struct VexNode {char data;ArcNode *firstarc; }; //弧结构 struct ArcNode { //邻接顶点的下标int adjvex;ArcNode *nextarc; };class AdjList { private:VexNode data[100];int vn,an; //顶点数 弧数 public://构造函数以及其他的一些函数AdjList();virtual ~AdjList(); };
沙坪坝区13582761679: 求一个源代码要求显示图的邻接矩阵图的邻接表,深度广度优先遍历最小生成树PRIM算法KRUSCAL算法图的连通分1.显示图的邻接矩阵,图的邻接表,深... - ?
黎水洁奈:[答案] 用C++实现的,希望对你有所帮助. #include #include using namespace std; #define int_max 10000 #define inf 9999 #define max 20 //…………………………………………邻接矩阵定义…………………… typedef struct ArcCell { int adj; char *info; }...
沙坪坝区13582761679: 网络图中顶点的插入与删除算法用C++怎么实现 - ?
黎水洁奈: 如果是用图的邻接矩阵存储的话,数组足够大,直接在二维数组的末端插入一行数据,譬如已有i-1个结点,插入a【i】【】行数据,就是把和这个结点有连接的边置1,比如i和i-2有连接,a【i】【i-2】=1,如果是有向图的话,也一样,只需读入有连接边的顶点的编号,注意顶点的顺序
沙坪坝区13582761679: 要求采用邻接矩阵作为无向图的存储结构,邻接表作为有向图的存储结构,完成无向图和有向图的建立,并对建 - ?
黎水洁奈: #include"utility.h" #include"adj_matrix_undir_graph.h" #include"adj_list_dir_graph.h" #include"dfs.h" #include"bfs.h" int main(void) { int n,j=0,i=0; int m,e,b=0; char vexs[20],c; char nums[20]; cout<<"输入无向图的顶点个数n:"<<endl; ...
沙坪坝区13582761679: 数据结构: 用C++ 编写邻接表存储,实现有向图的深度搜索. 要自己写的 主要是邻接表的建立 - ?
黎水洁奈: #include <iostream>#include <string>#include <vector>#include <fstream>#include <iterator>#include <cassert> using namespace std; struct stArcNode{ stArcNode( int adjVex, int weight, stArcNode *next = NULL, void *info = NULL ):_adjVex(...