目录
数据类型
存储结构
邻接矩阵表示法
无向图
邻接矩阵表示
有向图
网
实现
邻接矩阵表示
存储结构
创建无向图
优点
缺点
邻接表法表示
表示无向图
表示有向图
存储结构
无向网
特点
十字链表与多重表
十字链表
存储结构
多重表
存储结构
数据类型
存储结构
邻接矩阵表示法
无向图
无向图的度=矩阵中非0元素个数和的一半
邻接矩阵表示
有向图
因此，有向图的度为矩阵中非0元素个数总和
网
实现
邻接矩阵表示
存储结构
创建无向图
优点
缺点
邻接表法表示
表示无向图
表示有向图
示例
存储结构
先表示出所有边结点，再将边结点组成链表连接到各个对应顶点上。
示例
无向网
特点
十字链表与多重表
十字链表
为解决有向图求度不方便的问题
存储结构
firstin表示以data为弧头(终点，即指向data顶点-入)的边，firstout表示以data为弧尾(起点-出)的边。
tailvex表示弧的弧尾(起点)顶点序号，headvex表示弧的弧头(终点)顶点序号，
hlink指向下一个弧头相同的弧，tlink指向下一个弧尾相同的弧。
先列出所有弧，再连接到顶点。
多重表
存储结构
相关代码
#include <iostream>
using namespace std;
//图的存储//1.邻接矩阵存储:边数+顶点数+顶点表-一维+边表-二维
#define maxn 20
#define infi 33333333
//类型定义
typedef struct {char vexs[maxn];//顶点表 int arc[maxn][maxn];//边表 int vexnum,arcnum;//顶点数与边数
}adjgraph;
//创建无向图
//1.输入边数与顶点数，初始边表-无穷
//2.输入顶点，为顶点表赋值
//3.输入边的顶点及权值，为边表赋值：需要先确定顶点的下标才能确定边
int getvex(adjgraph *g,char v){for(int i=1;i<=g->vexnum;i++)if(g->vexs[i]==v) return i;return 0;
}
//后期实现！！！！
//void print(adjgraph *g){
// for(int i=1;i<=g->vexnum;i++)
// if(g->vexs[i]==v) return i;
//}
void create(adjgraph *g){char vex1,vex2;//存储边的顶点 int weigh;//存储边的权值 int v1,v2;//存储边的下标 cout<<"输入顶点数及边数："<<endl;cin>>g->vexnum>>g->arcnum;for(int i=1;i<=g->vexnum;i++){//初始边表 for(int j=1;j<=g->arcnum;j++){g->arc[i][j]=infi;} }for(int i=1;i<=g->vexnum;i++){//存储顶点信息 cout<<"请输入第"<<i<<"个顶点信息：\n";cin>>g->vexs[i];}for(int j=1;j<=g->arcnum;j++){//存储边表信息 cout<<"请输入第"<<j<<"条边的顶点信息：\n";cin>>vex1>>vex2;cout<<"请输入第"<<j<<"条边的权值：\n";cin>>weigh;v1=getvex(g,vex1);v2=getvex(g,vex2);g->arc[v1][v2]=weigh;//单向g->arc[v2][v1]=weigh;//双向-无向图 }
}//2.邻接表表示：顶点表+顶点数+边数
//顶点表：顶点信息+第一条边结点
//边结点：顶点编号+边权+下一条边
int getvex2(adjlist &g,char v){for(int i=1;i<=g.vnum;i++)if(g.vex[i].vex==v) return i;return 0;
}
typedef struct acrnode{//边结点 int adjacr;//记录邻接顶点编号-弧尾 int weigh;//权值 acrnode *next;//有相同弧头顶点的下一个边结点
}acrnode;
typedef struct vnode{//顶点类型 char vex;acrnode *first;
}vnode;
typedef struct {//邻接表 int vnum,acrnum;vnode vex[maxn];//顶点表
}adjlist;
void create(adjlist &g){char v1,v2;int vex1,vex2;acrnode n,m; //1.输入顶点数、边数cin>>g.vnum>>g.acrnum; //2.初始邻接表：输入顶点，初始顶点表头指针为空for(int i=1;i<=g.vnum;i++){cin>>g.vex[i].vex;g.vex[i].first=NULL;}//3.输入边顶点，构造边结点，记录弧头与弧尾顶点，头插边表for(int i=1;i<=g.acrnum;i++){cin>>v1>>v2;vex1=getvex2(g,v1);//弧尾 vex2=getvex2(g,v2);//弧头n=new acrnode;//构造边结点//记录边v1->v2; 并插入到顶点v1的边表中 n->adjacr=vex2;//存储邻接v1的顶点v2的编号 n->next=g.vex[vex1].first;//下一个边结点存储原来v1顶点的第一个边结点g.vex[vex1].first=n;//更新v1顶点的第一条边为n,实现插入 //记录边v2->v1：新边结点结构-左边记录邻接指点编号 权值 右边记录具有同样以v2为弧尾的下一条边结点 m=new acrnode;m->adjacr=vex1;//记录邻接v2的顶点v1的编号m->next=g.vex[vex2].first;//下一个边结点存储v2指向的第一个边结点 g.vex[vex2].first=m;//更新顶点v2的第一条边结点，实现插入 }
}//3.十字链表表示:弧结点+顶点结点==>顶点表+弧数+顶点数-解决有向图找出入度的问题
//弧结点
typedef struct acrnode{int tailvex,headvex;//弧头+弧尾编号struct acrnode *tailacr,*headacr;//分别具有相同弧头和弧尾的下一条弧结点
}arcnode;
typedef struct vexnode{char data;//顶点信息 acrnode *tail,*head;//以顶点为弧尾或为弧头的弧结点
}vexnode;
typedef struct node{int vnum,acrnum;vexnode v[maxn];
};//4.多重表：顶点结点+边结点==>顶点表+边数+顶点数-解决无向图重复存边的问题
typedef struct acrnode{int tailvex,headvex;//组成边结点的两顶点编号 struct acrnode *tailacr,*headacr;//与边结点顶点相同的边结点 int weigh;//边的权重
};
//顶点结点：顶点信息+指向第一条边的指针
typedef struct vexnode{char data;acrnode *first;//第一条边结点
};
typedef struct node{int vnum,vacr;vexnode v[maxn];//顶点表
};
int main(){adjgraph g;create(&g);return 0;
} 
