Graphs

89 阅读 0 评论 59 点赞

我是靠谱客的博主哭泣草莓，最近开发中收集的这篇文章主要介绍Graphs，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Graphs

-----------------------------------------------------------------------------------------------------------------------------

Graphs versus Trees

1) Unlike trees, in graphs, a node can have many parents.
2) The link between the nodes may have values or weights.

A simple graph:
A
/ |
B C D
/ /
E F

Notes:
A graph can be a directed/undirected and weighted/un-weighted graph. Here, we will discuss undirected and un-weighted.

Edges -- Represent the connection between nodes.

1. Adjacency Matrix

A B C D E F
A 0 1 1 1 0 0
B 1 0 0 0 1 1
C 1 0 0 0 0 1
D 1 0 0 0 0 0
E 0 1 0 0 0 0
F 0 1 1 0 0 0

2. Adjacency List

* It's an array of linked list nodes.
Array:

0(A) *--> B --> C --> D
1(B) *--> A --> E --> F
2(C) *--> A --> F
3(D) *--> A
4(E) *--> B
5(F) *--> B --> C

Advantages using the adjacency matrix:
1) Simplicity in implementation.
2) Create/Remove edges easily.

Drawbacks of using the adjacency matrix:
1) Increased memory as you need n*n matrix.
2) Redundancy of information. I.e. to represent an edge between A and B, same to B and A.

Depth First Search (DFS)

Algorithmic Steps:

1) Push the root node in the stack.
2) Loop until the stack is empty.
3) Peek the node in the stack.
4) If the node has unvisited child nodes, get the child, mark it as traversed and push it into stack.
5) If the node does not has any unvisited child nodes, pop the node.

Breadth First Search (BFS)

Algorithmic Steps:

1) Push the root node in the queue.
2) Loop until the queue is empty.
3) Remove the node from the queue.
4) If the removed node has unvisited children, mark them as visited and insert the children in the queue.

Reference:
https://www.codeproject.com/articles/32212/introduction-to-graph-with-breadth-first-search-bf