导言：
图，是数据结构中非常重要的一部分。我们之前学过的树，其实都可以算是图的一种特例。所以我们需要对图有非常深刻的理解才能够自如地使用图这个数据结构.
1.什么是图？
在回答什么是图之前，我们需要回答一下什么是数据结构。数据结构就是计算机存储数据的一种方式，这种方式可以方便我们进行排序，遍历，查找等等。所以，图也就是
一种存储数据结构的方式。一堆数据在计算机中怎么去表示呢？之前我们有栈，链表，队列等等表示方式，这些表示方式都可以简单认为是一种线性的表示方式，但是图就不是
，图是一种通过顶点与顶点之间进行连接形成的一种结构，可以用来存储数据。
这就是图，没什么神奇的，不过是按照这种方式去存储罢了！pic--CHENYUE
接下来我们给出一个简单的定义：图是一种多对多的关系，它包括一组顶点（vertex），一组边（edge），其中边是顶点与顶点之前的那段玩意儿，也就是顶点对<v,w>属于E，其中v,w属于V。
2.图的抽象数据类型(ADT)
转自浙大-数据结构MOOC PPT-CHENYUE
可能有些人不知道什么是抽象数据类型，其实简单理解就是对一种数据结构的名称，取值范围啊（类比数学上函数），这个数据结构怎么操作的（类比面向对象语言中的类中的函数）.其实就是这个东西了。抽象数据类型的出现其实是为了对一种数据结构有一个统一的模板进行描述。
3.常见术语
无向图：若点对的次序无所谓，那么图是无向的，也就称为无向图，可以记做（u，v）或者（v,u）.
有向图：如果点对是有序的，那么图是有向的，也就称为有向图.<u, v>这里约定u指向v，其中u被称作该边的顶点或尾顶点，而v称作该边的终点，或者头顶点。
度：对于任何边e=(v,u),称顶点u与v彼此邻接，互为邻居，而它们都与边e彼此关联。在无向图中，与顶点v关联的边数，称作v的度数（degree），记做deg(v).对于有向图e = <u,v>,其中e称作u的出边，v的入边，v的出边总数称作其出度，入边总数称作其入度。
权值：就是边上的值，带有权重的边组成的图，有时称作网络。
理解着三个术语，基本上其他术语的理解就不是太大问题了，都是从这些派生出去的。以后遇到一个再学一个就成。
4.图的几种表示方式（c语言描述）
1.邻接矩阵
邻接矩阵是图最基本的一种表现方式
PPT来源--CHENYUE
上面PPT中画的其实是无（有）向图的邻接矩阵，如果是网络，只需要把1换成权重就行了。
实现（c语言）：
#include <stdio.h> #include <stdlib.h> #define MAXVERTEXNUM 400 #define INFINITY 65535 typedef char VertexType; //设置顶点类型为字符型 typedef int EdgeType; //设置边类型为整数类型 enum GraphType{DG,UG,DN,UN}; //有向图，无向图，有向网图，无向网图 typedef struct{ EdgeType vertexs[MAXVERTEXNUM]; //顶点表 VertexType edges[MAXVERTEXNUM][MAXVERTEXNUM]; //边表，就是邻接矩阵 int n,e; //顶点数和边数 enum GraphType GType; //图的类型 }MGraph; //MGraph是以邻接矩阵表示的图 void creatGraph(MGraph *G) { int i,j,k,w; G->GType = UN; //无向网络图 printf("请输入顶点数和边数：\n"); scanf("%d %d",&G->n,&G->e); printf("请输入顶点：\n"); for(i=0;i<G->n;i++) { scanf("%d",&G->vertexs[i]); } for(i=0;i<G->n;i++) { for(j=0;j<G->n;j++) { G->edges[i][j] = INFINITY; //初始化邻接矩阵 } } printf( "请输入每条边对应的两个顶点的序号和权值，输入格式为:i, j, w:\n" ); for(k=0;k<G->e;k++) { scanf("%d %d %d",&i,&j,&w); G->edges[i][j] = w; G->edges[j][i] = w; //因为矩阵是对称的。 } } int main() { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); creatGraph(G); printf("Hello world!\n"); return 0; }
2.邻接表
#include <stdio.h> #include <stdlib.h> #define MAX_VEXTER_NUM 100 //最大顶点数 typedef char VertexType; typedef int EdgeType; typedef struct node //边表结构 { int Adjv; //邻接点 struct node *next; //指向邻接点的第一条边 }EdgeNode; typedef struct VNode //顶点结构 { VertexType vertex; //顶点 EdgeNode *FirstEdge; //指向该顶点的第一条边 }VertexNode; typedef struct Graph //图结构 { VertexNode Adjlist[MAX_VEXTER_NUM]; //邻接表 int n,e; //顶点数和边数 }ALGraph; void CreatGraph(ALGraph *G) { int i,j,k,w; printf("请输入顶点数和边数：\n"); scanf("%d %d",&G->n,&G->e); EdgeNode *edge; //初始化顶点 for(i=0; i<G->n; i++) { G->Adjlist[i].vertex = i; G->Adjlist[i].FirstEdge = NULL; } printf("请输入边的信息：(v,w) \n"); for(i=0; i<=G->e; i++) { scanf("%d %d",&k,&w); //读入顶点信息 edge = (EdgeNode*)malloc(sizeof(EdgeNode)); edge->Adjv = w; edge->next = G->Adjlist[k].FirstEdge; G->Adjlist[k].FirstEdge = edge; //如果是无向图，还得生成一个节点 edge = (EdgeNode*)malloc(sizeof(EdgeNode)); edge->Adjv = k; edge->next = G->Adjlist[w].FirstEdge; G->Adjlist[w].FirstEdge = edge; } } int main() { ALGraph *G; G = (ALGraph*)malloc(sizeof(ALGraph)); CreatGraph(G); return 0; }
原文：http://www.cnblogs.com/fuchen1994/p/5279192.html