🎯目的：
1、掌握图结构的静态及操作特点；
2、掌握图结构的静态存储和常见操作在C语言环境中的实现方法；
3、掌握图结构的遍历算法在C语言环境中的实现方法。
4、理解求最小生成树、最短路径、关键路径的算法实现。
🎯内容：
1、会使用邻接矩阵的方式存储图片，并实现相应操作。
2、会使用邻接表的方式存储图片，并实现相应操作。
🎯环境：
TC或VC++。
🎯步骤：
要求：
内容1——邻接矩阵
（1）使用邻接矩阵的方式存储上边无向图；
（2）以矩阵的形式输出无向图；
（3）在邻接矩阵的基础上实现深度优先遍历和广度优先遍历。
邻接矩阵存储图代码：
#include "iostream" using namespace std; #define MaxInt 0 #define MVNum 100 #define OK 1 typedef char VerTexType; typedef int ArcType; typedef int Status; typedef struct{ VerTexType vexs[MVNum];//顶点 ArcType arcs[MVNum][MVNum];//邻接矩阵 int vexnum,arcnum;//当前的点数和边数 }AMGraph; Status CreateUDN(AMGraph &G){ cout<<"请输入总顶点数和总边数："<<endl; cin>>G.vexnum>>G.arcnum;//输入总顶点数和总边数 cout<<"请输入各点的信息："<<endl; for(int i=0;i<G.vexnum;i++)//输入各点信息 cin>>G.vexs[i]; for(int i=0;i<G.vexnum;i++) //初始化邻接矩阵 for(int j=0;j<G.vexnum;j++) G.arcs[i][j]=MaxInt; for(int k=0;k<G.arcnum;k++){ int i,j,v1,v2,w; cout<<"请输入两个点的信息及权值："<<endl; cin>>v1>>v2>>w; i=v1-1;j=v2-1; G.arcs[i][j]=w; G.arcs[j][i]=G.arcs[i][j]; } return OK; } int main(){ AMGraph g; CreateUDN(g); cout<<"无向图邻接矩阵如下："<<endl; for(int i=0;i<g.vexnum;i++){ for(int j=0;j<g.vexnum;j++) printf("%5d",g.arcs[i][j]); cout<<endl; } }
内容2——邻接表
（1）使用邻接表的方式存储图；
（2）以邻接表的形式输出该图；
（3）（选做）实现深度优先遍历和广度优先遍历。
邻接表存储图代码：
#include "iostream" using namespace std; #define MVNum 100 #define OK 1 typedef int OtherInfo; typedef int Status; typedef int VerTexType; typedef struct ArcNode{//边结点 int adjvex;//该边所指向的顶点位置 struct ArcNode *nextarc;//指向下一条边的指针 OtherInfo info;//和边相关的信息 }ArcNode; typedef struct VNode//顶点信息 { VerTexType data; ArcNode *firstarc;//指向第一条依附于带顶点的边和指针 }VNode,AdjList[MVNum]; typedef struct{ AdjList vertices; int vexnum,arcnum;//图的当前顶点数和边数 }ALGraph; Status CreateUDG(ALGraph &G){ cout<<"输入顶点数和总边数"<<endl; cin>>G.vexnum>>G.arcnum; cout<<"输入各点"<<endl; for(int i=0;i<G.vexnum;i++){//输入各点，构建表头结点 cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL; } for(int k=0;k<G.arcnum;k++)//输入各边，构造边表 { int v1,v2,i,j; cout<<"请输入一条边依附的两个顶点："<<endl; cin>>v1>>v2; i=v1-1; j=v2-1; ArcNode *p1; p1=new ArcNode; p1->adjvex=j;//邻接点的序号为j; p1->nextarc=G.vertices[i].firstarc; G.vertices[i].firstarc=p1; ArcNode* p2=new ArcNode; p2->adjvex=i; p2->nextarc=G.vertices[j].firstarc; G.vertices[j].firstarc=p2; } return OK; } Status PrintUDG(ALGraph G) { //邻接表输出图 for(int i = 0; i < G.vexnum; i++){ //遍历图中每一个点 cout << i+1 << "(" << G.vertices[i].data << ")："; //输出当前点的标号和值 ArcNode *p = G.vertices[i].firstarc; //指向当前点的第一条边 while(p) { //输出与当前点相连的所有点的标号和值 cout << p->adjvex + 1 << "(" << G.vertices[p->adjvex].data << ")" << "->"; p = p->nextarc; } cout << "NULL" << endl; } return OK; } int main(){ ALGraph g; CreateUDG(g); PrintUDG(g); }
