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

最后

以上就是哭泣草莓最近收集整理的关于Graphs的全部内容，更多相关Graphs内容请搜索靠谱客的其他文章。