网的邻接矩阵
const int MAXN = 100;const int LIM = 0x3f3f3f3f;//无穷大struct MGraph{ int vexs[MAXN];//顶点表 int arc[MAXN][MAXN];//邻接矩阵 int numEdges, numVertexes;//边,顶点的数量};void CreatMGraph(MGraph *G){ int i, j, k, w; cout << "请输入顶点和边的数量:"; cin >> G->numVertexes >> G->numEdges; for (i = 0; i < G->numVertexes; i++)//建立顶点表 cin >> G->vexs[i]; for (i = 0; i < G->numVertexes; i++)//邻接矩阵的初始化 for (j = 0; j < G->numVertexes; j++) G->arc[i][j] = LIM; for (k = 0; k < G->numEdges; k++) { cout << "请输入(vi-vj)的标识和权:"; cin >> i >> j >> w; G->arc[i][j] = w; G->arc[j][i] = G->arc[i][j]; }}
无向图的邻接表
const int MAXN = 10000;struct EdgeNode //边表节点{ int adjvex;//邻接点域(有向图中弧头下标) int Weight;//权值 EdgeNode *next;//指向下一个边表};struct VertexNode //顶点表节点{ char data;//顶点域 EdgeNode *firstedge;//边表头指针};struct GraphAdjList//图{ VertexNode adjList[MAXN];//顶点表数组 int numVertexea, numEdges;//图中顶点数和边数};void CreatALGraph(GraphAdjList *G){ int i, j, k; EdgeNode *e; cout << "请输入顶点数和边数" << endl; cin >> G->numVertexea >> G->numEdges; for (i = 0; i < G->numVertexea; i++) { cin >> G->adjList[i].data;//输入顶点信息 G->adjList[i].firstedge = NULL;//边表制空 } for (k = 0; k < G->numEdges; k++)//头插法 { cout << "输入边(vi,vj)上的顶点序号:" << endl; cin >> i >> j; EdgeNode *e = new EdgeNode; e->adjvex = j; e->next = G->adjList[i].firstedge; G->adjList[i].firstedge = e; e = new EdgeNode; e->adjvex = i; e->next = G->adjList[j].firstedge; G->adjList[j].firstedge = e; }}
有向图的十字链表
struct EdgeNode//边表{ int headVex, tailVex;//弧的起点和终点在顶点表中的下标 EdgeNode *hLink, *tLink;//指向终点,起点相同的下一条边};struct VexNode//顶点节点{ int data;//顶点数据 EdgeNode *firstin;//指向第一个入度边表 EdgeNode *firstout;//指向第一个出度边表};struct Graph{ VexNode List[100];//定点表的建立 int vexnum, edgenum;//顶点和边的数量};void creat(Graph *G){ cout << "请输入顶点和边的数量:"; cin >> G->vexnum >> G->edgenum; for (int i = 0; i < G->vexnum; i++) { cout << "输入顶点:"; cin >> G->List[i].data; G->List[i].firstin = G->List[i].firstout = NULL;//指针初始化 } for (int i = 0; i < G->edgenum; i++) { int x,y; cout << "读入(vi-vj):"; cin >> x >> y;//头尾的下标,若x,y不是对应的下标则需要自己写一个查找函数找到下标 EdgeNode *p = new EdgeNode; p->tailVex = x;//头插法 p->headVex = y; p->hLink = G->List[y].firstin; p->tLink = G->List[x].firstout; G->List[i].firstin = p; G->List[i].firstout = p; }}
无向图的邻接多重表
struct EdgeNode//顶点表节点{ int ivex, jvex;//两个顶点的下标 EdgeNode *iLink, *jLink;//指向依附于ivex和jvex的下一条边};struct VexNode//边表{ int data; EdgeNode *firstedge;//指向改顶点的第一个边节点};struct Graph//总图{ VexNode list[100];//顶点表 int vexnum, edgenum;};void creat(Graph *G){ cout << "请输入顶点和边数:"; cin >> G->vexnum >> G->edgenum; for (int i = 0; i < G->vexnum; i++)//顶点表初始化 { cin >> G->list[i].data; G->list[i].firstedge = NULL; } for (int i = 0; i < G->edgenum; i++) { int a, b; EdgeNode *p = new EdgeNode; cout << "请输入(vi-vj)的i,j下标"; cin >> a >> b; p->ivex = a; p->jvex = b; p->iLink = G->list[a].firstedge; p->jLink = G->list[b].firstedge; G->list[a].firstedge = p; G->list[b].firstedge = p; }}