一、首先是图的存储和表示：
1.图的邻接矩阵表示：使用二维数组map[N][N]可表示图，map[u][v]的内容是一个标志。因为c语言中没有bool的类型，只有int的类型，所以在c中当值为1的时候，表示u和v两个点之间有边，当为0的时候表示两个点之间没有边。在c++中用bool表示，当为false的时候表示没有边，当为true的时候表示有边。
2.图的邻接表表示：用c++中的vector，是一个能够存放任意数据类型的动态数组，可以增加和压缩数据。具体函数为：
| 函数 |
表述 |
| c.assign(beg,end) c.assign(n,elem) |
将[beg; end)区间中的数据赋值给c。 将n个elem的拷贝赋值给c。 |
| c.at(idx) |
传回索引idx所指的数据，如果idx越界，抛出out_of_range。 |
| c.back() |
传回最后一个数据，不检查这个数据是否存在。 |
| c.begin() |
传回迭代器重的可一个数据。 |
| c.capacity() |
返回容器中数据个数。 |
| c.clear() |
移除容器中所有数据。 |
| c.empty() |
判断容器是否为空。 |
| c.end() |
指向迭代器中的最后一个数据地址。 |
| c.erase(pos) c.erase(beg,end) |
删除pos位置的数据，传回下一个数据的位置。 删除[beg,end)区间的数据，传回下一个数据的位置。 |
| c.front() |
传回第一个数据。 |
| get_allocator |
使用构造函数返回一个拷贝。 |
| c.insert(pos,elem) c.insert(pos,n,elem) c.insert(pos,beg,end) |
在pos位置插入一个elem拷贝，传回新数据位置。 在pos位置插入n个elem数据。无返回值。 在pos位置插入在[beg,end)区间的数据。无返回值。 |
| c.max_size() |
返回容器中最大数据的数量。 |
| c.pop_back() |
删除最后一个数据。 |
| c.push_back(elem) |
在尾部加入一个数据。 |
| c.rbegin() |
传回一个逆向队列的第一个数据。 |
| c.rend() |
传回一个逆向队列的最后一个数据的下一个位置。 |
| c.resize(num) |
重新指定队列的长度。 |
| c.reserve() |
保留适当的容量。 |
| c.size() |
返回容器中实际数据的个数。 |
| c1.swap(c2) swap(c1,c2) |
将c1和c2元素互换。 同上操作。 |
| vector<Elem> c vector <Elem> c1(c2) vector <Elem> c(n) vector <Elem> c(n, elem) vector <Elem> c(beg,end) c.~ vector <Elem>() |
创建一个空的vector。 复制一个vector。 创建一个vector，含有n个数据，数据均已缺省构造产生。 创建一个含有n个elem拷贝的vector。 创建一个以[beg;end)区间的vector。 销毁所有数据，释放内存。 |
Vector操作
| 函数 |
描述 |
| operator[] |
返回容器中指定位置的一个引用。 |
//用vector方法创建邻接表式的数组
vector<int> v;
v.push_back(1);
v.push_back(1);
v.push_back(13);
v.push_back(14);
for(i = 0;i < v.size();i++)
{printf("%d",v[i];
}图的遍历分为两种，深度优先（Depth-first-search）和广度优先（Breath-first-search）
1.深度优先（dfs）
dfs是从图中某一个结点出发，依次访问与之相通的没有被访问过的结点，直到图中与之相同的点都被访问到。若还有没有被访问到的点，则另选一个未被访问过的点，继续按照此过程深度遍历图，直到所有的结点都被访问到。
下面是深度优先的代码：
void dfs(int u)
{printf("%d",u); //从未被访问的结点开始访问,并将其标记为已经被访问过 vis[u] = 1; for(i= 1; i <= n;i++) //依次深度优先访问与当前顶点邻接的但没有被访问过的点 if(vis[i] == 0 && map[u][i] == 1)dfs(i);
} 下面是dfs的应用
（1）判断图是否连通，计算连通分量的个数：
若一个图是连通的，有n个顶点，则从图的一个顶点出发进行深度优先遍历，所经过的顶点一定是n个。即对顶点为1-n的图，dfs（1）所访问的结点数一定是n个，用计数器ans作为所访问的次数，若ans为n，则一定是连通图。具体代码如下：
for(int i = 1;i <= n;i++)
if(vis[i] == 0)
{ans++;dfs(i);
} （2）欧拉（回）路问题：
欧拉路：从无向图的一个结点出发走一条道路，每条边恰好经过一次，这样的道路就会称为欧拉路。
欧拉回路：从图中的一个点开始，可以经过图中的每条边并回到最初的位置。
欧拉道路的判断方法：如果一个图是连通的，且该图最多有两个奇点（度数为奇数），则一定存在欧拉道路。
有欧拉回路所必须满足的条件是：
（1）有向图：保证图是连通图，而且每个节点的入度必须等于出度；
（2）无向图：保证图是连通图，且每个节点的度数必须为偶数（不能为0）；所以要判断欧拉回路和欧拉路，统计每个点的度，连通性可以用dfs判断。