图的实现方法
在线调试
图
带权重的图又称为网络
邻接矩阵表示：有边问一（自己到自己没边的为0）
（无向图可以只存下三角，网络需要引入#define INF 10000 ）
#include<stdio.h>
int main()
{
int arr[8][8] = {
{
0, 1, 1, 1, 1, 1, 0, 0}, {
0, 0, 1, 0, 1, 0, 0, 0}, {
0, 0, 0, 1, 0, 0, 0, 0}, {
0, 0, 0, 0, 1, 0, 0, 0}, {
0, 0, 0, 0, 0, 1, 0, 0}, {
0, 0, 1, 0, 0, 0, 1, 1}, {
0, 0, 0, 0, 0, 1, 0, 1}, {
0, 0, 0, 0, 0, 1, 1, 0}} ;for(int i=0;i<8;i++){
for(int j=0;j<8;j++)printf(" %d",arr[i][j]);printf(" \n");} return 0;
}
邻接表
邻接链表
#include<stdio.h>
#include <string.h>
#include<stdlib.h>//无向图的邻接表
#define Mv 100;//the max number of vertextypedef struct vn //顶点数组
{
float price;arcn *next;//注意注意注意注意注意注意注意注意注意注意注意注意注意注意
} vn,adjlist[100];typedef struct arcn //边类型
{
int 下一个端点;arcn *next;
} arcn;typedef struct //图的构成
{
adjlist v;
int vnum,arcnum;
} Gra;int creatG(Gra *G)//图的创建方法
{
scanf("%d%d",&G->vnum,&G->arcnum);printf("图书信息：%d %d\n",G->vnum,G->arcnum);//定点数 边数int aaahhh;scanf("%d",aaahhh); //防止运行完一闪而过return 0;}int main(){
Gra G;int c= creatG(&G); return 0;}
#include<stdio.h>
#include <string.h>
#include<stdlib.h>//无向图的邻接表
#define Mv 100;//the max number of vertextypedef struct vn //顶点数组
{
float price;arcn *next;//注意注意注意注意注意注意注意注意注意注意注意注意注意注意
} vn,adjlist[100];typedef struct arcn //边类型
{
int 下一个端点;arcn *next;
} arcn;typedef struct //图的构成
{
adjlist v;
int vnum,arcnum;
} Gra;int creatG(Gra *G)//图的创建方法
{
scanf("%d%d",&G->vnum,&G->arcnum);printf("图书信息：%d %d\n",G->vnum,G->arcnum);//定点数 边数for(int i=0;i<G->vnum;i++)//定点的初始化{
G->v[i].price=i;G->v[i].next=NULL;}for(int j=0;j<G->arcnum;j++){
int v1,v2;scanf("%d%d",v1,v2);//两端的序号arcn *p1= new arcn;//创造边节点p1->下一个端点=v1;//一端：下一个的编号，只是记录一个（位置的）值p1->next=(G->v[v2]).next;//另一端(G->v[v2]).next=p1;arcn *p2= new arcn;//创造边节点 无向图的对称性p2->下一个端点=v2;//一端：下一个的编号p2->next=(G->v[v1]).next;//另一端(G->v[v1]).next=p2;}int aaahhh;scanf("%d",aaahhh); //防止运行完一闪而过return 0;}int main(){
Gra G;int c= creatG(&G); return 0;}
#include<stdio.h>
#include <string.h>
#include<stdlib.h>//无向图的邻接表
#define Mv 100;//the max number of vertex
int visited[5]={
0,0,0,0,0};
int shuru=0;typedef struct arcn //边类型
{
int 下一个端点;arcn *next;
} arcn;
typedef struct vn //顶点数组
{
float price;arcn *next;//注意注意注意注意注意注意注意注意注意注意注意注意注意注意
} vn,adjlist[100];typedef struct //图的构成
{
adjlist v;
int vnum,arcnum;
} Gra;int creatG(Gra *G)//图的创建方法
{
printf("请输入顶点数 边数");scanf("%d%d",&G->vnum,&G->arcnum);printf("图书信息：%d %d\n",G->vnum,G->arcnum);//定点数 边数for(int i=0;i<G->vnum;i++)//定点的初始化{
G->v[i].price=i*10;G->v[i].next=NULL;}for(int j=0;j<G->arcnum;j++){
int v1=0;int v2=3;for(;shuru<6;shuru++){
if(shuru==0){
v1=0; v2=3;};if(shuru==1){
v1=0; v2=1;};if(shuru==2){
v1=3; v2=2;};if(shuru==3){
v1=1; v2=2;};if(shuru==4){
v1=4; v2=2;};if(shuru==5){
v1=1; v2=4;};}printf("请输入两个端点的序号，例如 0 3");
// scanf("%d%d",v1,v2);//两端的序号arcn *p1= new arcn;//创造边节点p1->下一个端点=v1;//一端：下一个的编号，只是记录一个（位置的）值p1->next=(G->v[v2]).next;//另一端(G->v[v2]).next=p1;arcn *p2= new arcn;//创造边节点 无向图的对称性p2->下一个端点=v2;//一端：下一个的编号p2->next=(G->v[v1]).next;//另一端(G->v[v1]).next=p2;}return 0;}void DFS(Gra *G, int k)
{
//图G为邻接矩阵类型，从第v个便点出发深度优先搜索遍厉图。
printf("输出信息");
visited[k]=true;
arcn *p=G->v[k].next;while(p!=NULL)//边结点非空
{
int w=p->下一个端点;
if(!visited[w])DFS(G,w);p=p->next;
}}int main(){
Gra G;int c= creatG(&G); int k=0;DFS( &G, k);int aaahhh=0;scanf("%d",aaahhh); //防止运行完一闪而过return 0;}
对于邻接矩阵参考书上更加详细的构造：
用邻接矩阵表示法表示图，除了一“个用于存储邻接矩阵的二维数组外",还需要一个一维数组用于存储顶点信息。
//-----图的邻接矩阵存储表示-----
#include <iostream>
using namespace std;#define MaxInt 32767
//表示极大值，即∞
#define MVNum 100
//最大顶点数
typedef char VerTexType;//假设顶点的数据类型为字符型
typedef int ArcType;//假设边的权值类型为整型
typedef struct{
VerTexType vexs [MVNum];//顶点表
ArcType arcs [MVNum] [MVNum];//邻接矩阵
int vexnum, arcnum;//图的当前点数和边数
} AMGraph;
int CreateUDN (AMGraph &G)
{
cin>>G.vexnum>>G.arcnum;//输人总顶点数，总边数for(i=0;i<G.vexnum;i++)cin>>G.vexs[i];//依次输入点的信息(数组一)for(i=0;i<G.vexnum;++i)//邻接矩阵初始化for(j=0;j<G.vexnum; ++j)G.arcs[i] [j] =MaxInt;for(k=0;k<G.arcnum;++k)//构造邻接矩阵{
cin>>v1>>v2>>w; //输人一条边依附的顶点及权值i=locateVex(G, v1) ;j=LocateVex(G,v2); //确定v1和v2在G中的位置，即顶点数组的下标G.arcs[i][j]=w; //边<v1, v2>的权值置为WG.arcs[j][i]=G.arcs[i][j];//置<v1, v2>的对称边<v2, v1>的权值为w}return 1;
}